BZOJ 2839 集合计数

发表于 | 更新于

Link

发现自己对容斥的理解还处于小学的水平，补点题找找感觉

Solution

首先这是求交集，被我当成并集想了大半天2333 求交集的话，那肯定是选kk个当交集，选出所有的集合剩下部分的交集为∅\emptyset 设f(n,i)f(n,i)表示从nn个元素的集合中选出交集至少有ii个元素的子集的方案数，考虑容斥 那么最后的答案就是 Cnk(∑i=0n−k(−1)if(n−k,i))C_n^k(\sum\limits_{i=0}^{n-k}(-1)^{i}f(n-k,i)) 应该是比较好懂的。。 又显然f(n,k)=Cn−ki(22n−k−1)f(n,k)=C_{n-k}^i(2^{2^{n-k}}-1)，−1-1是因为必须选至少一个

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "lucida"

const int P=1000000007,MAXN=1000000+11;
int64 fac[MAXN],ifac[MAXN];
struct _{_(){
	ifac[1]=1;
	for(int i=2;i<MAXN;++i)
		ifac[i]=(P-P/i)*ifac[P%i]%P;
	fac[0]=ifac[0]=1;
	for(int i=1;i<MAXN;++i) {
		fac[i]=fac[i-1]*i%P;
		(ifac[i]*=ifac[i-1])%=P;	
	}
}}Prep;
int64 C(int n,int m) {
	return n>=m?fac[n]*ifac[m]%P*ifac[n-m]%P:0;
}
int64 Null(int n) {
	int64 res=0,p2p=2;
	for(int i=n;~i;--i,(p2p*=p2p)%=P)//n-1开始枚举的
		(res+=C(n,i)*(i&1?-1:1)*(p2p-1)%P)%=P;//外层没%
	return res;
}
int main() {
	freopen("input","r",stdin);
	int n,K;is>>n>>K;
	int64 Ans=Null(n-K)*C(n,K)%P;
	(Ans+=P)%=P;
	os<<Ans<<'\n';
	return 0;
}