组合数学专题总结

发表于 2026-05-19 更新于 2026-05-20 分类于专题总结

蓝桥杯国赛备赛过程中整理的一份组合数学基础专题总结，围绕取模逆元、组合数模板、错排模型、二项式定理、反射法与卡特兰数等内容，重点记录能直接转化为考场分数的知识模板与易错点。

前言

这篇文章是我在蓝桥杯国赛备赛过程中整理的一份组合数学专题总结。

起因是我在做 ABC458 E 时，发现自己虽然能推导出正确公式，但我并不会计算，对于乘法逆元、费马小定理、取模意义下的除法，以及组合计数中的一些常见模型并不了解。补题之后，我顺着这条线系统练了一组题，包括组合数模板、线性递推求逆元、错排、二项式定理、反射法和卡特兰数等内容。（ABC458 E 题解详见我的另一篇博客：AtCoder ABC458-E 复盘：隔板建模、非空分组与范德蒙德卷积）

这篇文章不是组合数学大全，也不会展开 Lucas 定理、扩展欧几里得、中国剩余定理或者更复杂的容斥模型。它的定位很明确：只整理“能转化成考场分数”的组合数学基础。

因此，本文更关注三个问题：

取模意义下的除法到底应该怎么处理；
常见组合计数模型应该如何快速转成公式；
写代码时哪些地方最容易因为边界、取模或中间溢出而出错。

取模除法与乘法逆元

在普通数学中，除法是很自然的操作。例如：

\frac{a}{b}

但是在取模意义下，不能直接写成：

1	(a / b) % MOD

因为整数除法会直接截断，而且模意义下的“除以 $b$ ”并不是普通除法，而应该理解为“乘上 $b$ 的乘法逆元”。

乘法逆元的定义

如果存在一个整数 $x$ ，满足：

bx \equiv 1 \pmod {MOD}

注：这里的 $\equiv$ 表示“同余”，可以理解为在模 $MOD$ 意义下相等。也就是说， $bx$ 和 $1$ 除以 $MOD$ 后的余数相同。等价地说， $bx-1$ 能被 $MOD$ 整除。

那么 $x$ 就叫做 $b$ 在模 $MOD$ 意义下的乘法逆元，记作：

b^{-1}

于是：

\frac{a}{b}\equiv a\cdot b^{-1}\pmod {MOD}

写成代码就是：

1	ans = a * inv(b) % MOD;

需要注意的是， $0$ 没有逆元。因为不存在任何 $x$ ，使得：

0\cdot x\equiv 1\pmod {MOD}

左边永远是 $0$ 。

费马小定理求逆元

如果 $MOD$ 是质数，且 $a$ 不是 $MOD$ 的倍数，那么根据费马小定理：

a^{MOD-1}\equiv 1 \pmod {MOD}

两边同乘 $a^{-1}$ ，可以得到：

a^{MOD-2}\equiv a^{-1}\pmod {MOD}

因此，在 $MOD$ 为质数且 $a \not\equiv 0 \pmod {MOD}$ 时，有：

a^{-1}\equiv a^{MOD-2}\pmod {MOD}

代码中通常取它在 $[0,MOD-1]$ 范围内的最小非负余数：

inv(a)=a^{MOD-2}\bmod MOD

写成代码就是：

using ll = long long;

//快速幂模板
ll qpow(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}                           

//费马小定理求逆元
ll inv(ll a) {
    return qpow(a, MOD - 2);
}

常见质数模数包括：1000000007、998244353

以及一些题目中给出的特定质数模数。

适用条件

费马小定理求逆元的适用条件是：

$MOD$ 是质数；
被求逆元的数 $a$ 与 $MOD$ 互质；
在质数模数下，只要 $a\not\equiv 0\pmod {MOD}$ ，就一定有逆元。

如果模数不是质数，或者 $a$ 与模数不互质，就不能无脑使用：

1	qpow(a, MOD - 2)

这属于更一般的逆元问题，通常需要扩展欧几里得等工具，本文暂不展开。

线性递推求普通逆元

如果需要求 $1\sim n$ 中每个数的逆元，当然可以对每个 $i$ 都写：

