A 数学 和式变换

题意

有一串长度为 $n$ 的串 $s$, 随机选择有序对 $(x, y)$ 且 $1 \le x \le y \le n$, 求 $\frac{\sum \limits_{i=x}^{y}s_i}{y - x + 1}$ 的期望

思路

注意：这里的随机不是指 $x, y$ 在 $[1, n]$ 均匀分布且随机, 而是指满足 $1 \le x \le y \le n$ 的有序对 $(x, y)$ 中随机抽取。

设：$F(x, y) = \frac{\sum \limits_{i=x}^{y}s_i}{y - x + 1}$, 那么:

$E(F(x, y)) = \binom{n}{2}^{-1}\sum \limits_{i=1}^{n} \sum \limits_{j=i}^{n}\frac{sum[j] - sum[i - 1]}{j-i+1}$

由于分母太难看，不妨换成 $len = j - i + 1$, 对 $i$ 进行换元，有：

$\frac{sum[j] - sum[i - 1]}{j-i+1} = \frac{sum[j] - sum[j - len]}{len}$

然后考虑置换和式的变量，和式是由以下方程围成的空间：

$i = 1$, $j = n$, $j = i$

置换 $i$ 后，和式是由以下方程围成的空间：

$j = len$, $j = n$,$len = 1$

先计算 $j$，再计算 $len$，得到：

$E(F(x, y)) = \binom{n}{2}^{-1}\sum \limits_{len=1}^{n} \sum \limits_{j=len}^{n}\frac{sum[j] - sum[j - len]}{len} = \binom{n}{2}^{-1}\sum \limits_{len=1}^{n} \frac{suffix[len] - prefix[n - len]}{len}$

其中，suffix 是 sum 的后缀和，prefix 是 sum 的前缀和，我们可以 $O(n)$计算 sum 以及 sum 的前后缀和，以及 $1$ 到 $n$ 的逆元，$O(n)$ 算出上列式子，时间复杂度 $O(n)$

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 2e5 + 5, MOD = 1e9 + 7;
ll sum[N], inv[N], prefix[N], suffix[N];

ll quick_pow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}

void init() {
    inv[1] = 1;
    for (int i = 2; i < N; ++i) {
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
}

int main() {
    int t;
    init();
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        sum[0] = prefix[0] = suffix[n + 1] = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &sum[i]);
            sum[i] = (sum[i - 1] + sum[i]) % MOD;
            prefix[i] = (prefix[i - 1] + sum[i]) % MOD;
        }
        for (int i = n; i >= 1; --i) {
            suffix[i] = (suffix[i + 1] + sum[i]) % MOD;
        }
        ll ans = 0;
        for (int len = 1; len <= n; ++len) {
            ans = (ans + (suffix[len] - prefix[n - len]) % MOD * inv[len]) % MOD;
        }
        ans = ans * quick_pow(1ll * n * (n + 1) / 2 % MOD, MOD - 2) % MOD;
        ans = (ans + MOD) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}