『题解』BZOJ2839 集合计数|天天热点评

2023-06-15 10:56:40 来源：博客园

西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内西内呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！！

烦死了

题面

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

(资料图片仅供参考)

这不就一眼丁真容斥原理么

容斥原理是什么, 不就是一个的减去两个的加上三个的减去四个的加上五个的... 以此类推一直到边界么.

类似地, 对于这个题来说, 我们设交集的元素个数 $\ge k$ 的方案数为 $g_k$ , 答案显然就是:

\[\sum_{i=k}^{n}(-1)^{i-k} \times g_i\]

但是, 这是错误的.当然也只有这个式子是错误的.不是, 并不是错误的, 而是不完整的,$g_i$ 具体是什么我们还不清楚, 所以我们要赋予 $g_i$ 一个含义.

这里 $i$ 和 $k$ 有点混了, 但是它们都是一个东西, 都是 $g_{某个字母}$ 代表的含义.

为什么呢? 因为虽然是交集元素个数 $\ge k$ , 但是我们不知道具体是哪 $k$ 个. 所以 $g_k$ 中一定有因子 $\mathrm{C}_n^k$ , 就是在这 $n$ 个数中任意选出 $k$ 个数来作为交集中一定存在的 $k$ 个元素.但是这还没完, 我们还剩下 $n-k$ 个数, 我们可以让这 $n-k$ 个数构成 $2^{n-k}$ 个集合(包括空集), 把交集中一定存在的 $k$ 个元素加到这 $2^{n-k}$ 个集合的每一个里(这 $2^{n-k}$ 个集合里有一个空集, 加到空集里没有用, 根据题意, 显然不可以两个相同的集合取交), 变成新的 $2^{n-k}$ 个集合.那么这 $2^{n-k}$ 个集合, 无论选多少集合取交集, 交集中一定有之前选出来的 $k$ 个数. 但是这个交集也有可能有这 $k$ 个数以外的数, 所以是交集的元素个数 $\ge k$ 的方案数. 所以我们把这 $2^{n-k}$ 个集合看作 $2^{n-k}$ 个元素, 并让这 $2^{n-k}$ 个元素组成新的集合, 显然可以组成 $2^{2^{n-k}}$ 个新的集合(显然新的集合的含义就是每一种取交集的情况). 但是前文已说过不能存在空集并上一定存在那 $k$ 个数的交集得到的新的集合, 所以可以组成 $2^{2^{n-k}}-1$ 个集合.

因为我们刚才论证的结果是在交集中 $k$ 个数确定的情况下论证的, 所以交集的元素个数 $\ge k$ 的方案数$g_k = \mathrm{C}_n^k \times (2^{2^{n-k}} - 1)$ .

然而这个题才刚刚开始

有一个东西叫做二项式反演, 在这里不作主要介绍.这个题用到的二项式反演的基本形式就是:

\[g_k = \sum_{i = k}^{n} \times \mathrm{C}_i^k \times f_i \Leftrightarrow f_k = \sum_{i = k}^{n} \times (-1)^{i - k} \times \mathrm{C}_i^k \times g_i \]

其中 $g_k$ 和上文含义一样, $f_k$ 含义为交集元素个数恰好为 $k$ 的情况.证明这里就省略了. 思路很无脑, 就是把右面的式子带入到左面, 再用一个组合数的性质 $\mathrm{C}_n^r \times \mathrm{C}_r^k = \mathrm{C}_n^k \times \mathrm{C}_{n-k}^{r-k}$ 就可以证明. 啊不对, 还得用一次二项式定理.

根据题意, 我们要求的答案便是 $f_k$ . 我们将 $g_i$ 代换, 因为 $g_i = \mathrm{C}_n^i \times (2^{2^{n-i}} - 1)$ , 所以最后的结果是:

\[f_k = (\sum_{i = k}^{n} \times (-1)^{i - k} \times \mathrm{C}_i^k \times \mathrm{C}_n^i \times (2^{2^{n-i}} - 1)) \% (1\mathrm{e}9+7)\]

