题目描述
一个有N个元素的集合有 2^N 个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）
输入格式
一行两个整数N, K
输出格式
一行为答案。
样例
样例输入
3 2
样例输出
6
样例说明
假设原集合为{A,B,C}
则满足条件的方案为：{ {AB}, {ABC} }, { {AC}, {ABC} }, { {BC}, {ABC} }, {AB}, {AC}, {BC}
数据说明
对于100%的数据，1≤N≤1000000；0≤K≤N；
题解
对于这道题，根据样例说明，很容易发现最后求的方案是“由集合构成的集合”，这就要求我们不能将单个元素看成一个数，而应该是由多个不同的数构成的集合（其中，不同的数的个数要大于等于k）；
不妨设“不同的数的个数”为x；
但由于我们并不知道x的大小，只知道x的范围（k~n），再看一眼数据范围，可以枚举；
枚举过程中，相当于x已经确定，我们只需找这x个数构成的所有集合中，至少有k个数的集合与剩下没有处理的数的全集的交集元素个数正好为k的情况；
- 对于 这x个数构成的所有集合中，至少有k个数的集合 这个东西，我们需要从n个数里面选i个，再从i个数里面选k个与后面去取交集；
公式为：
\[C(n, i) * C(i, k)
\]
- 对于 剩下没有处理的数的全集的交集 这个东西，根据题目中一个有N个元素的集合有 2^N 个不同子集（包含空集）这个定理，很容易得出公式；
公式为：
\[2^{2^{n - i}} - 1
\]
有空集，所以-1；
但是可能会出现前面选了 {A, B}, 后面选{B, C}，反过来后面选了 {A, B}, 前面选{B, C} 的情况，所以这时候要用容斥原理（不再解释）；
如果用Venn图表示的话，最后整个的面积就是答案；
最后公式：
\[\sum^{i}_{k - n}C(n, i) * C(i, k) * (2^{2^{n - i}} - 1) * (-1)^{i - k}
\]
代码
#include <iostream>
using namespace std;
const long long mod = 1000000007;
long long n, k;
long long fc[1000005];
long long po[1000005];
long long qpow(long long a, long long b) {long long ans = 1;while(b) {if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}
inline long long inv(long long a, long long b) {return qpow(a, b - 2);
}
inline long long C(long long n, long long m) {return n < m ? 0 : fc[n] * inv(fc[m], mod) % mod * inv(fc[n - m], mod) % mod;
}
inline long long lucas(long long n, long long m) {if (m == 0) return 1;return C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
}
int main() {cin >> n >> k;fc[0] = 1;for (int i = 1; i <= n; i++) {fc[i] = i * fc[i - 1] % mod;}po[0] = 2;po[1] = 4;for (int i = 2; i <= n; i++) {po[i] = po[i - 1] * po[i - 1] % mod; //预处理出2^2^(n - i);}long long ans = 0;for (int i = k; i <= n; i++) {if ((i - k) % 2) {ans = (ans % mod - lucas(i, k) * lucas(n, i) % mod * (po[n - i] - 1) % mod + mod) % mod;} else {ans = (ans % mod + lucas(i, k) * lucas(n, i) % mod * (po[n - i] - 1) % mod) % mod;}}cout << ans;return 0;
}