1	inv[i] = qpow(i, MOD - 2);

但是这样复杂度是：

O(n\log MOD)

如果 $n$ 很大，例如 $3\times 10^6$ ，就不够优秀。

对于质数模数，可以用线性递推在 $O(n)$ 时间内求出所有普通逆元。

线性递推求普通逆元的公式为：

inv_1 = 1

对于 $i\ge 2$ ，有：

inv_i \equiv \left(MOD-\left\lfloor\frac{MOD}{i}\right\rfloor\right)\cdot inv_{MOD\bmod i}\pmod{MOD}

其中， $inv_i$ 表示 $i$ 在模 $MOD$ 意义下的乘法逆元。

这一节的重点是理解这个公式从哪里来。

为什么不需要初始化 inv[0]

普通逆元 inv[i] 的含义是：

i\cdot inv[i]\equiv 1\pmod {MOD}

当 $i=0$ 时，这个式子变成：

0\cdot inv[0]\equiv 1\pmod {MOD}

显然不可能成立，所以 $0$ 没有逆元。

因此数组中真正有意义的起点是：

1	inv[1] = 1;

因为：

1\cdot 1\equiv 1\pmod {MOD}

递推式推导

设当前要求 $i$ 的逆元。根据整数除法，有：

MOD=\left\lfloor \frac{MOD}{i}\right\rfloor\cdot i+MOD\bmod i

为了书写方便，记：

q=\left\lfloor \frac{MOD}{i}\right\rfloor

r=MOD\bmod i

则：

MOD=qi+r

在模 $MOD$ 意义下， $MOD\equiv 0$ ，所以：

qi+r\equiv 0\pmod {MOD}

移项得：

r\equiv -qi\pmod {MOD}

也就是：

MOD\bmod i\equiv -\left\lfloor \frac{MOD}{i}\right\rfloor i\pmod {MOD}

接下来，两边同时乘上 $r$ 的逆元，也就是 $inv[r]$ 。

因为：

r\cdot inv[r]\equiv 1\pmod {MOD}

所以：

(-qi)\cdot inv[r]\equiv 1\pmod {MOD}

整理得：

i\cdot (-q\cdot inv[r])\equiv 1\pmod {MOD}

这说明：

-q\cdot inv[r]

就是 $i$ 的逆元。

代回 $q$ 和 $r$ ：

inv[i]\equiv -\left\lfloor \frac{MOD}{i}\right\rfloor\cdot inv[MOD\bmod i]\pmod {MOD}

为了避免负数，可以写成：

inv[i]=\left(MOD-\left\lfloor \frac{MOD}{i}\right\rfloor\right)\cdot inv[MOD\bmod i]\bmod MOD

也就是代码里的：

1	inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

为什么可以从小到大递推

因为：

MOD\bmod i<i

所以计算 inv[i] 时，需要用到的是 inv[MOD % i]，它的下标一定比 $i$ 小。

因此只要从 inv[1] 开始向后递推，每次需要的值都已经算过。

手推过程如下：

模板

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}

这类线性递推求的是普通逆元：

inv[i]=i^{-1}

不要和阶乘逆元混淆。

阶乘预处理与组合数模板

组合数公式为：

C_{n}^{k}=\frac{n!}{k!(n-k)!}

在模意义下，除法要转成乘法逆元，因此：

C_{n}^{k}\equiv n!\cdot (k!)^{-1}\cdot ((n-k)!)^{-1}\pmod {MOD}

于是可以预处理：

1 2	fac[i] = i! ifac[i] = (i!)^{-1}

然后快速计算组合数。

阶乘数组

阶乘数组很好处理：

fac[0] = 1;
for (int i = 1; i <= N; ++i) {
    fac[i] = fac[i - 1] * i % MOD;
}

其中：

fac[i]=i!

阶乘逆元数组

阶乘逆元数组表示：

ifac[i]=(i!)^{-1}

先求出最大项：

1	ifac[N] = qpow(fac[N], MOD - 2);

注意这里是：

1	qpow(fac[N], MOD - 2)

而不是：

1	qpow(N, MOD - 2)