利用上面说的组合数的那个性质, 也可以写成:

\[f_k = (\sum_{i = k}^{n} \times (-1)^{i - k} \times \mathrm{C}_n^k \times \mathrm{C}_{n-k}^{i-k} \times (2^{2^{n-i}} - 1)) \% (1\mathrm{e}9+7)\]

把 $\mathrm{C}_n^k $ 提出来:

\[f_k = \mathrm{C}_n^k \times (\sum_{i = k}^{n} \times (-1)^{i - k} \times \mathrm{C}_{n-k}^{i-k} \times (2^{2^{n-i}} - 1)) \% (1\mathrm{e}9+7)\]

因为在计算的时候要枚举 $i$ , 这么写可以省去其中一项的 $i$ , 避免冗余计算.

到这里, 式子就推完了.

如何计算

枚举每一个 $i$ , 算出每一个 $i$ 下的结果, 累加并取模即可.

对于 $(-1)^{i - k}$ , 维护 $i-k$ 的奇偶性即可.

对于组合数, 因为 $n \leq 1\mathrm{e}6$ , 所以直接对阶乘以及$\%1\mathrm{e}9 + 7$ 意义下的逆元打表求解即可.

对于 $2^{2^{n-i}} - 1$ , 需要用到欧拉定理 $a^{\varphi(p)} \equiv 1 (\mod p), \gcd(a, p) = 1$ .因为我们最后对 $1\mathrm{e}9 + 7$ 取模(显然 $1\mathrm{e}9 + 7$ 是个素数), 所以 $(2^{2^{n-i}} - 1) \% (1\mathrm{e}9 + 7) = (2^{2^{n-i}} \% (1\mathrm{e}9 + 7) - 1) \% (1\mathrm{e}9 + 7)$ .将欧拉定理变形为 $a^{\varphi(p)} \% p = 1 \% p = 1, p \neq 1$ , 类似地, 对于 $2^{2^{n-i}} \% (1\mathrm{e}9 + 7)$ 可变形为 $2^{2^{n-i} \% \varphi(1\mathrm{e}9 + 7)} \% (1\mathrm{e}9 + 7)$ , 其中 $\varphi(1\mathrm{e}9 + 7) = 1\mathrm{e}9 + 6$ .对于 $2^{n-i}$ , 我们可以打表计算 $2^{某个整数}$ .

如果不能保证转义都正确, 建议都开 $long\ long$ .

完结撒代码

#include #define LL long longusing namespace std;const LL maxn(1e6 + 5), MOD(1e9 + 7);LL n, k, f[maxn], g[maxn], Pow2[maxn], ans, flag;LL QuickPow(LL a, LL b, LL p) {    LL res(1);    for (; b; b >>= 1) {        if (b & 1) res = res * a % p;        a = a * a % p;    }    return res;}void Init(LL p) {    f[0] = g[0] = Pow2[0] = 1;    for (int i = 1; i <= n; ++i) {        f[i] = f[i - 1] * i % p;        g[i] = QuickPow(f[i], p - 2, p) % p;        Pow2[i] = (Pow2[i - 1] << 1) % (p - 1);    }}LL getC(LL n, LL m, LL p) {    if (n < m) return 0;    if (n == m || m == 0) return 1;    return f[n] * g[m] % p * g[n - m] % p;}int main() {    cin >> n >> k;    Init(MOD);    for (int i = k; i <= n; ++i) {        if ((i - k) & 1) ans = ans - getC(n - k, i - k, MOD) % MOD * (QuickPow(2, Pow2[n - i], MOD) - 1) % MOD;        else ans = ans + getC(n - k, i - k, MOD) % MOD * (QuickPow(2, Pow2[n - i], MOD) - 1) % MOD;        ans = (ans % MOD + MOD) % MOD;    }    ans = ans * getC(n, k, MOD) % MOD;    cout << ans << "\n";}

如有错误, 疑问或不同见解, 欢迎评论区留言.

关键词：