应该是前五题中最难的吧。
这个数据范围很大,我们必须使用单次操作 的方法。
由于数列构成不唯一,我们可以构造数列 ,放置 个 ,满足条件。
然后我们计算加入 后的数列的 值。
序列 ,于是前缀和数组的总和为:
。
因为要取平均值,所以我们除以 。
但是呢这么写好像会爆,我们变形一下式子。
答案相当于:。
这样就没事了。
应该是前五题中最难的吧。
这个数据范围很大,我们必须使用单次操作 O(1) 的方法。
由于数列构成不唯一,我们可以构造数列 a=0,0,0,……,n×F(x),放置 n−1 个 0 ,满足条件。
然后我们计算加入 x0 后的数列的 F(a) 值。
序列 a′=x0,0,0,0,……,n×F(x),于是前缀和数组的总和为:
(n+1)×x0+n×fx。
因为要取平均值,所以我们除以 n+1。
但是呢这么写好像会爆,我们变形一下式子。
答案相当于:n+1(n+1)×x0+n×fx=n+1(n+1)×x0+(n+1)×fx−fx=x0−fx−n+1fx。
这样就没事了。