因为 ifac[N] 表示的是 $(N!)^{-1}$ ，不是 $N^{-1}$ 。

接下来倒推。

因为：

(i+1)! = i!\cdot (i+1)

所以：

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

也就是：

ifac[i]=ifac[i+1]\cdot (i+1)

写成代码：

1
2
3

for (int i = N - 1; i >= 0; --i) {
    ifac[i] = ifac[i + 1] * (i + 1) % MOD;
}

组合数模板

ll C(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

完整预处理模板：

long long qpow(long long a, long long b) {
    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) {
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    ifac[N] = qpow(fac[N], MOD - 2);
    for (int i = N - 1; i >= 0; --i) {
        ifac[i] = ifac[i + 1] * (i + 1) % MOD;
    }
}

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

适用边界

这个模板适用于：

$MOD$ 是质数；
需要预处理的最大 $N$ 不太大；
普通阶乘中没有遇到更复杂的 $n\ge MOD$ 情形。

如果 $n$ 极大，或者 $n\ge MOD$ 后阶乘中含有模数因子，就不能简单套这个模板。那属于 Lucas 定理等更一般的内容，本文不展开。

错排模型

错排指的是：有 $n$ 个元素，每个元素都不能放回原来的位置，问有多少种排列方式。

记错排数为：

D_n

常用初值为：

D_0=1, D_1=0

递推式为：

D_n=(n-1)(D_{n-1}+D_{n-2})

递推推导

考虑第 $n$ 个元素。

它不能放在自己的位置，所以它可以放到前 $n-1$ 个位置中的任意一个。假设它放到了位置 $k$ ，其中：

1\le k\le n-1

接下来考虑原本应该放在位置 $k$ 的元素。

设第 $k$ 个元素为 $k$ 。

当 $n$ 放到了位置 $k$ 后，元素 $k$ 有两种情况。

情况一：元素 k 放到位置 n

也就是 $k$ 和 $n$ 互换位置。

此时这两个元素的位置已经确定：

$n$ 放到 $k$ 的位置；
$k$ 放到 $n$ 的位置。

剩下 $n-2$ 个元素仍然需要全部错排，所以方案数为：

D_{n-2}

情况二：元素 k 不放到位置 n

此时可以把位置 $n$ 看成“原来属于 $k$ 的禁位”。

换句话说，除去元素 $n$ 后，剩下 $n-1$ 个元素仍然形成一个错排问题：每个元素都不能放到自己的对应禁位上。

这部分方案数为：

D_{n-1}

对于第 $n$ 个元素，它一共有 $n-1$ 种选择位置的方式。因此总数为：

D_n=(n-1)(D_{n-1}+D_{n-2})

模板

D[0] = 1;
D[1] = 0;
for (int i = 2; i <= N; ++i) {
    D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % MOD;
}

如果题目不取模，并且范围很小，也可以不写 % MOD。

与组合数结合

一个常见变形是：要求排列中恰好有 $m$ 个位置固定。

可以先选出这 $m$ 个固定位置：

C_{n}^{m}

剩下 $n-m$ 个位置都不能固定，所以是一个错排问题：

D_{n-m}

因此答案为：

C_{n}^{m}\cdot D_{n-m}

洛谷P4071 就是这个模型的典型应用。

二项式定理与系数问题

二项式定理的基础形式是：

(A+B)^k=\sum_{i=0}^{k}C_{k}^{i}A^iB^{k-i}

也可以理解为：

一共有 $k$ 个括号，每个括号里都要在 $A$ 和 $B$ 之间选一个。选了 $i$ 次 $A$ ，就会选 $k-i$ 次 $B$ ，这种选法有 $C_{k}^{i}$ 种。

带系数的二项式

如果是：

(by+ax)^k

要求其中：

x^n y^m

这一项的系数。

由于要得到 $x^n$ ，必须选 $n$ 次 $ax$ ；要得到 $y^m$ ，必须选 $m$ 次 $by$ 。题目通常会保证：

n+m=k

从 $k$ 个括号中选出 $n$ 个括号取 $ax$ ，方案数是：

C_{k}^{n}

每选一次 $ax$ ，会贡献一个 $a$ ；选 $n$ 次就贡献：

a^n

每选一次 $by$ ，会贡献一个 $b$ ；选 $m$ 次就贡献：

b^m

所以最终系数为：

C_{k}^{n}a^n b^m

也可以写作：

C_{k}^{m}a^n b^m

因为 $n+m=k$ 。

代码形式

1	ans = C(k, n) * qpow(a, n) % MOD * qpow(b, m) % MOD;

这里容易错的地方是：不要只算组合数，也不要把组合数写成 $C_{n}^{m}$ 。

在洛谷P1313 中，核心就是把题面中的多项式系数问题翻译成这个公式。

反射法与广义卡特兰

反射法是一类处理“前缀合法限制”的经典方法。

常见模型是：

有 $n$ 个 1 和 $m$ 个 0，要求任意前缀中 1 的数量都不少于 0 的数量。问合法字符串数量。

也就是对于任意前缀，都要满足：

\#1\ge \#0

总方案数

如果不考虑前缀限制，那么只需要从 $n+m$ 个位置中选出 $m$ 个位置放 0，其余放 1。

所以总方案数为：

C_{n+m}^{m}

非法方案的刻画

非法方案指的是：存在某个前缀，使得：

\#0>\#1

从左到右扫描一个非法串，考虑它第一次变非法的位置。

在这个位置上，一定满足：

\#0=\#1+1

因为每次只加入一个字符，差值不可能一下子跳过这个状态。

第一次越界前缀反转

对一个非法串，找到第一次满足：

\#0=\#1+1

的前缀。

把这个前缀中的 0 和 1 全部互换。

假设这个前缀中原来有：

a\text{ 个 }1, \quad a+1\text{ 个 }0

反转后变成：

a+1\text{ 个 }1, \quad a\text{ 个 }0

所以整个字符串的总数量会从：

n\text{ 个 }1, \quad m\text{ 个 }0

变成：

n+1\text{ 个 }1, \quad m-1\text{ 个 }0

因此，每个非法串都会被映射成一个含有 $n+1$ 个 1 和 $m-1$ 个 0 的普通字符串。

为什么这是一一对应

只证明单向映射还不够，还需要说明不会多算或漏算。

反过来，任取一个含有：

n+1\text{ 个 }1, \quad m-1\text{ 个 }0

的字符串。

从左到右扫描，找到第一次满足：

\#1=\#0+1

的前缀。

这个前缀一定存在，因为整个字符串中 1 的数量比原来多了一个，而 0 的数量少了一个；从前缀差值的角度看，最终差值一定会变成正数，所以必然会第一次到达 $+1$ 。

然后把这个前缀中的 0 和 1 全部互换。

这个前缀原来有：

a+1\text{ 个 }1, \quad a\text{ 个 }0

反转后变成：

a\text{ 个 }1, \quad a+1\text{ 个 }0

于是反转后的字符串在这个前缀处第一次出现：

\#0=\#1+1

所以它一定是非法串。

两个方向的操作互为逆操作：

非法串第一次掉到 $-1$ ，反转后变成另一类普通串；
普通串第一次升到 $+1$ ，反转后回到非法串。

因此，非法串数量等于：

C_{n+m}^{m-1}

广义公式

所以合法方案数为：

C_{n+m}^{m}-C_{n+m}^{m-1}

如果 $n<m$ ，最终总的 1 都比 0 少，不可能所有前缀都满足 1 不少于 0，答案直接为 $0$ 。

洛谷P1641 就是这个模型的典型题。

标准卡特兰数与无模计算坑

当上一节中的 $n=m$ 时，就得到标准卡特兰数模型。

也就是：

有 $n$ 个 1 和 $n$ 个 0，要求任意前缀中 1 的数量都不少于 0 的数量。

根据反射法公式：

Cat_n=C_{2n}^{n}-C_{2n}^{n-1}

这就是第 $n$ 个卡特兰数的一种形式。

它还可以化简成：

Cat_n=\frac{1}{n+1}C_{2n}^{n}

简单推一下。由于：

C_{2n}^{n}=\frac{(2n)!}{n!\,n!}

而：

C_{2n}^{n-1}=\frac{(2n)!}{(n-1)!(n+1)!}

所以二者的比值为：

\frac{C_{2n}^{n-1}}{C_{2n}^{n}} = \frac{n!\,n!}{(n-1)!(n+1)!} = \frac{n}{n+1}

也就是说：

C_{2n}^{n-1}=\frac{n}{n+1}C_{2n}^{n}

代回原式：

Cat_n=C_{2n}^{n}-C_{2n}^{n-1}

得到：

Cat_n = C_{2n}^{n}-\frac{n}{n+1}C_{2n}^{n} = \frac{1}{n+1}C_{2n}^{n}

从组合数公式到递推式

如果题目不取模，且 $n$ 不大，可以用线性递推直接计算卡特兰数，避免中间阶乘爆掉。

从：

Cat_n=\frac{1}{n+1}C_{2n}^{n}

和：

Cat_{n-1}=\frac{1}{n}C_{2n-2}^{n-1}

考虑两者比值：

\frac{Cat_n}{Cat_{n-1}} = \frac{\frac{1}{n+1}C_{2n}^{n}}{\frac{1}{n}C_{2n-2}^{n-1}}

整理得：

\frac{Cat_n}{Cat_{n-1}} = \frac{n}{n+1}\cdot \frac{C_{2n}^{n}}{C_{2n-2}^{n-1}}

其中：

\frac{C_{2n}^{n}}{C_{2n-2}^{n-1}} = \frac{(2n)(2n-1)}{n^2}

所以：

\frac{Cat_n}{Cat_{n-1}} = \frac{n}{n+1}\cdot \frac{(2n)(2n-1)}{n^2}

化简后：

\frac{Cat_n}{Cat_{n-1}}=\frac{4n-2}{n+1}

于是递推式为：

Cat_n=Cat_{n-1}\cdot \frac{4n-2}{n+1}

代码中可以写成：

cat[0] = 1;
for (int i = 1; i <= n; ++i) {
    cat[i] = cat[i - 1] * (4 * i - 2) / (i + 1);
}

手推过程如下：

无模计算中的坑

在洛谷P1754 中， $n\le 20$ ，最终答案可以放进 long long。

但如果直接用阶乘计算：

C_{2n}^{n}-C_{2n}^{n-1}

就需要计算到：

(2n)!

当 $n=20$ 时，中间会出现：

40!

这远远超过 long long 范围。

所以这题的坑不是“答案爆 long long”，而是：

最终答案不爆，不代表中间阶乘不爆。

这种情况下可以使用卡特兰递推，或者用更稳的组合数乘法式 / 高精度等方式处理。

易错点汇总

这一节整理本模块中最容易写错、想错的地方。

普通逆元、阶乘逆元和阶乘数组的区别

最容易混的三个数组是：

1
2
3

fac[i]  = i!
ifac[i] = (i!)^{-1}
inv[i]  = i^{-1}

它们的含义完全不同。

fac[i] 是阶乘：

fac[i]=i!

ifac[i] 是阶乘的逆元：

ifac[i]=(i!)^{-1}

inv[i] 是普通数字 $i$ 的逆元：

inv[i]=i^{-1}

组合数模板中用的是：

1	fac[n] * ifac[k] % MOD * ifac[n - k] % MOD

普通除法中用的是：

1	a * inv[b] % MOD

inv 正推和 ifac 倒推不要混

普通逆元的线性递推是正向的：

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}

