CF1925D Good Trip 题解

Solution

不好做的地方在于每一对朋友的友谊值是不同的，于是考虑将其统一为一个数。比较好想的就是将他们的初始友谊值提前计算，即对于每一次远足，设总情况为 \(S=\frac{n \times (n-1)}{2}\)，总的初始友谊值为 \(w=\sum_{i=1}^{m} f_i\)，假设友谊值不变，获得的期望友谊值为 \(\frac{w}{S}\)，共有 \(k\) 次远足，所以初始友谊值的贡献即为 \(\frac{k \times w}{S}\)。

现在我们可以认为每一对朋友的友谊值为 \(0\)，带来的好处是每一对朋友的期望增加量可以认为是相同的。于是考虑其中一对朋友被选中了 \(t\) 次，那么这对朋友的增加量为 \(h=\frac{t*(t-1)}{2} \times P(t)\)，\(P(t)\) 是被选中 \(t\) 次的概率。设 \(p1\) 为这 \(t\) 次远足在 \(k\) 次远足中出现的情况数，即 \(p1=\binom{k}{i}\)；设 \(p2\) 为这对朋友被选中 \(t\) 次的期望，所以 \(p2=(\frac{1}{S})^t\)；设 \(p3\) 为这对朋友在剩余的 \(k-t\) 次远足中不再被选中的期望，所以 \(p3=(\frac{S-1}{S})^{k-t}\)。那么 \(P(t)=p1\times p2 \times p3\)。知道了其中一对朋友出现 \(0 \sim k\) 次的期望后，乘上 \(m\) 即为总的期望增加量。

void work(){ 
    cin>>n>>m>>k; int ans=0,res=0; 
    for(int i=1,a,b,p;i<=m;i++) cin>>a>>b>>p,ans=(ans+p)%Mod; 
    int S=n*(n-1)/2%Mod,invS=qmi(S,Mod-2); ans=k*ans%Mod*invS%Mod; 
    for(int i=1;i<=k;i++){ 
        int w=i*(i-1)/2%Mod; 
        res=(res+w*C(k,i)%Mod*qmi(invS,i)%Mod*qmi((S-1)*invS%Mod,k-i)%Mod)%Mod; 
    } ans=(ans+res*m%Mod)%Mod; printf("%lld\n",ans); 
}