牛客小白月赛42 C 寒潭烟光

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

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

由于数列构成不唯一，我们可以构造数列 $a=0,0,0,\dots \dots ,n\times F(x)a=\{0,\; 0,\; 0,\; \dots \dots ,n\times F(x)\}$，放置 $n-1n-1$ 个 $00$ ，满足条件。

然后我们计算加入 $x_{0}x\_0$ 后的数列的 $F(a)F(a)$ 值。

序列 $a\mathrm{\prime }=x_0,0,0,0,\dots \dots ,n\times F(x)a\prime =\{x\_0,0,0,0,\dots \dots ,n\times F(x)\}$，于是前缀和数组的总和为：

$(n+1)\times x_0+n\times fx(n\; +\; 1)\; \times \; x\_0\; +\; n\; \times \; fx$。

因为要取平均值，所以我们除以 $n+1n+1$。

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

答案相当于：$\frac{(n+1)\times x_0+n\times fx}{n+1}=\frac{(n+1)\times x_0+(n+1)\times fx-fx}{n+1}=x_0-fx-\frac{fx}{n+1}\backslash frac\{(n\; +\; 1)\; \times \; x\_0\; +\; n\; \times \; fx\}\{n+1\}=\backslash frac\{(n\; +\; 1)\; \times \; x\_0\; +\; (n+1)\; \times \; fx-fx\}\{n+1\}=x\_0-fx-\backslash frac\{fx\}\{n+1\}$。

这样就没事了。

代码。