长沙网站建设招聘,重庆做网站开发的公司,百度帐号注册,wordpress 首页调用Problem - D - Codeforces
题目大意#xff1a;有n个数#xff0c;其中有m个匹配对#xff0c;对于一个匹配对#xff08;x,y#xff09;#xff0c;他们的除湿贡献为z#xff0c;一共有k轮行动#xff0c;每一轮从n个数中独立等概率的选出两个数#xff0c;如果这两…Problem - D - Codeforces
题目大意有n个数其中有m个匹配对对于一个匹配对x,y他们的除湿贡献为z一共有k轮行动每一轮从n个数中独立等概率的选出两个数如果这两个数在一个匹配对内那么就贡献z的分数同时z永远1如果不在匹配对立就贡献0问最终分数的期望是多少
2n1e5;0mmin(1e5,n*(n-1)/2);1k2e5
思路因为只有匹配对被选中才有贡献所以很容易想到可以枚举每个匹配对然后枚举其被选中的次数被选中的次数符合二项分布但这样两层循环枚举显然会超时。 因为每一对被选中的概率都是一样的只有初始贡献不同所以如果我们把每个匹配对的初始贡献的期望都算出来这样就可以把所有匹配对看做m个初始贡献为0的匹配对只需要枚举被选中的次数然后乘以m即可。 考虑怎么算初始贡献的期望每个匹配对被选中的概率psel1/C(2,n)k轮中被选中的次数的期望就是k/C(2,n)再乘以贡献zz*k/C(2,n)就是单个匹配对初始贡献的期望可以O(m)的时间求出。 然后从2到k枚举每个匹配对被选中的次数i被选中i次的累计贡献为(0i-1)*i/2因为每次被选中的概率psel独立等概符合二项分布所以被选中i次的概率为C(i,k)*(psel)的i次方*(1-psel)的k-i次方再乘以m将所有贡献相加注意预处理逆元和取模即可。
//#include__msvc_all_public_headers.hpp
#includebits/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-pselMOD)%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;
}
