题目描述
难度分:1400
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(2≤n≤2×105)和长为n的数组a(0≤a[i]≤109)。
等概率地从a中选出两个下标不同的数a[i]和a[j]。
输出a[i]×a[j]的期望值,模109+7。
输入样例
3
3
3 2 3
4
2 2 2 4
5
1 2 3 4 5
输出样例
7
6
500000012
算法
后缀和
总共的方案数是C2n=n(n−1)2,每种方案的概率均等。所以根据期望的公式E=2n(n−1)Σ1≤i<j≤na[i]×a[j],可以发现E=2n(n−1)Σi∈[1,n−1]a[i]×s[i+1],其中s[i]=Σnj=ia[j],是数组a的后缀和。
因此预处理出一个后缀和就能计算出2Σi∈[1,n−1]a[i]×s[i+1]的部分,而分数取模的除法部分,预处理出逆元就能直接代入公式使用。
复杂度分析
时间复杂度
预处理出后缀和数组s和逆元的时间复杂度为O(n),计算期望值的时间复杂度也为O(n),这也是整个算法的时间复杂度。
空间复杂度
空间消耗就是后缀和数组s以及逆元数组inv(inv[i]表示i在模109+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;
}