P12992 题解

从大到小加边，做一个转化，

k

个连通块相当于有

k

条边在加进来的时候两个点都没有任何连边。

考虑容斥，选定

i

条边加进来的时候两个点都没有任何连边，容斥及系数（选定

i

条边的方案数，注意不能有重复点）是平凡的，考虑如何计算确定这

i

条边后的概率。

首先给这

i

条边按大小定序。不妨把每条边视作一个点，选定的偏序关系视为有向边。于是我们将问题转化为了有向树拓扑序数量，套用经典结论概率即为

\prod\frac1{siz_j}

。不难发现只有

i

个子树大小不为

1

（即选定的

i

条边对应点的子树）。更进一步，我们会发现选定

i

对应的概率可以从

i-1

直接推，因此可以预处理出来做到

O(1)

计算。

总复杂度

O(TM)

。

CPP

#include <bits/stdc++.h>
#define int long long
#define lowbit(i) (i&(-i))
using namespace std;
const int mod=1e9+7;
int qp(int a,int b){
	a%=mod;
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		(a*=a)%=mod;
		b>>=1; 
	}
	return ans;
}
int fac[1000005],inv[1000005],invp[1000005],ipw[1000005];
void init(){
	ipw[0]=1; for(int i=1;i<=1000000;i++) ipw[i]=ipw[i-1]*((mod+1)>>1)%mod;
	fac[0]=1; for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=qp(fac[1000000],mod-2); for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	for(int i=1;i<=1000000;i++) invp[i]=fac[i-1]*inv[i]%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return fac[i]*inv[j]%mod*inv[i-j]%mod;
}
int f[1000005];
void solve(int tc){
	int n,k; cin>>n>>k;
	f[0]=1;
	for(int i=1;(i<<1)<=n;i++) f[i]=f[i-1]*qp((i<<1)*(n-(i<<1))+i*((i<<1)-1),mod-2)%mod;
	int ans=0;
	for(int i=k;(i<<1)<=n;i++){
		if((i-k)&1) (ans+=mod-f[i]*C(i,k)%mod*fac[n]%mod*ipw[i]%mod*inv[n-(i<<1)]%mod)%=mod;
		else (ans+=f[i]*C(i,k)%mod*fac[n]%mod*ipw[i]%mod*inv[n-(i<<1)]%mod)%=mod;
	}
	cout<<"Case #"<<tc<<": "<<ans<<"\n";
}
signed main(){
	init();
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t; cin>>t;
	for(int i=1;i<=t;i++) solve(i);
	return 0;
}

文章操作

相关推荐

评论

P12992 题解