跳转至

容斥原理

容斥原理ψ(｀∇´)ψ

概述ψ(｀∇´)ψ

若有 \(n\) 个集合 \(S_1 \dots S_n\)，并且集合之间可能有交集。

那么 \(|\bigcup S_i|\) 就等于 \(\sum_i |S_i| - \sum_{i, j} |S_i \cap S_j| + \sum_{i, j, k} |S_i \cap S_j \cap S_k| \dots + (-1)^{n + 1} \sum_{a_1, \dots a_n} |\bigcap_j S_{a_j}|\)。

\(a_1, \dots a_n\) 是用来枚举集合的。

这个柿子也可以简述为，多个集合的并集大小等于奇数个集合的交集的大小之和减去偶数个集合的交集大小之和。

或者描述为:

\(\sum\) 在任意一个集合内的元素个数总和 \(−\sum\) 在任意两个集合交内的元素个数总和 \(+\sum\) 在任意三个集合交内的元素个数总和...

注意这里“在任意两个集合交集内的元素个数总和”是要算重的，也就是说如果 \(x\) 在 \(A\cap B \cap C\) 当中，那么在算任意两个集合交内的元素个数总和时，\(x\) 的贡献就是 \(3\)。

这么做其实就是为了方便计数，因为有多个条件但是只是“至少”满足一个或者几个的时候，无法比较方便的知道哪些条件满足，哪些条件不满足。

所以我们直接只考虑某些特定的条件一定被满足的时候方案数，其它的直接不管怎么搞，反正不合法或者重复的肯定会被容斥掉。

这就是一种“至少转强制”的思想。

一些应用ψ(｀∇´)ψ

假设有 \(n\) 个条件组成了一个条件集合 \(S\)，且这些限制建立在一个元素集合 \(U\) 上，我们想要知道至少满足一个条件的元素有多少个，此时可以使用容斥原理。

我们将 \(U\) 作为全集，设 \(s_i\) 表示满足第 \(i\) 个条件的所有元素构成的集合。

答案显然是求 \(|\bigcup s_i|\) 那么根据容斥原理可以有：

\(ans = \sum_i |s_i| - \sum_{i, j} |s_i \cap s_j| + \sum_{i, j, k} |s_i \cap s_j \cap s_k| \dots + (-1)^{n + 1} \sum_{a_1, \dots a_n} |\bigcap_j s_{a_j}|\)

这个柿子也可以写成一个更方便的形式，我们令 \(p\) 表示 \(S\) 的一个子集，即由若干个条件组成的条件集合，设 \(f(p)\) 表示满足 \(p\) 中所有条件的元素个数，即 \(|\bigcap\limits_{s\subseteq p} s|\)。

那么 \(ans = \sum\limits_{p\subseteq S, p \not= \emptyset} (-1)^{|p|+1} f(p)\)。

（这里空集一般来说枚举不枚举都没有啥问题，因为大多数时候 \(f(\emptyset) = 0\)，如果遇到特殊定义的再看情况就好，为了通用所以排除了空集。）

然后求不满足任意条件的元素就直接 \(|U| - ans\) 即可。

例题ψ(｀∇´)ψ

不定方程非负整数解计数ψ(｀∇´)ψ

给定若干个非负整数 \(x_i\)，保证 \(\sum\limits_{i = 1}^n x_i = m\)，求出合法的解的数量，\(m \in \mathbb{N}\)。

这个东西比较简单，我们放 \(m\) 个无差别的小球，然后考虑将其分成 \(n\) 组（\(1\ 1\ 2\) 和 \(1\ 2\ 1\) 不是相同的分法），对合法的分组计数即可。

这个就是插板法，直接用公式就可以了。

如果对于每一个 \(x_i\) 有一个限制：\(x_i \le b_i\)，求出合法解的数量，\(b_i \in \mathbb{N}\)。

这个限制一看长的就像容斥原理里面“满足某一个条件的元素”，这里在对满足所有限制的合法解做计数，所以考虑容斥。

抽象一下 model：

  • 集合 \(s\)：设 \(s_i\) 表示满足第 \(i\) 个条件的所有合法解组成的集合。
  • 全集 \(U\)：所有合法解。
  • 答案 \(ans\)：\(|\bigcup s_i|\)。

写出柿子：\(ans = |\bigcup s_i| = \sum\limits_{p \subseteq S,p\not= \emptyset} (-1)^{|p| + 1} f(p)\)

于是接下来我们要考虑的就只有怎么计算 \(f(p)\)，考虑任意一个 \(S\) 的非空子集 \(p\)，假设它由 \(q\) 个条件 \(x(a_i) \le b(a_i)\) 组成（\(a_i\) 用于枚举下标）。

嗯，然后发现这个东西很不好算，我们并没有什么头绪，最根本的原因在于这个 \(x_i \le b_i\) 的条件是难以计算的。

我们想到，在插板法的几个基本问题里，有一个问题是：“第 \(i\) 组的元素至少要有 \(v_i\) 个”，转化成不定方程的形式就是 \(x_i \ge v_i\)，这个东西是容易计数的。

于是我们考虑 “正难则反” 的思想，计算不满足 \(x_i \le b_i\) 的合法解个数，也就是考虑计算 \(x_i \ge (b_i + 1)\) 的合法解个数，然后用全集 \(U\) 的大小减去这个即可（求补集）。

那么对于任意一个 \(p\) 的答案就是 \(\dbinom{n + \sum\limits_{i = 1}^q (b(a_i) + 1) - 1}{n}\)

