模运算 — 从定义到计数

前言：从“时钟上的数学”说起

你可能已经注意到，大量的算法竞赛题最后都会说一句”答案对 $10^9+7$ 取模”。这不是在凑字数——而是因为很多计数问题的答案大得离谱。

举个例子：“从 100 个人里选 50 个组成委员会，有多少种选法？” 答案是 $\binom{100}{50} \approx 10^{29}$。这个数有 29 位，远超任何编程语言能精确表示的整数范围。如果题目问的不是 100 而是 $10^6$，答案的位数更是天文数字。

但题目不需要你输出那个天文数字本身，只需要输出它”除以某个素数（比如 $10^9+7$）的余数”。这个余数一定在 $0$ 到 $10^9+6$ 之间，计算机完全存得下。

于是问题变成：我们能不能在只保留余数的情况下，正确地完成中间的所有加减乘除运算？

答案是能——但这需要一套严谨的数学工具。这套工具就是模运算。

一个生活中的例子：现在是上午 10 点，6 个小时后是几点？你会说是下午 4 点，而不是 16 点（虽然 10+6=16）。你下意识地做了一次模运算：$16 \bmod 12 = 4$。时钟只有 12 个刻度，超过 12 就”卷绕”回去了。

模运算就是研究这种”卷绕”世界里的数学。它要回答的核心问题是：

• 什么时候两个数在这个卷绕的世界里”相等”？（同余）
• 卷绕世界里的加、减、乘和普通运算有什么区别？（运算性质）
• 卷绕世界里怎么做”除法”？（逆元）
• 怎么高效地计算组合数等复杂表达式？（阶乘、逆阶乘）

这篇笔记会按照这个顺序，从最基础的概念开始，逐步把这些问题讲清楚。最后用一道综合题，把所有知识点串起来。

一、同余：模运算的根基

1.1 定义

给定正整数 $m$，若 $m \mid (a - b)$（即 $a - b$ 是 $m$ 的倍数），则称 $a$ 与 $b$ 模 $m$ 同余，记作：

$$a \equiv b \pmod{m}$$

这意味着 $a$ 和 $b$ 除以 $m$ 的余数相同。等价地说，存在整数 $k$ 使得 $a = b + km$。

一个直觉：同余就是把整数”卷绕”到 $0, 1, \ldots, m-1$ 这 $m$ 个值上。想象一个标了 $0$ 到 $m-1$ 的时钟，每个整数映射到它除以 $m$ 的余数——这就是模运算的几何图像。

1.2 同余是等价关系

同余关系 $\equiv \pmod{m}$ 满足等价关系的三条性质：

性质	内容	为什么
自反性	$a \equiv a \pmod{m}$	$m \mid 0$，显然
对称性	$a \equiv b \Rightarrow b \equiv a$	$m \mid (a-b) \Rightarrow m \mid (b-a)$
传递性	$a \equiv b,\ b \equiv c \Rightarrow a \equiv c$	$m \mid (a-b)$ 且 $m \mid (b-c) \Rightarrow m \mid (a-c)$

因为它是等价关系，整数被划分为 $m$ 个等价类（也叫剩余类）：

$$\overline{r} = \{r + km : k \in \mathbb{Z}\}, \quad r = 0, 1, \ldots, m-1$$

所有等价类的集合记作 $\mathbb{Z}/m\mathbb{Z}$（或 $\mathbb{Z}_m$），共 $m$ 个元素。

二、模运算的代数性质

2.1 运算的封闭性

若 $a \equiv a' \pmod{m}$ 且 $b \equiv b' \pmod{m}$，则：

$$a + b \equiv a' + b' \pmod{m}$$ $$a - b \equiv a' - b' \pmod{m}$$ $$a \cdot b \equiv a' \cdot b' \pmod{m}$$

这意味着加法、减法、乘法在模意义下是良定义的——不依赖等价类中代表元的选取。

但除法不行。$2 \equiv 5 \pmod{3}$，但 $4/2 = 2$ 而 $4/5$ 甚至不是整数。模意义下的”除法”需要特殊处理——这就是逆元的由来。

2.2 模的分配律

实际计算中，为避免溢出，随时可以取模：

