应该是前五题中最难的吧。

这个数据范围很大,我们必须使用单次操作 O(1)O(1) 的方法。

由于数列构成不唯一,我们可以构造数列 a=0,0,0,,n×F(x)a={0, 0, 0, ……,n×F(x)},放置 n1n-100 ,满足条件。

然后我们计算加入 x0x_0 后的数列的 F(a)F(a) 值。

序列 a=x0,0,0,0,,n×F(x)a′={x_0,0,0,0,……,n×F(x)},于是前缀和数组的总和为:

(n+1)×x0+n×fx(n + 1) × x_0 + n × fx

因为要取平均值,所以我们除以 n+1n+1

但是呢这么写好像会爆,我们变形一下式子。

答案相当于:(n+1)×x0+n×fxn+1=(n+1)×x0+(n+1)×fxfxn+1=x0fxfxn+1\frac{(n + 1) × x_0 + n × fx}{n+1}=\frac{(n + 1) × x_0 + (n+1) × fx-fx}{n+1}=x_0-fx-\frac{fx}{n+1}

这样就没事了。

代码。