BZOJ2839 集合计数 容斥

题目描述(权限题qwq)

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

输入格式

一行两个整数N,K

输出格式

一行为答案

样例输入:

3 2

样例输出:

6

因为集合中的元素是无序的,所以我们随便选(k)个作为交集,最后把答案乘上(egin{pmatrix}n\ kend{pmatrix})就好了。选出来(k)个之后,问题转化为在(n-k)个元素中选若干个集合,使它们的交集为空集。没有交集为空集的限制条件的话答案为(2^{2^{n-k}})(可以这么理解:先选出来一些集合,再决定哪个集合选不选)。直接求不好求,考虑容斥,答案即为(sumlimits_{i=0}^{n-k}(-1)^iegin{pmatrix}n-k\ iend{pmatrix}2^{2^{n-k-i}})。预处理(2^{2^{p}})需要一些技巧,就是(2^{2^{p+1}}=(2^{2^{p}})^2)
代码的坑找个时间再填...

原文地址:https://www.cnblogs.com/dummyummy/p/9981679.html