I - 双人登山 - Solution

期望的贡献可以分为两部分，第一部分是原始 $f_i$ 数组产生的贡献，第二部分是增加的数产生的贡献，注意到第二部分和原数组没有任何关系，只与增加的方案相关。

第一部分的贡献即 $\frac{k\sum _{i=1}^{m}f_i}{d}$ ，其中 $d=\binom{n}{2}$

令第二部分贡献的随机变量为 $Z$ ，每个友谊组合的贡献的随机变量为同分布 $Y_i$ ，则 $Z=Y_1 Y_2 ... Y_m$ ，这步是问题核心。

令每个友谊组合被选中的次数为 $X_i$ ，因为选中 $x$ 次就会产生 $\sum _{i=0}^{x-1}i$ 的贡献，有 $Y_i=\frac{X_i(X_i-1)}{2}$ ，又 $X_i \sim B(k,\frac{1}{d})$ ，因此 $E(Y)=\sum _{x=1}^{k}\frac{x(x-1)}{2}\cdot P(x)$ ，其中 $P(x)=\binom{k}{x}(\frac{1}{d})^x(1-\frac{1}{d})^{k-x}$

最终 $E(Z)=m\cdot E(Y)$

int n,m,k; 
int a[100005],b[100005],f[100005];
const ll mod=1e9+7;
inline ll qpow(ll x,ll n){ll res=1;for(;n;(n&1)&&(res=res*x%mod),x=x*x%mod,n>>=1);return res;}
ll jc[200005],jcinv[200005],dpx[200005],mdpx[200005];
const int MAXK=2e5;
inline ll C(ll n,ll m){return jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;}
int main(){
	jc[0]=jc[1]=1;
	for(int i=2;i<=MAXK;i++)
		jc[i]=jc[i-1]*i%mod;
	jcinv[MAXK]=qpow(jc[MAXK],mod-2);
	for(int i=MAXK-1;i>=0;i--)
		jcinv[i]=jcinv[i+1]*(i+1)%mod;
	int t;
	R(t);
	while(t--){
		R(n);R(m);R(k);
		ll ans1=0,ans2=0;
		for(int i=1;i<=m;i++){
			R(a[i]);R(b[i]);R(f[i]);
			ans1=(ans1+f[i])%mod;
		}
		ll d=1ll*n*(n-1)/2%mod;
		ans1=qpow(d,mod-2)*ans1%mod*k%mod;
		dpx[0]=mdpx[0]=1;
		dpx[1]=qpow(d,mod-2);
		mdpx[1]=(d-1)*qpow(d,mod-2)%mod;
		for(int i=2;i<=k;i++){
			dpx[i]=dpx[i-1]*dpx[1]%mod;
			mdpx[i]=mdpx[i-1]*mdpx[1]%mod;
		}
		ll cnt;
		for(int x=1;x<=k;x++){
			cnt=1ll*x*(x-1)/2%mod;
			ans2=(ans2+cnt*C(k,x)%mod*dpx[x]%mod*mdpx[k-x]%mod)%mod;
		}
		printf("%lld\n",(ans1+ans2*m%mod)%mod);
	}return 0;
}

题解 | I - 双人登山

I - 双人登山 - Solution