$$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$$ $$(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$$

减法需要小心：$(a - b) \bmod m$ 在 C++ 中可能得负数，应写成：

((a - b) % m + m) % m

2.3 $\mathbb{Z}/p\mathbb{Z}$ 是一个域

当 $m = p$ 为素数时，$\mathbb{Z}/p\mathbb{Z}$ 不仅是环，还是域——这意味着每个非零元素都有乘法逆元。这是素数模在竞赛中如此常见（$10^9+7$、$998244353$）的根本原因。

三、模逆元 — 模意义下的”除法”

3.1 定义

若存在整数 $x$ 使得 $ax \equiv 1 \pmod{m}$，则称 $x$ 是 $a$ 模 $m$ 的乘法逆元，记作 $a^{-1}$ 或 $a^{*-1}$。

存在条件：$a^{-1}$ 存在 $\iff$ $\gcd(a, m) = 1$。

当 $m = p$ 为素数且 $a \not\equiv 0$ 时，逆元一定存在。

3.2 费马小定理

若 $p$ 为素数且 $\gcd(a, p) = 1$，则 $a^{p-1} \equiv 1 \pmod{p}$。

这个定理告诉我们：在模素数 $p$ 下，$a$ 的幂次每 $p-1$ 步就会回到 1。这就像一个周期——既然 $a^{p-1} \equiv 1$，那我们自然想到：把它和逆元的定义 $ax \equiv 1$ 联系起来。

等式两边乘 $a^{-1}$：

$$a^{p-2} \equiv a^{-1} \pmod{p}$$

所以模素数 $p$ 下，$a$ 的逆元就是 $a^{p-2} \pmod{p}$——直接用快速幂算。

long long inv(long long a, long long p) {
    return qpow(a, p - 2, p);  // 快速幂
}

3.3 为什么逆元 = 模意义下的除法？

因为 $b / a \equiv b \cdot a^{-1} \pmod{m}$。

验证：$b \cdot a^{-1} \cdot a \equiv b \cdot 1 \equiv b \pmod{m}$。乘上去、再除回来，确实还原了。

四、模意义下的组合计数

4.1 阶乘与逆阶乘

要算大量的 $\binom{n}{k}$，预处理阶乘和逆阶乘：

$$\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!} \equiv n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \pmod{p}$$

预处理方式：

const int MOD = 998244353;
const int MAXN = 3000006;

long long fact[MAXN], inv_fact[MAXN];

