F. Sakurako's Box

传送门：Problem - 2008F - Codeforces

Sakurako has a box with nn balls. Each ball has it's value. She wants to bet with her friend that if the friend randomly picks two balls from the box (it could be two distinct balls, but they may have the same value), the product of their values will be the same as the number that Sakurako guessed.

Since Sakurako has a PhD in probability, she knows that the best number to pick is the expected value, but she forgot how to calculate it. Help Sakurako and find the expected value of the product of two elements from the array.

It can be shown that the expected value has the form PQ, where P and Q are non-negative integers, and Q≠0. Report the value of P⋅Q−1(mod10^9+7)

Input

The first line contains a single integer t (1≤t≤10^4)  — the number of test cases.

The first line of each test case contains a single integer nn (2≤n≤2⋅10^5)  — the number of elements in the array.

The second line of each test case contains nn integers a1,a2,…,an (0≤ai≤10^9)  — the elements of the array.

It is guaranteed that the sum of nn across all test cases does not exceed 2⋅10^5.

Output

For each test case, output the value of P⋅Q−1(mod10^9+7)

题目描述

樱子有一个装有 n 个球的盒子。每个球都有自己的价值。她想和她的朋友打赌，如果她的朋友从盒子里随机挑选两个球(可能是两个不同的球，但它们的价值可能相同)，它们的价值的乘积将与樱子猜测的数字相同。

由于樱子是概率学博士，她知道最好的数字是 期望值，但她忘了如何计算。请帮助樱子找出数组中两个元素乘积的期望值。

可以证明期望值的形式为 PQ ，其中 P 和 Q 是非负整数，而 Q≠0 。请报告 P⋅Q−1(mod10^9+7) 的值。

题意不难，暴力行不通n有点大。只需要预处理一个后缀数组，然后用前缀和的方式计算答案即可

我试过几次C++都wa了因为范围溢出了

溢出范围代码

#include <iostream>#define ll long longusing namespace std;const int N = 2e5 + 10, mod = 1e9 + 7;
ll a[N], pre[N], f[N];int t, n;ll qmi(ll m, ll k, ll p){ll res = 1 % p, t = m;while(k){if(k & 1) res = res * t % p;t = t * t % p;k >>= 1;}return res;
}ll inv(ll x){return qmi(x, mod - 2, mod);
}void solve()
{cin >> n;ll sum = 0;for(int i = 1;i <= n;i ++){cin >> a[i];sum = (sum + a[i]) % mod;pre[i] = 0, f[i] = 0;}for(int i = 1;i <= n;i ++){pre[i] = (sum - a[i] + mod) % mod;sum = (sum - a[i] + mod) % mod;}for(int i = 1;i <= n;i ++){f[i] = ((ll)a[i] * pre[i] % mod + f[i - 1]) % mod;}f[n] = 2 * f[n] % mod * inv(n * (n - 1)) % mod;cout << f[n] << endl;
}int main()
{cin >> t;while(t --){solve();}return 0;
}

 py有他的好处也有坏处和c++结合是不错的选择。这里快速幂求逆元（费马小定理）的模板在这里：快速幂已经快速幂求逆元（数论）-CSDN博客

ac代码

mod = 10**9 + 7
N = 2 * 10**5 + 10
pre = [0] * N
f = [0] * Ndef qmi(m, k, p):res = 1 % pt = mwhile k:if k & 1:res = res * t % pt = t * t % pk >>= 1return resdef inv(x):return qmi(x, mod - 2, mod)def main(n):ls = list(map(int,input().split()))s = sum(ls)# print(s)a = [0] * (n + 1)for i in range(1, n + 1):f[i] = 0pre[i] = 0a[i] = ls[i - 1]for i in range(1, n + 1):pre[i] = s - a[i]s -= a[i]f[i] = pre[i] * a[i] + f[i - 1]f[n] = f[n] * 2 * inv(n * (n - 1)) % modprint(f[n])t = int(input())
for _ in range(t):n = int(input())main(n)

加油