题目大意：一个有 \(N\) 个元素的集合有 \(2^N\) 个不同子集（包含空集），现在要在这 \(2^N\) 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 \(K\)，求取法的方案数，答案模 \(10^9+7\)。
为表述方便，不妨设这 \(i\) 个元素分别为 \(1\sim n\)。
前置知识：二项式反演。
考虑设 \(g(x)\) 为我们选择恰好 \(x\) 个数，要求选出若干个集合他们的交集里是这 \(x\) 个数的方案数，这个东西由于是“恰好”不好计数，考虑设 \(f(x)\) 表示说我们钦定 \(x\) 个数他一定要在这若干个集合的交集中的方案数。
\(f(x)\) 是好求的，我们直接从集合中钦定 \(x\) 个数一定要在若干个集合的交集中（其他数在不在我不关心），然后考虑包含这 \(x\) 个数的集合数量，显然除了这 \(x\) 个数必选以外，其余的数可选可不选，所以这部分的数量是 \(2^{n-x}\) 的。然后对于这些包含这 \(x\) 个数的集合，对于每个集合来说我们也是可选可不选，所以最终这部分的答案是 \({n\choose x}\times(2^{2^{n-x}}-1)\)，这部分的 \(-1\) 是因为要排除掉空集。
接下来考虑如果 我们已知 \(g\)，如何用 \(g\) 表示出 \(f\)（以方便我们用二项式反演从 \(f\) 反推回 \(g\)），显然\(f(x)=\sum_{i=x}^ng(i)\times{n\choose i}\)，代表说我们对于每一个 \(i\ge x\)，我们恰好选 \(i\) 个数的方案数之和就是钦定 \(x\) 个数的方案数。然后对这个式子用一下二项式反演：
\[f(x)=\sum_{i=x}^n{n\choose i}\times g(i)\Leftrightarrow g(x)=\sum_{i=x}^n(-1)^i\times{n\choose i}\times{i\choose x}\times(2^{2^{n-i}}-1) \]最后用一遍扩展欧拉定理就做完了，时间复杂度 \(O(n\log n)\)，如果预处理 \(2^{2^i}\) 可以做到 \(O(n)\)。
const int MAXN = 1e6 + 5, mod = 1e9 + 7;
int n, k, fac[MAXN], ifac[MAXN];
int quickpow(int a, int b, int p = mod) {
int ret = 1;
while (b) {
if (b & 1) ret = ret * a % p;
a = a * a % p; b >>= 1;
}
return ret;
}
int C(int n, int m) {
if (n < m) return 0;
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
void work() {
cin >> n >> k;
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
ifac[n] = quickpow(fac[n], mod - 2);
for (int i = n; i; i--) ifac[i - 1] = ifac[i] * i % mod;
int ans = 0, coff = 1;
for (int i = k; i <= n; ++i) {
ans = ans + coff * C(i, k) * C(n, i) % mod * quickpow(2, quickpow(2, n - i, mod - 1)) % mod;
ans = (ans % mod + mod) % mod;
coff = -coff;
}
cout << ans << endl;
}