38 · 组合计数与容斥原理

计数题只做两件事。乘法原理：一件事分几步做完，各步的选择互不影响，总方案数是各步之积。加法原理：把全部方案切成互不重叠的几类，总方案数是各类之和。排列、组合、容斥、错排，全是这两条的推论。

从 n 个不同元素里取 m 个排成一排：第一个位置有 n 种选法，第二个 n−1 种，……，第 m 个 n−m+1 种。乘法原理直接给出 A(n,m) = n(n−1)…(n−m+1) = n!/(n−m)!。如果不关心顺序，同一组 m 个元素被数了 m! 次（它们内部的 m! 种排法都算同一种选法），于是 C(n,m) = A(n,m)/m! = n!/(m!(n−m)!)。

“先按有序数、再除掉重复计数”这个动作会反复出现：圆排列除以 n（每种圈法被它的 n 个起点各数了一次），含重复元素的排列除以各元素个数的阶乘。记住这句，比背五个公式有用。

第三个动作是取模，它和公式对错完全无关。看这组数：

2000! 有 5736 位。所以“这题要不要取模”在读完数据范围的那一刻就定了，不存在“先算出来再取模”这种选项。本节只讲两套组合数求法中最基础的一套，它只有一个加法，因此对模数没有任何要求。

const int NMAX = 2005;
int C[NMAX][NMAX];                  // C[i][j] = C(i,j) % MOD

void build(int n) {                 // 预处理第 0..n 行
    for (int i = 0; i <= n; ++i) {
        C[i][0] = C[i][i] = 1 % MOD;        // 边界：选 0 个、选全部
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }
}
// build(5) 之后
// 第 4 行：1 4 6 4 1
// 第 5 行：1 5 10 10 5 1

// 求 1..n 中与 m 互质的数的个数：对 m 的质因子容斥
// k = m 的质因子个数，p[0..k-1] = 这些质因子，n = 上界
int cnt = 0;                                  // cnt = "不互质"的个数
for (int S = 1; S < (1 << k); ++S) {
    long long prod = 1; int bits = 0;
    for (int i = 0; i < k; ++i)
        if (S >> i & 1) { prod *= p[i]; ++bits; }  // p[] 是 m 的质因子
    cnt += (bits & 1) ? n / prod : -(n / prod);    // 奇数个质因子：加；偶数个：减
}
cout << n - cnt << "\n";                           // 补集：总数减“不互质”

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
int C[MAXN][MAXN];        // C[i][j] = C(i,j) mod k
int pre[MAXN][MAXN];      // pre[i][j] = 左上角矩形内 ok 的和
int qn[10005], qm[10005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; long long k;                 // k 最大到 10⁹ 也可能，用 long long 读不吃亏
    cin >> t >> k;

    int maxn = 0;
    for (int i = 0; i < t; ++i) {
        cin >> qn[i] >> qm[i];
        maxn = max(maxn, max(qn[i], qm[i]));   // m 可能比 n 大，上界要按两者取
    }

    for (int i = 0; i <= maxn; ++i) {
        C[i][0] = C[i][i] = 1 % k;      // 边界。写成 1，k = 1 时就会错
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k;   // 只有加法，k 不必是质数
    }

    for (int i = 0; i <= maxn; ++i)
        for (int j = 0; j <= maxn; ++j) {
            // j > i 时 C(i,j) 名义上是 0，但不在统计范围内，必须记 0 而不是 1
            int ok = (j <= i && C[i][j] == 0) ? 1 : 0;
            int v = ok;
            if (i) v += pre[i - 1][j];
            if (j) v += pre[i][j - 1];
            if (i && j) v -= pre[i - 1][j - 1];   // 容斥去重：左上角被加了两次
            pre[i][j] = v;
        }

    for (int i = 0; i < t; ++i)
        cout << pre[qn[i]][qm[i]] << "\n";   // j>i 的格子全是 0，所以不用再写 min
    return 0;
}

容斥解决的是“至少满足一个”。把“满足条件 i”记成集合 Aᵢ，则

|A₁ ∪ A₂ ∪ … ∪ A_m| =
    Σ|Aᵢ|  −  Σ|Aᵢ∩Aⱼ|  +  Σ|Aᵢ∩Aⱼ∩Aₖ|  −  …  +  (−1)^(m+1)|A₁∩…∩A_m|
    （第一个求和枚举 1 个集合，第二个枚举 2 个，共 2^m − 1 项）

