Good Trip Codeforces Round 921 (Div. 2) 1925D

Problem - D - Codeforces

题目大意：有n个数，其中有m个匹配对，对于一个匹配对（x,y），他们的除湿贡献为z，一共有k轮行动，每一轮从n个数中独立等概率的选出两个数，如果这两个数在一个匹配对内，那么就贡献z的分数，同时z永远+1，如果不在匹配对立就贡献0，问最终分数的期望是多少

2<=n<=1e5;0<=m<=min(1e5,n*(n-1)/2);1<=k<=2e5

思路：因为只有匹配对被选中才有贡献，所以很容易想到可以枚举每个匹配对，然后枚举其被选中的次数，被选中的次数符合二项分布，但这样两层循环枚举显然会超时。

        因为每一对被选中的概率都是一样的，只有初始贡献不同，所以如果我们把每个匹配对的初始贡献的期望都算出来，这样就可以把所有匹配对看做m个初始贡献为0的匹配对，只需要枚举被选中的次数然后乘以m即可。

        考虑怎么算初始贡献的期望，每个匹配对被选中的概率psel=1/C(2,n)，k轮中被选中的次数的期望就是k/C(2,n)，再乘以贡献z，z*k/C(2,n)就是单个匹配对初始贡献的期望，可以O(m)的时间求出。

        然后从2到k枚举每个匹配对被选中的次数i，被选中i次的累计贡献为(0+i-1)*i/2，因为每次被选中的概率psel独立等概符合二项分布，所以被选中i次的概率为C(i,k)*(psel)的i次方*(1-psel)的k-i次方，再乘以m，将所有贡献相加，注意预处理逆元和取模即可。

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll n;
ll fac[N];
ll inv[N];
ll qpow(ll a, ll b)
{//快速幂a %= MOD;ll ret = 1;while (b){if (b & 1){ret = ret * a % MOD;}a = a * a % MOD;b >>= 1;}return ret;
}
ll C(ll x, ll y)
{//组合数的O(1)算法return inv[x] * fac[y] %MOD * inv[y - x] % MOD;
}
void initfac()
{//预处理阶乘和逆元fac[0] = inv[0] = 1;for (int i = 1; i <= 200000; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = qpow(fac[i], MOD - 2);}
}
void init()
{}
void solve()
{cin >> n;init();ll m;cin >> m;ll k;cin >> k;ll ans = 0;ll psel = qpow(C(2, n), MOD - 2);//每个匹配对被选中的概率for (int i = 1; i <= m; i++){ll x, y, z;cin >> x >> y >> z;ans = (ans + k * psel % MOD * z % MOD) % MOD;//算出每个匹配对的除湿贡献产生的期望}for (ll i = 2; i <= k; i++){//枚举每个匹配对被选中的次数ll con = i * (i - 1) % MOD * qpow(2, MOD - 2) % MOD;//被选中i次的总贡献ll pro = C(i, k) * qpow(psel, i) % MOD * qpow((1-psel+MOD)%MOD, k - i) % MOD;//被选中i次的概率ans = (ans + con * pro % MOD * m % MOD) % MOD;}cout << ans;cout << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;initfac();while (t--){solve();}return 0;
}