它求的是：

inv[i]=i^{-1}

阶乘逆元的倒推是反向的：

ifac[N] = qpow(fac[N], MOD - 2);
for (int i = N - 1; i >= 0; --i) {
    ifac[i] = ifac[i + 1] * (i + 1) % MOD;
}

它求的是：

ifac[i]=(i!)^{-1}

这两个公式长得都和逆元有关，但本质完全不同。

模减法要加 MOD

如果答案中有减法，例如：

a-b

在模意义下要写成：

1	(a - b + MOD) % MOD

否则即使真实答案非负，模后的两个数也可能出现前者小于后者，导致输出负数。

在洛谷P1641 中，公式为：

C_{n+m}^{m}-C_{n+m}^{m-1}

如果直接相减，就可能 WA。

0 没有逆元

不存在任何 $x$ ，使得：

0\cdot x\equiv 1\pmod {MOD}

所以 inv[0] 没有意义。

线性递推求普通逆元时，从 inv[1] 开始即可。

费马逆元要求模数是质数

1	qpow(a, MOD - 2)

这个写法依赖费马小定理，因此要求 $MOD$ 是质数，并且 $a$ 不是 $MOD$ 的倍数。

如果模数不是质数，需要考虑更一般的逆元判定与求法，本文不展开。

最终答案不爆，不代表中间阶乘不爆