它为什么对：设某个元素恰好属于 r 个集合（r ≥ 1）。右边把它数了 C(r,1) − C(r,2) + C(r,3) − … 次，而这个交错和等于 1 − (1−1)^r = 1。不属于任何集合的元素被数 0 次。所以每个该被数的元素恰好被数一次。证明用的是二项式定理，见本节数学补给。

例：1..1000 中不能被 2、3、5 整除的数有多少个？令 A₂、A₃、A₅ 分别是被 2、3、5 整除的数。

1000 − (500 + 333 + 200) + (166 + 100 + 66) − 33 = 266
  ↑总数   ↑一个集合           ↑两个集合的交        ↑三个集合
          500=|A₂|  333=|A₃|  200=|A₅|
          166=|A₂∩A₃|(÷6)  100=|A₂∩A₅|(÷10)  66=|A₃∩A₅|(÷15)  33=|A₂∩A₃∩A₅|(÷30)

注意每一步都只用到 ⌊n/d⌋：“1..n 中能被 d 整除的数的个数”。容斥题能不能做，几乎全看交集的集合大小能不能 O(1) 算出来。

错排是容斥最经典的应用。n 封信全部装错：令 Aᵢ = “第 i 封信装进了第 i 个信封”，要的是 |A₁∪…∪Aₙ| 的补集。|Aᵢ| = (n−1)!，|Aᵢ∩Aⱼ| = (n−2)!，k 个集合的交 = (n−k)!，而 k 个集合有 C(n,k) 种选法，于是

D(n) = n! − C(n,1)(n−1)! + C(n,2)(n−2)! − … + (−1)ⁿ·C(n,n)·0!
     = n! · ( 1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n! )

这个和式里都是除法，不好直接算。把它化简成只含加减乘的递推：

D(1) = 0,  D(2) = 1
D(n) = (n − 1) · ( D(n−1) + D(n−2) )        // n ≥ 3

证明：第 n 封信一定不在第 n 个信封里，设它进了第 k 个信封（k 有 n−1 种选法）。此时看第 k 封信，只有两种可能：① 它进了第 n 个信封——两封信互换，剩下 n−2 封要错排，方案数 D(n−2)；② 它没进第 n 个信封——把“第 n 个信封”改名成“第 k 个信封”，剩下的正好是 n−1 封信的错排，方案数 D(n−1)。两类互不重叠，相加后乘 n−1。

前几项：0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961。手算 D(3) = 2 可以验证：只有 (2,3,1) 和 (3,1,2) 两种。D(13) = 2290792932 已经超 int，D(20) = 895014631192902121 还在 long long 内，D(21) = 18795307255050944540 就超了。

#include <bits/stdc++.h>
using namespace std;

long long D[25];        // D[n] = n 封信全部装错的方案数，n ≤ 20

int main() {
    int n;
    cin >> n;

    D[1] = 0;           // 1 封信只有"装对"一种放法，全错 0 种
    D[2] = 1;           // 2 封信只有互换这一种放法，且两封都错
    for (int i = 3; i <= n; ++i)
        D[i] = (long long)(i - 1) * (D[i - 1] + D[i - 2]);   // 第 i 封有 i-1 个"错"位置可选

    cout << D[n] << "\n";
    return 0;
}

(1+x)^n = C(n,0) + C(n,1)x + C(n,2)x² + … + C(n,n)xⁿ

C(r,1) − C(r,2) + C(r,3) − … + (−1)^(r+1)·C(r,r)
= 1 − [ C(r,0) − C(r,1) + C(r,2) − … + (−1)^r·C(r,r) ]
= 1 − (1−1)^r = 1

D(n)/n! = 1 − 1/1! + 1/2! − 1/3! + … + (−1)^n/n!
n = 10：D(10)/10! = 1334961/3628800 = 0.3678794643
1/e                     = 0.3678794412      差 2.3×10⁻⁸

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 100003;

long long qpow(long long a, long long b) {   // a^b mod MOD
    long long res = 1 % MOD;
    a %= MOD;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    long long m, n;
    cin >> m >> n;              // 先读宗教数 m，再读房间数 n
    m %= MOD;                   // 底数先压进模数，避免中间乘积溢出

    long long total = qpow(m, n);                              // 全部状态 m^n
    long long bad   = m * qpow((m - 1 + MOD) % MOD, n - 1) % MOD;  // 一个相邻相同都没有
    cout << (total - bad + MOD) % MOD << "\n";                 // 减法后补 MOD 再取模
    return 0;
}