返回首页 返回专题

【BZOJ2839】集合计数 题解

题意

一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模10^9+7

题解

首先假设最多只能取两个集合

定住其中一个集合，并使得它恰好有k个元素，那么另一个集合可以在这个集合的基础上任意添加一些其它的数（或不添加），那么另一个集合的取法方案数就是2^(n-k)。定住的这一个集合则可以有C(n,k)中取法方案

接着假设定住的集合有k+1个元素，那么另一个集合需要在定住的集合中选取k个元素，再在其它元素中任取一些，它的取法方案数就是C(k+1,k)*2^(n-k-1)，定住的集合有C(n,k+1)种取法

那么假设定住的集合有k+i个元素，它的取法方案数就是C(n,k+i)C(k+i,k)2^(n-k-i)

现在我们要取若干个集合

其实很简单，我们把所有“另一个集合”的可能取法看作一个集合，这个集合的元素个数就是“另一个集合”的取法数量，假设“定住的集合”有k+i个元素，它的元素数量就是2^(n-k-1)，在其中任取一些元素，取法总数就是2^2^(n-k-1)

那么再根据容斥原理，得到最终答案：

#include<bits/stdc++.h>
#define Mod 1000000007
using namespace std;

const int N=1000000;
int fac[N+10],ifac[N+10];

int Pow(int a,int b,int p)
{
	int ans=1;
	for(;b;a=1ll*a*a%p,b>>=1)
		if(b&1) ans=1ll*ans*a%p;
	return ans;
}

void Init()
{
	fac[0]=ifac[0]=1;
	for(int i=1;i<=N;i++)
		fac[i]=1ll*fac[i-1]*i%Mod;
	ifac[N]=Pow(fac[N],Mod-2,Mod);
	for(int i=N-1;i>=1;i--)
		ifac[i]=1ll*ifac[i+1]*(i+1)%Mod;
}

int C(int n,int k){return 1ll*fac[n]*ifac[k]%Mod*ifac[n-k]%Mod;}

int main()
{
	Init();
	int n,k,fg,tmp=2,ans=0;
	cin>>n>>k;
	for(int i=n-k;i>=0;i--)
	{
		fg=(i&1)?-1:1;
		ans=(ans+1ll*fg*C(n,k+i)*C(k+i,k)%Mod*tmp%Mod)%Mod;
		tmp=1ll*tmp*tmp%Mod;
	}
	cout<<(ans+Mod)%Mod<<endl;
	return 0;
}