在无模组合计数中，不能只看最终答案范围。

例如洛谷P1754 中，最终答案可以放进 long long，但如果用阶乘算组合数，中间会出现 $40!$ ，直接溢出。

这种情况下应该换计算方式，例如使用卡特兰递推。

组合数变量不要写错

二项式系数题里，最容易把变量写混。

例如洛谷P1313 中，要求的是：

(by+ax)^k

中 $x^n y^m$ 的系数。

正确组合数是：

C_{k}^{n}

不是：

C_{n}^{m}

因为本质是从 $k$ 个括号中选出 $n$ 个取 $ax$ 。

预处理范围要按题目最大需要值

如果题目需要计算：

C_{n+m}^{n}

那么预处理范围至少要到：

n+m

不要只预处理到 $n$ 或 $m$ 。

例如网格路径类题目洛谷P2265，需要的就是：

C_{n+m}^{n}

前缀合法类问题中 n < m 直接无解

对于模型：

$n$ 个 `1`， $m$ 个 `0`，要求任意前缀 `1` 的数量不少于 `0` 的数量。

如果：

n<m

那么最终整个字符串中 1 的数量都少于 0，一定无法满足条件，答案直接为 $0$ 。

练习题记录

下面记录本专题中涉及到的练习题。这里不展开题解，只标注每道题对应的训练点和 AC 代码链接。

