洛谷P10596 & BZOJ2839 集合计数题解

题意：

一个有 \(N\) 个元素的集合有 \(2^N\) 个不同子集（包含空集）

现在要在这 \(2^N\) 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 \(K\)

求取法的方案数，答案模 \(10^9+7\)。

输入格式：

一行两个整数 \(N,K\)。

输出格式：

一行一个整数表示答案。

数据范围：

\(1\leq N\leq 10^6,~0\leq K\leq N\)。

先选出 \(k\) 个元素为交集，然后在剩下的 \(2^{n-k}\) 个集合里选 \(i\) 个和它并上

于是列出一个感觉也不太对的式子 \[ \binom{n}{k}\sum_{i=1}^{2^{n-k}}\binom{2^{n-k}}{i} = \binom{n}{k} \left(2^{2^{n-k}}-1\right) \] 由于我们选的集合不能有交集，所以上面这个东西多算了有交集的情况。

看上去直接算也不好算，考虑容斥。那么钦定后选的集合交集至少为 \(i\) ，有 \[ \mathrm{Ans} = \binom{n}{k}\sum_{i=0}^{n-k}(-1)^i\binom{n-k}{i}\left(2^{2^{n-k-i}}-1\right) \] 可以理解为，比如 \(i=1\) 时，每个集合就是确定 \(a_i\) 一定有，其他不一定时的各种情况。

upd. 实际上这道题利用二项式反演会更简单一些。

设 \(f_i\) 为钦定集合的交集为 \(i\) 的方案数，设 \(g_i\) 为集合的交集恰好为 \(i\) 的方案数，那么 \[ \begin{aligned} f_k &=\binom{n}{k} \left(2^{2^{n-k}}-1\right) \\[6pt] &=\sum_{i=k}^n\binom{i}{k} g_i \end{aligned} \] 那么根据二项式反演可知 \[ \begin{aligned} g_k&=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k} f_i \\[6pt]&=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}\binom{n}{i}\left(2^{2^{n-i}}-1\right) \end{aligned} \] 这种做法的实现可以参考这篇文章。

另外后面这个可以记 \(f_i = 2^{2^i}-1\) ，因为 \(2^{2^{n-k}}= (2^{2^{n-k-1}})^2\) ，所以 \[ f_{i} = (f_{i-1}+1)^2-1 = f_{i-1}^2+2f_{i-1} \] 边界 \(f_0 = 1\) 。那么只需要倒着递推就好啦。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

int fac[N], infac[N];
int qpow(int a, int b)
{
    int r = 1;
    for(a %= mod; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
int C(int n, int m)
{
    if(n < m || m < 0) return 1;
    return fac[n] * infac[m] % mod * infac[n - m] % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, k; cin >> n >> k; fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    infac[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; ~i; i--) infac[i] = infac[i + 1] * (i + 1) % mod;
    int res = 0, dp = 1, tmp = C(n, k), sgn = ((n -= k) & 1) ? -1 : 1;
    for(int i = n; ~i; i--)
    {
        res = (res + sgn * C(n, i) * dp % mod) % mod;
        dp = (dp * dp % mod + 2 * dp % mod) % mod; sgn = -sgn;
    }
    cout << (mod + res * tmp % mod) % mod << '\n';
    return 0;
}