[BZOJ2839]:集合计数

题目传送门


题目描述:

一个有N个元素的集合有2N个不同子集(包含空集),现在要在这2N个集合中取出若干集合(至少一个),使得它们的交集的元素个数为K,求取法的方案数,答案模1000000007。(是质数喔~)


输入格式:

一行两个整数N,K。


输出格式:

一行为答案。


样例:

样例输入:

3 2

样例输出:

6


样例说明:

假设原集合为{A,B,C}

则满足条件的方案为:{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}


 

数据范围与提示:

对于100%的数据,1≤N≤16;0≤K≤N;


题解:

我也不知道为什么看到这道题就像到了组合数学和容斥,别问我为什么。

好叭~既然你这么可爱……那就……

其实,我感觉叭……这种什么什么集合的题,要是你一秒想不出来什么算法,就往容斥去想吧,个人感觉基本上就是容斥了。

反正是容斥你就赚了,不是你也不亏(反正你也不会,不不不,您是最神的)。

言归正转(其实刚才也不是废话叭~):

首先是组合数学,既然自己很执着就往组合数学上去想吧。

显然,问题可以转化为先在n个数里选k个,然后在剩下的数中选出任意多个集合,使他们的交集为空集即可。

这时候答案即为:ans=(一堆数,我也不知道有多大)×C(n,k)。

然后“我也不知道有多大”的数看样子很难求,它们会组成2(n-k)个集合,然后你还要从这些集合当中去选,让它们没有交集,那我估计你有钱的话可以让它先跑着,自己冷冻个几百年没准它能算完?不好说~

那么显然不能这样,怎么办?

我说了还有容斥。

那么我们考虑让它们的交集为i(i=[k,n],i∈N*)。

从这n个元素中选出i个元素,剩下的n-i个元素可以组成2(n-i)个不同的集合,然后这些集合还有2(2^(n-i))-1种组合,-1是因为我们不能什么也不选。

方案数即为C(n,i)×C(i,k)×(2(2^(n-i))-1)。

这时候就要考虑我们伟大的容斥了,奇加偶减即可。


 

代码时刻:

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long ans;
long long jc[1000005],inv[1000005];
long long qpow(long long x,long long y,long long mod)//快速幂
{
	long long ans=1;
	while(y)
	{
		if(y%2)ans=(ans*x)%mod;
		y>>=1;
		x=(x*x)%mod;
	}
	return ans;
}
void pre_work()//预处理
{
	jc[0]=1;
	for(long long i=1;i<=1000000;i++)
		jc[i]=(jc[i-1]*i)%1000000007;
	inv[1000000]=qpow(jc[1000000],1000000005,1000000007);
	for(long long i=999999;i>=0;i--)
		inv[i]=(inv[i+1]*(i+1))%1000000007;
 }
long long cm(long long n,long long m){return jc[n]*inv[m]%1000000007*inv[n-m]%1000000007;}//求C
int main()
{
	pre_work();
	scanf("%lld%lld",&n,&k);
	int flag=1;//用来奇加偶减
	for(long long i=k;i<=n;i++)
	{
		ans=(ans+(((cm(n,i)*cm(i,k))%1000000007*(qpow(2,qpow(2,n-i,1000000006),1000000007)-1))%1000000007)*flag%1000000007)%1000000007;//式子,注意容斥
		flag=-flag;
	}
	cout<<(ans+1000000007)%1000000007;//因为最后一步可能是一个减,所以注意要+mod再%mod
	return 0;
}

 

rp++

上一篇:7.24 杭电多校第二场小结(3/12)


下一篇:[CF1111D]Destroy the Colony