洛谷B2164：基础组合数 / 取模练习。AC 代码
洛谷B3717：乘法逆元与组合数相关练习。AC 代码
洛谷P2265：网格路径计数，训练 $C_{n+m}^{n}$ 的建模和组合数模板。AC 代码
洛谷P4071：固定点计数与错排模型，训练 $C_{n}^{m}\cdot D(n-m)$ 。AC 代码
洛谷P1595：错排模型本体，训练 $D_n$ 递推。AC 代码
洛谷P3811：线性递推求普通逆元。AC 代码
洛谷P1313：二项式定理与带系数项的系数计算。AC 代码
洛谷P1641：反射法与广义卡特兰模型。AC 代码
洛谷P1754：标准卡特兰数模型，以及无模情况下中间阶乘溢出的计算坑。AC 代码
ABC458 E：组合计数公式推导、隔板建模与取模逆元的综合应用。AC 代码

结语

这篇专题主要整理了我在蓝桥杯备赛过程中补上的一组组合数学基础内容。

从取模除法开始，乘法逆元解决了“模意义下怎么除”的问题；费马小定理和快速幂给出了质数模数下求逆元的基本工具；线性递推进一步解决了批量求普通逆元的问题；阶乘和阶乘逆元预处理则构成了组合数模板的基础。

在模型层面，错排、二项式定理、反射法和卡特兰数分别对应几类很常见的组合计数题。真正需要记住的不是某一道题的代码，而是题面如何转化成这些模型：

固定点与“不回原位”可以想到错排；
多项式展开中的指定项系数可以想到二项式定理；
路径、括号、排队、01 串中的前缀合法限制可以想到反射法；
数量相等的前缀合法问题则是标准卡特兰数。

这部分内容并不算组合数学的全部，但对于蓝桥杯这类比赛来说，已经覆盖了不少能直接转化为分数的基础模型。后续如果再遇到更一般的组合计数问题，再根据题目需要补 Lucas、扩展欧几里得或更复杂的容斥。当前阶段，先把这些基础模板和推导真正写稳，比盲目扩展更重要。