题解：P10596 BZOJ2839 集合计数

我们令

f_k

表示的交集的元素个数恰好为

k

，令

g_k

表示的交集的元素个数至少为

k

。根据二项式反演可得：

f_k = \sum_{i=k}^{n}\left (-1 \right )^{i-k}\binom{i}{k}g_i

下面考虑如何求

g_k

。

我们先钦定其中的

k

个元素为交集的元素，则方案数为

\binom{n}{k}

，这表示在选出的集合中这

k

个元素一定选，这些钦定的集合还有

n-k

个元素可以选，枚举这

n-k

个元素选或不选共有

2^{n-k}

种方案，由于不能不选，所以

g_k = \binom{n}{k} ( 2^{2^{n-k}}-1)

。最终答案为

f_k

。

参考代码

CPP

#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7,N=1e6+5;
using namespace std;
int n,k,fac[N],inv[N];
int c(int a,int b){return fac[a]*inv[b]%mod*inv[a-b]%mod;}
int qpow(int a,int b,int p){
	int res=1;
	while(b){
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1; 
	}
	return res;
}
int f[N],g[N];
signed main(){
	scanf("%lld%lld",&n,&k);
	fac[0]=1;
	for(int i = 1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	inv[n]=qpow(fac[n],mod-2,mod);
	for(int i = n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	for(int i = 0;i<=n;i++)
	f[i]=c(n,i)*(qpow(2,qpow(2,n-i,mod-1),mod)-1)%mod;
	for(int i = k;i<=n;i++){
		int x;
		if((i-k)%2==1) x=-1;
		else x=1;
		int tmp=c(i,k)*f[i]%mod;
		tmp*=x; 
		g[k]=(g[k]+tmp+mod)%mod;
	}
	printf("%lld",g[k]);
}

题解：P10596 BZOJ2839 集合计数

文章操作

参考代码

相关推荐

评论

题解：P10596 BZOJ2839 集合计数