题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$。

等概率地从$a$中选出两个下标不同的数$a[i]$和$a[j]$。

输出$a[i] \times a[j]$的期望值，模$10^9+7$。

输入样例

3
3
3 2 3
4
2 2 2 4
5
1 2 3 4 5

输出样例

7
6
500000012

算法

后缀和

总共的方案数是$C_{n}^{2}=\frac{n(n-1)}{2}$，每种方案的概率均等。所以根据期望的公式$E=\frac{2}{n(n-1)}\Sigma_{1 \leq i \lt j \leq n}a[i] \times a[j]$，可以发现$E=\frac{2}{n(n-1)}\Sigma_{i \in [1,n-1]}a[i] \times s[i+1]$，其中$s[i]=\Sigma_{j=i}^{n}a[j]$，是数组$a$的后缀和。

因此预处理出一个后缀和就能计算出$2\Sigma_{i \in [1,n-1]}a[i] \times s[i+1]$的部分，而分数取模的除法部分，预处理出逆元就能直接代入公式使用。

复杂度分析

时间复杂度

预处理出后缀和数组$s$和逆元的时间复杂度为$O(n)$，计算期望值的时间复杂度也为$O(n)$，这也是整个算法的时间复杂度。

空间复杂度

空间消耗就是后缀和数组$s$以及逆元数组$inv$（$inv[i]$表示$i$在模$10^9+7$意义下的逆元）的空间，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 1e9 + 7;
int t, n, a[N], s[N], inv[N];

int main() {
    scanf("%d", &t);
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= N - 10; i++) {
        inv[i] = 1LL * (MOD - MOD/i) * inv[MOD % i] % MOD;
    }
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        s[n + 1] = 0;
        for(int i = n; i >= 1; i--) {
            s[i] = (s[i + 1] + a[i]) % MOD;
        }
        int ans = 0;
        for(int i = 1; i < n; i++) {
            ans = (ans + 2LL * a[i] * s[i + 1] % MOD * inv[n] % MOD * inv[n - 1] % MOD) % MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}