[bzoj2839]集合计数

这是道权限题
题目大意:
一个有N个元素的集合有2^N个不同子集(包含空集),现在要在这2^N个集合中取出若干集合(至少一个),使得它们的交集的元素个数为K,求取法的方案数,答案模1000000007。
k<=n<=1000000

首先不妨将这取的k个数放到最前面,考虑后面n-k个数的交为空的方案数。
我们可以直接使用容斥来做,枚举交的集合大小,然后拿组合数和算一算即可。
注意要将n=k的情况特判掉

Tagged with:

发表评论