所以最终的答案是 \(\dbinom{n + m - 1}{n} - \sum\limits_{p \subseteq S,p\not= \emptyset} (-1)^{|p| + 1} \dbinom{n + \sum\limits_{i = 1}^q (b(a_i) + 1) - 1}{n}\)

CF997C Sky Full of Starsψ(｀∇´)ψ

现在有一个 \(n \times n\) 的网格，你有 RGB 三种颜色，你需要给每一个格子染色。

请问至少有一行或者一列颜色相同的方案数有多少？求出这个数对 \(998244353\) 取模的值。

\(n \le 1e6\)。

这个问题是比较经典的“用钦定来容掉至少方便计数”的问题。

模型应该比较好看出来，我们把有一行或者一列颜色相同看作 \(2n\) 个条件就行。

于是模型抽象出来：

  1. 全集 U ：所有可能的染色方式，方案数是 \(3^{n\times n}\)。
  2. 元素 ：染色方式。
  3. 属性：（更好的理解是“一种限制/条件”）一行或者一列涂的颜色完全相同。

发现属性本质上就是 \(2n\) 个限制，也就是第 \(i\) 行全相同，第 \(j\) 列全相同这样的 \(2n\) 个条件。

要求的东西是至少有一行或者一列的限制/条件被满足的方案数。

也就是说我们如果设 \(S_i\) 表示所有满足第 \(i\) 个属性/限制的染色方案构成的集合，

显然不能直接把所有 \(|S_i|\) 相加，肯定会算重，那么考虑容斥，要求的答案就是 \(|\bigcup S_i|\)。

这个东西可以类比最简单的容斥，类似求 \(100\) 以内有多少数至少含有 \(2,3,5\) 其中一个因数。

写出来就是：

\[ ans = \sum\limits_{S \not= \emptyset}(-1)^{|S| - 1} f(S) \]

其中 \(S\) 表示若干个 \(S_i\) 的交，\(f(S)\) 表示这种情况的贡献。

考虑 \(S\) 表示有某 \(i\) 行，某 \(j\) 列是相同的情况，那么可以发现，选出来的这 \(i\) 行 \(j\) 列的颜色都是一样的。

我们现在就相当于 钦定 这 \(i\) 行 \(j\) 列是同一种颜色，剩下的 \((n - i)(n - j)\) 个格子就随便选（就算又有新的相等的也不管，因为这里是钦定，也就是只考虑被限制的部分，其他的部分都直接容斥掉了）。

因为 \(i\) 行 \(j\) 列是可以任意选的（这里只是考虑某个固定状态），那么 \(f(S)\) 就是 \(\dbinom{n}{i}\dbinom{n}{j}3^{1 + (n - i)(i - j)}\)

可以得知：

\[ \begin{aligned} ans &= 3\sum\limits_{i \not = 0 \lor j \not = 0} \dbinom{n}{i} \dbinom{n}{j} (-1)^{i + j - 1} 3^{i + j} \end{aligned} \]

考虑枚举 \(i\)，把式子拆开：

\[ \begin{aligned} ans= 3\sum\limits_{i > 0} \ [\ \dbinom{n}{i}(-1)^i \sum\limits_{j > 0} \ [\dbinom{n}{j} (-1)^j 3^{(n - i)(n - j)}\ ]\ ] \end{aligned} \]

后面那坨看起来像二项式定理，把 \(j=0\) 补上之后减去再用二项式定理：

也可以拉出来变成两个 \(\sum\) 的乘积，就可以合并了。

\[ ans = 3\sum\limits_{i > 0}\ [\ \dbinom{n}{i}(-1)^i([3^{n - i} - 1]^n - 3^{(n - i)n})\ ] \]

然后就可以 \(O(n \log n)\) 做了。

代码实现有几个细节，注意减法之后要加mod，然后尽量用 i64 做运算避免忘记乘 1ll。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// author : black_trees

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
using i64 = long long;

const i64 si = 1e6 + 10;
const i64 mod = 998244353;

i64 n;
i64 inv[si], fact[si], invf[si];
void init(i64 n) {
    inv[1] = 1, fact[0] = invf[0] = 1;
    for(i64 i = 2; i <= n; ++i)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(i64 i = 1; i <= n; ++i)
        fact[i] = 1ll * fact[i - 1] * i % mod,
        invf[i] = 1ll * invf[i - 1] * inv[i] % mod;
}
i64 C(i64 n, i64 m) {
    if(m < 0 || n < m) return 0;
    return 1ll * fact[n] * invf[n - m] % mod * invf[m] % mod;
}
i64 Qpow(i64 a, i64 b) {
    i64 ret = 1 % mod;
    for(; b; b >>= 1) {
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
    } return ret % mod;
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    i64 ans = 0, sum = 0;
    cin >> n, init(n);
    for(i64 i = 1; i <= n; i++) 
        ans = (ans + Qpow(3ll, (1ll * n * (n - i) + i)) * Qpow(-1ll, i + 1ll) * C(n, i) % mod + mod) % mod;
    ans = ans * 2ll % mod;
    i64 tmp = 0;
    for(i64 i = 0; i < n; i++) {
        i64 t = -Qpow(3ll, i);
        tmp = (tmp + C(n, i) * Qpow(-1, i + 1ll) * (Qpow(1 + t, n) - Qpow(t, n) + mod) % mod + mod) % mod;
    }
    ans = (ans + tmp * 3) % mod;
    cout << ans % mod << endl;
    return 0; 
}

ARC101(E/C) Ribbons on Treeψ(｀∇´)ψ

To be continued.

最后更新: September 6, 2023