void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % MOD;

    // 只需一次快速幂算 (n!)^{-1}，然后倒推
    inv_fact[n] = qpow(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

关键点：逆阶乘不需要逐个算快速幂，从 $\text{inv\_fact}[n]$ 倒推只需 $O(n)$，因为：

$$(k!)^{-1} = ((k+1)!)^{-1} \cdot (k+1)$$

4.2 插一句：Vandermonde 恒等式

后面会用到的一个重要组合恒等式：

$$\sum_{j} \binom{a}{j+r}\binom{b}{j} = \binom{a+b}{b+r}$$

它是范德蒙德卷积 $\sum_j \binom{a}{j}\binom{b}{n-j} = \binom{a+b}{n}$ 的变形。本质上说的是：从 $A \cup B$（$|A|=a, |B|=b$）中选 $b+r$ 个元素，按”从 $A$ 中选多少”来分类求和，结果等于直接选。

五、实战：序列计数

问题：求长度为 $X_1 + X_2 + X_3$ 的序列 $A$ 的个数，模 $998244353$，满足：

1. $A$ 含有 $X_1$ 个 $1$、$X_2$ 个 $2$、$X_3$ 个 $3$
2. 相邻元素之差的绝对值 $\le 1$（即 $|a_{i+1} - a_i| \le 1$）

约束：$1 \le X_1, X_2, X_3 \le 10^6$

5.1 约束的翻译

值只有 $1, 2, 3$，$|a_{i+1} - a_i| \le 1$ 意味着禁止 $1 \leftrightarrow 3$ 的直接跳转。

所以问题的等价表述是：在由 $1, 2, 3$ 组成的序列中，$1$ 和 $3$ 永不相邻。

5.2 组合建模

核心操作：把 $X_2$ 个 $2$ 排成一排，它们自然地把序列分成 $X_2 + 1$ 个”槽”：

$$\underbrace{\Box}_{\text{槽 }0}\ 2\ \underbrace{\Box}_{\text{槽 }1}\ 2\ \cdots\ 2\ \underbrace{\Box}_{\text{槽 }X_2}$$

每个槽可以填入：

• 若干个 $1$（每个 $\ge 1$）
• 若干个 $3$（每个 $\ge 1$）
• 什么都不填（$0$ 个元素）

但不能在一个槽里同时放 $1$ 和 $3$——因为槽内没有 $2$ 来隔开它们，而 $1$ 与 $3$ 相邻是禁止的。

为什么这样建模是对的？ 因为 $2$ 是唯一允许出现在 $1$ 和 $3$ 之间的值。一旦固定了 $2$ 的位置，所有非 $2$ 的位置自然形成了被 $2$ 分隔的连续段。在每个连续段内部，元素只能是纯 $1$ 或纯 $3$，否则就出现了 $1$-$3$ 相邻。

5.3 计数

设 $s$ 个槽分配给 $1$，$t$ 个槽分配给 $3$（$s + t \le X_2 + 1$，$s \ge 1$，$t \ge 1$）。

四个独立的选择：

步骤	做什么	方案数
1	从 $X_2+1$ 个槽中选 $s$ 个放 $1$	$\binom{X_2+1}{s}$
2	从剩余槽中选 $t$ 个放 $3$	$\binom{X_2+1-s}{t}$
3	将 $X_1$ 个 $1$ 分到 $s$ 个槽（每槽 $\ge 1$）	$\binom{X_1-1}{s-1}$
4	将 $X_3$ 个 $3$ 分到 $t$ 个槽（每槽 $\ge 1$）	$\binom{X_3-1}{t-1}$

步骤 3 和 4 用的是隔板法（Stars and Bars）：将 $n$ 个相同物品分到 $k$ 个非空组，方案数为 $\binom{n-1}{k-1}$。

所以：

$$\text{Ans} = \sum_{s=1}^{X_1}\sum_{t=1}^{X_3} \binom{X_2+1}{s}\binom{X_2+1-s}{t}\binom{X_1-1}{s-1}\binom{X_3-1}{t-1}$$

这是 $O(X_1 \cdot X_3)$ 的双重求和，$X_1, X_3$ 高达 $10^6$——太慢了。

5.4 用 Vandermonde 恒等式消一层求和

固定 $s$，对 $t$ 求和：

$$\sum_{t=1}^{X_3}\binom{X_2+1-s}{t}\binom{X_3-1}{t-1}$$

令 $j = t - 1$：

$$\sum_{j=0}^{X_3-1}\binom{X_2+1-s}{j+1}\binom{X_3-1}{j}$$

由 Vandermonde 恒等式的变形 $\sum_j \binom{a}{j+r}\binom{b}{j} = \binom{a+b}{b+r}$，取 $a = X_2+1-s$，$r = 1$，$b = X_3-1$：

$$= \binom{X_2+X_3-s}{X_3}$$

一层求和消失了。 最终公式：

$$\boxed{\text{Ans} = \sum_{s=1}^{\min(X_1,\, X_2+1)} \binom{X_2+1}{s}\binom{X_1-1}{s-1}\binom{X_2+X_3-s}{X_3}}$$

$O(\min(X_1, X_2))$ 的单层求和，完全可行。

5.5 验证

取 $X_1 = X_3 = 1$：

• 唯一的 $s = 1$，$\binom{X_2+1}{1}\binom{0}{0}\binom{X_2}{1} = (X_2+1) \cdot 1 \cdot X_2$
• 即答案为 $X_2(X_2 + 1)$

手动验证：$N = X_2 + 2$ 个位置放一个 $1$、一个 $3$、$X_2$ 个 $2$，$1$ 和 $3$ 不相邻。总排列 $(X_2+2)(X_2+1)$ 减去 $1$-$3$ 相邻的 $2(X_2+1)$，等于 $(X_2+1) \cdot X_2$。✓

5.6 C++ 实现

#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = 998244353;
const int MAXN = 3000006;

long long fact[MAXN], inv_fact[MAXN];

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

void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv_fact[n] = qpow(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    int X1, X2, X3;
    scanf("%d%d%d", &X1, &X2, &X3);

    init(X1 + X2 + X3);

    long long ans = 0;
    int M = min(X1, X2 + 1);
    for (int s = 1; s <= M; s++) {
        long long term = C(X2 + 1, s) * C(X1 - 1, s - 1) % MOD;
        term = term * C(X2 + X3 - s, X3) % MOD;
        ans = (ans + term) % MOD;
    }

    printf("%lld\n", ans);
    return 0;
}