组合数学

组合意义天地灭，代数推导保平安。

# 阅读前须知

​ 本博客包含了一些提高到省选难度的组合数学知识点，主要由知识点和笔者做题时遇到的一些题组成。

​ 对于知识点，阅读前需要你掌握最基础的一些组合数学知识，如排列数组合数，插板法等等，还需要一定的推式子能力，其中还会涉及到一部分与多项式和生成函数有关的内容，读者可以自行选择阅读。同时由于笔者能力有限，更高级的多项式和生成函数知识无法涉及到，若想学习可以从网上搜集学习。

​ 题目上笔者也对题目进行了简单分类，读者完全可以只看自己学了的知识点所对应的题目。由于笔者水平有限，题目难度可能不高，还请大家谅解。

​ 同时这篇博客也会在笔者学过更高深的内容后，进行知识上和题目上的不定期的更新。

# 组合数学知识点

# Lucas 定理

当 $p$ 为质数时，有 ${\binom{n}{m}} \equiv {\binom{n/p}{m/p} } \times {\binom{n\bmod p} {m \bmod p}} {\pmod{p}}$

# 基础组合数公式

定义式： ${\binom{n}{m}}={\frac{n!}{m!\times(n-m)!}}$

二项式定理： $(a+b)^n=\sum_{i=0}^{n}\binom{n}{i}a^{n-i}b^i$

$\binom{n}{m}=\binom{n}{n-m}$ ，取补集即可

$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$ ，根据定义式直接展开即可

$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$ ，常见递推式，分别考虑选不选第 $m$ 个得到

$\sum_{i=0}^n\binom{n}{i}=2^n$ ，二项式定理取 $a=b=1$ 时的特殊情况，也可以理解为任意选择

$\sum_{i=0}^{n}\binom{n-m}{i-m}=2^{n-m}$ ，上式变形。

$\sum_{i=0}^{n}\binom{n}{i}(-1)^i=\sum_{i=0}^{n}\binom{n}{i}(-1)^{n-i}=[n=0]$ ，二项式定理取 $a=1,b=-1$ 的特殊情况，只有当 $n=0$ 时答案为 $1$ 。

$\sum_{i=0}^{n}\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}$ $(n\ge m)$

$\sum_{i=0}^{n}\binom{n}{i}^2=\binom{2n}{n}$ ，上一条取 $n=m$ 的特殊情况

$\sum_{i=0}^{n} {i} {\binom{n}{i}} = {n} \times {2^{n-1}}$

考虑对于 $F(x)=(1+x)^n=\sum_{i=0}^{n}\binom{n}{i}x^i$ ，两边同时求导得 $n(1+x)^{n-1}=\sum_{i=1}^{n}\binom{n}{i}ix^{i-1}$ ，取 $x=1$ 时可得

$\sum_{i=0}^{n}\binom{i}{m}=\binom{n+1}{m+1}$ ，上指标求和公式，不断递推即可得到

$\sum_{i=0}^{n}\binom{m+i}{m}=\binom{m+n+1}{m}$ ，平行求和公式，与上指标求和证明类似

$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$ ，定义式直接化简可得

范德蒙德卷积： $\sum_{i=0}^{k}\binom{r}{i}\binom{s}{k-i}=\binom{r+s}{k}$ ，证明如下：

$$\begin{aligned} (1+x)^{r+s}&=\sum_{i=0}^{r+s}\binom{r+s}{i}x_i\\ &=(1+x)^r\times(1+x)^s\\ &=(\sum_{i=0}^{r}\binom{r}{i}x^i)(\sum_{j=0}^{s}\binom{s}{j}x^j)\\ &=\sum_{i=0}^{r+s}\sum_{j=0}^{i}\binom{r}{j}\binom{s}{i-j}x^i \end{aligned}$$

由于对应项系数相等，所以 $\sum_{i=0}^{k}\binom{r}{i}\binom{s}{k-i}=\binom{r+s}{k}$ ，得证。

# 二项式反演

# 常用形式一

设 $f_n$ 表示恰好 $n$ 个元素形成特定结构的方案数，$g_n$ 表示从 $n$ 个元素中选出 $i\ge 0$ 个元素形成特定结构的方案数，根据定义我们得到 $g_n=\sum_{i=0}^{n}\binom{n}{i}f_i$ 。若我们已知 $g_n$ ，要求解 $f_i$ ，有反演公式 $f_n=\sum_{i=0}^{n}\binom{n}{i}(-1)^{n-i}g_i$ 。代数推导证明如下（大式子警告！）

$$\begin{aligned} f_n &= \sum_{i=0}^{n}{\binom{n}{i}}(-1)^{n-i}g_i\\ &= \sum_{i=0}^{n}{\binom{n}{i}}(-1)^{n-i}\sum_{j=0}^{i}{\binom{i}{j}}f_j\\ &= \sum_{i=0}^{n}\sum_{j=0}^{i}{\binom{n}{i}}{\binom{i}{j}}(-1)^{n-i}f_j\\ &= \sum_{j=0}^nf_j\sum_{i=j}^{n}{\binom{n}{i}}{\binom{i}{j}}(-1)^{n-i}\\ &= \sum_{j=0}^{n}f_j\sum_{i=j}^{n}{\binom{n}{j}}{\binom{n-i}{i-j}}(-1)^{n-i}\\ \end{aligned}$$

我们设 $k=i-j$ ，则

$$\begin{aligned} f_n&=\sum_{j=0}^{n}f_j\binom{n}{j}\sum_{k=0}^{n-j}\binom{n-j-k}{k}(-1)^{n-j-k}\\ &=\sum_{j=0}^{n}f_j\binom{n}{j}[n-j=0]\\ &=\sum_{j=0}^{n}f_j\binom{n}{j}[n=j]\\ &=f_n \end{aligned}$$

证毕。

其实也有更简单的证法，我们利用 $EGF$ 。

$$\begin{aligned} f_n&=\sum_{i=0}^{n}\binom{n}{i}g_i\\ \frac{f_n}{n!}&=\sum_{i=0}^{n}\frac{1}{(n-i)!}\frac{g_i}{i!}\\ F(x)&=e^x\,G(x)\\ G(x)&=F(x)\,e^{-x}\\ g_n&=\sum_{i=0}^{n}\binom{n}{i}(-1)^{n-i}f_i\\ \end{aligned}$$

我们考虑其实际意义，$g_n$ 表示至多 $n$ 个的方案数，$f_n$ 表示恰好 $n$ 个的方案数。

​ $g_n=\sum_{i=0}^{n}\binom{n}{i}f_i$ $f_n=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}g_i$

# 常用形式二

$g_k$ 表示至少 $k$ 个的方案数，$f_k$ 表示恰好 $k$ 个的方案数。

​ $g_k=\sum_{i=k}^{n}\binom{i}{k}f_i$ $f_k=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}g_i$ （证明与形式一类似，此处省略）

# 多重集排列数

​ 共有 $n$ 个球，有 $k$ 种，每种球有 $a_i$ 个，则所有球的全排列数为 $\frac{n!}{\prod_{i=1}^{k}a_i!}$ 。

# 卡特兰数

卡特兰数常见求解式子，默认 $C_0=C_1=1$ 。

$$C_n=\frac{\binom{2n}{n}}{n+1}\\ C_n=\sum_{i=1}^{n}C_{i-1}C_{n-i}\\ C_n=C_{n-1}\frac{4n-2}{n+1}\\ C_n=\binom{2n}{n}-\binom{2n}{n-1}$$

进栈序列为 $1$ 到 $n$ ，求出栈序列数

$n$ 个节点的二叉树数量

长度为 $2n$ 个括号序列数

凸 $n+2$ 边形三角剖分数

以上答案均为卡特兰数第 $n$ 项 $C_n$ 。

# 斯特林数

# 第二类斯特林数

第二类斯特林数，又叫做斯特林子集数。$n\brace m$ 表示将 $n$ 个元素划分为 $m$ 个互不相同的非空子集的方案数。

递推式：${n \brace m}={n-1\brace m-1}+m{n-1\brace m}$ ，枚举将新元素放入一个新子集或放入之前的子集中得到。

通项公式：${n\brace m}=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$ 。

证明：我们有 $m^n=\sum_{i=0}^{m}{n\brace i}\times i!\times \binom{m}{i}$ 。（考虑其组合意义，左边表示 $n$ 个不同球随意放进 $m$ 个盒中的方案数，右边表示枚举非空盒子的数量 $i$ 计算即可。）

显然我们考虑二项式反演，设 $g_i=i^n$ ，$f_i={n\brace i}i!$ ，有 $g_m=\sum_{i=0}^{m}\binom{m}{i}f_i$ ，则

$$\begin{aligned} f_m&=\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}g_i\\ {n\brace m}\times m!&=\sum_{i=0}^{m}(-1)^{m-i}\frac{m!}{i!(m-i)!}i^n\\ {n\brace m}&=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!} \end{aligned}$$

另一种写法 ${n\brace m}=\sum_{i=0}^{m}\frac{(-1)^i(m-i)^n}{i!(m-i)!}$ 。

所以我们得到了求同一行第二类斯特林数 $n\brace i$ 的方法，直接按照递推式卷积一下即可，时间复杂度 $O(n\log n)$ 。

根据上面我们还可以得到自然数幂求和的一个推导：

$$\begin{aligned} \sum_{i=0}^{n}i^k&=\sum_{i=0}^{n}\sum_{j=0}^{k}{k\brace j}\times j!\times \binom{i}{j}\\ &=\sum_{j=0}^{k}{k \brace j}\times j!\times \sum_{i=0}^{n}\binom{i}{j}\\ &=\sum_{j=0}^{k}{k\brace j}\times j!\times \binom{n+1}{j+1} \end{aligned}$$

我们再从 $EGF$ 的角度去研究第二类斯特林数，一个非空盒子装 $i$ 个物品的方案数为 $[i>0]$ ，对应的 $EGF$ 为 $F(x)=\sum_{i=1}^{\infty}\frac{x^i}{i!}$ ，其封闭形式为 $e^x-1$ ，所以 $k$ 个无标号非空盒子装 $i$ 个物品对应的 $EGF$ 为 $\frac{(e^x-1)^k}{k!}$ ，同时它也是同一列第二类斯特林数对应的 $EGF$ ，即 $\sum_{i=k}^{\infty}{i\brace k}\frac{x^i}{i!}=\frac{(e^x-1)^k}{k!}$ 。

# 第一类斯特林数

第一类斯特林数，又叫斯特林轮换数。$n\brack m$ 表示将 $n$ 个元素分为 $m$ 个环的方案数（旋转前后相同的环视为一个环）

递推式： ${n\brack m}={n-1\brack m-1}+(n-1){n-1 \brack m}$ ，枚举将新元素放入一个新环或插入一个旧环中得到。

性质： $\sum_{i=1}^{n}{n\brack i}=n!$ ，每种排列对应每种置换。

# 上升幂与下降幂

下降幂 $x^{\underline n}=\frac{x!}{(x-n)!}=\prod_{i=0}^{n-1}(x-i)$

上升幂 $x^{\overline n}=\prod_{i=0}^{n-1}(x+i)$

普通幂转下降幂 $x^n=\sum_{i=0}^{n}{n \brace i}x^{\underline i}$ ，下降幂转普通幂 $x^{\underline n}=\sum_{i=0}^{n}{n\brack i}(-1)^{n-i}x^i$

普通幂转上升幂 $x^n=\sum_{i=0}^{n}{n \brace i}(-1)^{n-i}x^{\overline i}$ ，上升幂转普通幂 $x^{\overline n}=\sum_{i=0}^{n}{n\brack i}x^i$

现在证明第二个式子，我们利用归纳法

$$\begin{aligned}\\ x^{\underline {n+1}}&=(x-n)x^{\underline n}\\ &=(x-n)\sum_{i=0}^n {n \brack i}(-1)^{n-i}x^i\\ &=x\sum_{i=0}^{n} {n \brack i}(-1)^{n-i}x^{i}-n\sum_{i=0}^n {n \brack i}(-1)^{n-i} x^i\\ &=\sum_{i=0}^{n} {n \brack i}(-1)^{n-i}x^{i+1}-n\sum_{i=0}^{n+1} {n \brack i}(-1)^{n-i} x^i\\ &=\sum_{i=1}^{n+1} {n \brack i-1}(-1)^{n-i+1}x^{i}+n\sum_{i=1}^{n+1} {n \brack i}(-1)^{n-i+1} x^i\\ &=\sum_{i=1}^{n+1} ({n \brack i-1}+n*{n \brack i})(-1)^{n-i+1}x^{i}\\ &=\sum_{i=1}^{n+1} {n+1 \brack i}(-1)^{n-i+1}x^{i}\\ &=\sum_{i=0}^{(n+1)} {n+1 \brack i}(-1)^{(n+1)-i}x^{i}\\ \end{aligned}$$

我们再证明第四个式子，利用第二个式子的结论，

$$\begin{aligned} x^{\overline n}&=(-1)^n(-x)^{\underline n}\\ &=\sum_{i=0}^{n}{n \brack i}(-1)^n(-1)^{n-i} (-x)^i\\ &=\sum_{i=0}^{n}{n\brack i}(-1)^{n+n-i+i}x^i\\ &=\sum_{i=0}^{n}{n\brack i}x^i \end{aligned}$$

# 斯特林反演

​ 若 $f_k=\sum_{i=0}^{k}{k\brace i}g_i$ ，则有 $g_k=\sum_{i=0}^{k}(-1)^{k-i}{k\brack i}f_i$

斯特林反演与二项式反演相比不太常用，可以只做了解。

# 组合计数

# [NOIP2016 提高组] 组合数问题

​ 题意：给定 $n,m,k$ ，求对于所有的 $0\le i\le n,0\le j\le \min(i,m)$ 有多少对 $(i,j)$ 满足 $k|\binom{i}{j}$ 。

​ $n\le 2000$ ，$m\le 2000$ ，$k\le 21$ 。

直接 $O(n^2)$ 递推预处理所有组合数模 $k$ 意义下的值，然后设 $f_{i,j}$ 表示 $n=i,m=j$ 时对应的答案。考虑每拓展一次对答案的贡献，$f_{i,j}=f_{i-1,j-1} +(f_{i-1,j}-f_{i-1,j-1})+(f_{i,j-1}-f_{i-1,j-1})=f_{i-1,j}+f_{i,j-1}-f_{i-1,j-1}$ ，同时判断 $\binom{i}{j}$ 的值是否为 $0$ ，若为 $0$ 则 $f_{i,j}++$ ，然后直接 $dp$ 过去即可。时间复杂度 $O(nm)$ 。

# [SDOI2016] 排列计数

​ 题意：求有多少种 $1$ 到 $n$ 的排列 $p$ 满足有恰好 $m$ 个位置 $p_i=i$ 。答案对 $10^9+7$ 取模。

​ $n,m\le 10^6$ ，$T\le 5\times 10^5$ 。

考虑钦定这 $m$ 个位置，有 $\binom{n}{m}$ 种情况。再考虑剩下的 $(n-m)$ 个位置，由于恰好 $m$ 个位置满足 $p_i=i$ ，所以剩下的这 $(n-m)$ 个位置为错排，直接递推错排数公式 $f_i=(i-1)(f_{i-1}+f_{i-2})$ ，初始化 $f_0=1,f_1=0$ 。最终答案为 $\binom{n}{m}\times f_{n-m}$ 。时间复杂度为 $O(n+T)$ 。

# [NOI Online #2 入门组] 建设城市

​ 有 $2n$ 座建筑，每座建筑的高度为 $1$ 到 $m$ 之间的正整数，要求前 $n$ 座高度单调不降，后 $n$ 座高度单调不升，且第 $x$ 座和第 $y$ 座的高度相同，求方案数模 $998244353$ 后的结果。

​ $1\le n,m\le 10^5$ ，$1\le x<y\le2n$

经典组合计数题，我们先分类讨论一下。

当 $x\le n<y$ 时，我们枚举第 $x$ 和第 $y$ 座的高度 $i$ ，此时序列会被分成 $4$ 部分，以第一部分为例，它们高度区间为 $[1,i]$ ，编号区间为 $[1,x-1]$ 。即将 $x-1$ 个相同的球放进 $i$ 个盒子里的方案数，允许盒子为空，这就是经典的插板法了，易得答案为 $\binom{x-1+i-1}{i-1}$ ，同理我们能求出其它部分的方案数，乘起来即可。

再考虑当 $x<y\le n$ 或 $n<x<y$ 时，我们可以将 $x$ 到 $y$ 之间看成一个建筑，这样序列就被分成了两个部分，还是按照上面的插板法计算即可。最终时间复杂度为 $O(n+m)$ 。

# [HAOI2011] Problem c

​ 给 $n$ 个人安排座位，每个人有一个编号 $a_i$ （编号可以相同）。从第一个人开始依次入座，第 $i$ 个人先尝试坐到 $a_i$ ，如果 $a_i$ 被占了，就尝试 $a_i+1$ ，$a_i+1$ 被占据了就尝试 $a_i+2$ ，依次类推。如果一直尝试到第 $n$ 个都不行，该安排方案就不合法。现在有 $m$ 个人的编号已经确定，安排剩下的人的编号，求有多少种合法的安排方案，无解输出 NO，有解输出方案数对 $mod$ 取模的结果。

​ $T\le 10$ ，$n\le 300$ ，$0\le m\le n$ ，$2\le mod\le 10^9$

先考虑无解的情况，我们设 $sum_i$ 表示已经确定的人中编号 $\ge i$ 的人数。枚举编号，若 $sum_i>n-i+1$ ，说明一定有人尝试到第 $n$ 个也没座位，此时无解。然后我们去考虑有解的方案数，我们考虑一个 $dp$ ，设 $f_{i,j}$ 表示剩余人数中编号 $\ge i$ 的人中已经确定 $j$ 个人的方案数，我们枚举一个 $k$ ，表示选择 $k$ 人的编号为 $i$ ，有转移 $f_{i,j}=\sum _{k=0}^{j}f_{i+1,j-k}\times \binom{j}{k}\;(0\le j\le n-sum_i-i+1)$ ，最终答案为 $f_{1,n-m}$ 。时间复杂度 $O(Tn^3)$ 。

# [SHOI2015] 超能粒子炮・改

​ 求 $\sum_{i=0}^{k}\binom{n}{i}$ 的值，对质数 $p=2333$ 取模。

​ $T\le 10^5$ ，$n,k\le {10^{18}}$

我们设 $f_{n,k}=\sum_{i=0}^{k}\binom{n}{i}$ ，大力化简。

$$\begin{aligned} f_{n,k}&=\sum_{i=0}^{k}\binom{n}{i}\\ &=\sum_{i=0}^{k}\binom{n/p}{i/p}\times\binom{n\bmod p}{i\bmod p}\\ &=\binom{n/p}{0}\times\sum_{i=0}^{p-1}\binom{n\bmod p}{i}+\binom{n/p}{1}\times\sum_{i=0}^{p-1}\binom{n\bmod p}{i}+\cdots+\binom{n/p}{k/p}\times\sum_{i=0}^{k\bmod p}\binom{n\bmod p}{i}\\ &=(\,\sum_{i=0}^{p-1}\binom{n\bmod p}{i}\times\sum_{j=0}^{k/p-1}\binom{n/p}{j}\,)+\binom{n/p}{k/p}\times\sum_{i=0}^{k\bmod p}\binom{n\bmod p}{i}\\ &=f_{n\bmod p,p-1}\times f_{n/p,k/p-1}+\binom{n/p}{k/p}\times f_{n\bmod p,k\bmod p} \end{aligned}$$

直接递归求解即可，并且由于 $p$ 只有 $2333$ ，所以可以直接预处理 $2333$ 以内的组合数以及 $f$ 数组即可，对于 $\binom{n/p}{k/p}$ 直接 $lucas$ 定理计算即可。时间复杂度为 $O(p^2+T\log_{p}^2n)$ 。

# [CQOI2018] 交错序列

​ 称一个 $01$ 序列为交错序列，当且仅当序列中没有相邻的 $1$ 。对于一个长度为 $n$ 的交错序列，设 $0$ 出现的次数为 $x$ ，$1$ 出现的次数为 $y$ ，并给定非负整数 $a,b$ ，则我们定义这个序列的特征值为 $x^a\times y^b$ 。求长度为 $n$ 的所有交错序列的特征值之和对质数 $mod$ 取模的结果。

​ $1\le n \le 10^7$ ，$0\le a,b\le 45$ ，$mod\le 10^8$

我们考虑枚举序列中 $1$ 的个数 $i$ ，那么有 $n-i$ 个 $0$ ，考虑插板法。有 $n-i+1$ 个空位，填入 $i$ 个 $1$ ，则方案数为 $\binom{n-i+1}{i}$ ，同时根据 $n-i+1\ge i$ 得到 $i\le \lfloor\frac{n+1}{2}\rfloor$ ，所以答案为 $\sum \limits_{i=0}^{\lfloor \frac{n+1}{2}\rfloor}\binom{n-i+1}{i}\times i^b\times (n-i)^a$ 。发现可以直接线性筛得到 $i^a,i^b$ ，且 $mod$ 为质数也可以通过求阶乘和阶乘的逆元求组合数。所以最终时间复杂度为 $O(n)$ 。事实上这道题有更优秀的时间复杂度，这里不再介绍。

# luogu P4981 父子

​ 多次询问 $n$ 个点的有根树种类对 $10^9+9$ 取模后的结果。

​ $T\le 10^4$ ，$n\le 10^9$

# Prufer 序列

Prufer 序列可以用来解决一些无根树计数的问题。

树转化为 Prufer 序列：每次从树上选出一个编号最小的叶子节点，然后将与该叶子节点相邻的节点的编号写入 Prufer 序列的末尾，然后从树上删掉这个叶子节点，循环这个步骤直到只剩下两个节点。这个过程可以用一个 set 维护度数为 $1$ 的节点实现。

一些性质：一个 $n$ 个节点的树对应长度为 $n-2$ 的 Prufer 序列，Prufer 序列中某个数出现的次数就等于这个数对应的节点在原无根树中的度数减一。

Cayley 公式：$n$ 个节点的有标号无根树有 $n^{n-2}$ 个。（根据 Prufer 序列易得）

推论：1. $n$ 个节点的有标号有根树有 $n\times n^{n-2}=n^{n-1}$ 个。

​ 2. 已知 $n$ 个节点的度数为 $d_1,d_2\cdots d_n$ ，这样的无根树有 $\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}$ 个。

所以这道题答案为 $n^{n-1}$ ，快速幂计算一下即可。时间复杂度为 $O(T\log n)$ 。

# [HNOI2004] 树的计数

​ 一个 $n$ 个节点的树，给定每个节点的度数 $d_i$ ，问这样的树有多少种。

​ $1\le n\le 150$ ，答案保证在 long long 范围内。

还是熟悉的 Prufer 序列。题意可以转化为：有 $n-2$ 个位置，要放 $n$ 个数，每个数占 $d_i-1$ 个位置，问方案数。这就是一个简单的组合计数，$ans=\prod_{i=1}^{n}\binom{sum}{d_i-1}$ ，其中 $sum$ 表示剩余的位置数，预处理组合数即可。同时这个式子化简完就可以得到 $\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}$ ，但是这么算要写高精度，所以不如原始式子。时间复杂度 $O(n^2)$ 。

# CF785D Anton and School - 2

​ 给定一个长度为 $n$ 的只由小括号组成的括号序列，问有多少个长度为偶数的子序列，满足前半部分均为 '('，后半部分均为 ')' 。

​ $1\le n\le 2\times10^5$

考虑枚举满足条件的子序列中最后一个 '(' 的位置，假设它左边有 $a$ 个 '(' （包括它自己），右边有 $b$ 个 ')' ，那么它对答案的贡献为 $\sum_{i=0}^{\min(a-1,b-1)}\binom{a-1}{i}\binom{b}{i+1}$ ，此时时间复杂度为 $O(n^2)$ ，考虑优化。发现这个东西有点像范德蒙德卷积：$\sum_{i=0}^{k}\binom{a}{i}\binom{b}{k-i}=\binom{a+b}{k}$ ，所以我们转化一下。

当 $\min(a-1,b-1)=b-1$ 时，$\sum_{i=0}^{b-1} {\binom{a-1}{i}}{\binom{b}{b-i-1}}={\binom{a+b-1}{b-1}}={\binom{a+b-1}{a}}$

当 $\min(a-1,b-1)=a-1$ 时，$\sum_{i=0}^{a-1}{\binom{a-1}{a-1-i}}{\binom{b}{i+1}}=\sum_{i=0}^{a}{\binom{a-1}{a-1-i}}{\binom{b}{i+1}}={\binom{a+b-1}{a}}$

综上所述，对答案贡献为 $\binom{a+b-1}{a}$ ，可以 $O(n)$ 预处理，单次 $O(1)$ 计算。时间复杂度为 $O(n)$ 。

# luogu P7481 梦现时刻

​ 设 $f_{a,b}=\sum_{i=0}^{b}\binom{b}{i}\binom{n-i}{a}$ ，求 $⨁\limits_{i=1}^{m}⨁\limits_{j=1}^{m}f_{i,j}\bmod 998244353$ 的值。

​ $1\le n\le 10^9$ ，$1\le m\le 5000$

非常巧妙的一道推式子题，发现异或无法利用性质，故我们只能考虑递推出所有的 $f$ 值。

$$\begin{aligned} f_{a,b}&=\sum_{i=0}^{b}\binom{b}{i}\binom{n-i}{a}\\ &=\sum_{i=0}^{b}\binom{b-1}{i}\binom{n-i}{a}+\sum_{i=0}^{b}\binom{b-1}{i-1}\binom{n-i}{a}\\ &=f_{a,b-1}+\sum_{i=0}^{b-1}\binom{b-1}{i}\binom{n-i-1}{a}\\ &=f_{a,b-1}+\sum_{i=0}^{b-1}\binom{b-1}{i}\binom{n-i}{a}-\sum_{i=0}^{b-1}\binom{b-1}{i}\binom{n-i-1}{a-1}\\ &=f_{a,b-1}+f_{a,b-1}-\sum_{i=0}^{b-1}\binom{b}{i+1}\binom{n-i-1}{a-1}+\sum_{i=0}^{b-1}\binom{b-1}{i+1}\binom{n-i-1}{a-1}\\ &=2f_{a,b-1}-\sum_{i=1}^{b}\binom{b}{i}\binom{n-i}{a-1}+\sum_{i=1}^{b}\binom{b-1}{i}\binom{n-i}{a-1}\\ \end{aligned}$$

我们为了和题目的式子对应，我们将后面两个 $\sum$ 各补上一个 $i=0$ 的情况，我们会惊奇地发现：

$$\begin{aligned} ans&=2f_{a,b-1}-\sum_{i=1}^{b}\binom{b}{i}\binom{n-i}{a-1}+\sum_{i=1}^{b}\binom{b-1}{i}\binom{n-i}{a-1}\\ &=2f_{a,b-1}-f_{a-1,b}+f_{a-1,b-1}+\binom{n}{i-1}-\binom{n}{i-1}\\ &=2f_{a,b-1}-f_{a-1,b}+f_{a-1,b-1} \end{aligned}$$

至此我们可以递推求出所有的 $f$ ，然后我们考虑边界。发现 $f_{0,x}=\sum_{i=0}^{x}\binom{x}{i}=2^x$ ，$f_{x,0}=\binom{n}{x}=\frac{n!}{(n-x)!x!}$ ，均可以 $O(m)$ 预处理出来，然后递推求答案即可。时间复杂度 $O(m^2)$ 。

# 容斥原理 / 二项式反演

# 错排数

我们设 $f_n$ 表示恰好有 $n$ 个位置错开，$g_n$ 表示最多 $n$ 个位置错开。易知 $g_n$ 为全部的排列，即 $g_n=n!$ ，直接二项式反演得到 $f_n=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}g_i=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}i!$ 。

# [HAOI2008] 硬币购物

​ 题意：有 $4$ 种硬币面值分别为 $c_1,c_2,c_3,c_4$ 。共有 $T$ 组询问，每次询问给定 $lim_1,lim_2,lim_3,lim_4,tot$ ，询问在第 $i$ 种硬币数量不大于 $lim_i$ 的前提下凑出总价值为 $tot$ 的方案数。

​ $1\le T\le 1000$ ，$1\le c_i, lim_i,tot\le 10^5$

非常巧妙的一道题。考虑先做一个完全背包预处理出没有任何限制时凑出价值为 $i$ 的方案数 $f_i$ 。对于四个限制，我们可以考虑经典容斥，没有限制减去一个限制加上两个限制减去三个限制再加上四个限制。以一个限制为例，我们需要减去使用超过 $lim_i$ 个 $c_i$ 的方案数，那我们可以强制先用 $(lim_i+1)$ 个 $c_i$ ，设剩下的价值为 $p$，那么 $f_p$ 都是不满足限制的，需要减去，剩下的情况同理计算即可。时间复杂度为 $O(4n+16T)$ ，其中 $n$ 表示 $tot$ 的最大值。

# [CSP-S2019] Emiya 家今天的饭

​ 题意：有 $n$ 种烹饪方法和 $m$ 种食材，每道菜对应一种烹饪方法和一种食材，并且用第 $i$ 种烹饪方法和第 $j$ 种食材做出的菜种类数为 $a_{i,j}$ 。求满足 1. 至少做一道菜 2. 每道菜的烹饪方法互不相同 3. 每种食材最多在一半的菜中使用 的搭配方案数对 $998244353$ 取模的结果。

​ $1\le n\le 100$ ，$1\le m\le 2000$

很巧妙的一道计数 $dp$ 。发现不符合食材限制的最多有一种，所以直接枚举这一种不符合的食材。所以考虑容斥，先计算总方案数，比较简单，设 $s_i=\sum_{j=1}^{n}a_{i,j}$ ，再设 $f_{i,j}$ 表示前 $i$ 种菜中共选了 $j$ 种食材的方案数，直接转移 $f_{i,j}=f_{i-1,j}+s_i\times f_{i-1,j-1}$ ，总方案数为 $\sum_{i=1}^{n}f_{n,i}$ 。然后考虑减去不符合限制的，假如当前枚举到不符合食材的是 $p$ ，设 $g_{i,j,k}$ 表示前 $i$ 行选了 $p$ 食材 $j$ 次，其他食材 $k$ 次的方案数，根据选不选 $p$ 食材直接转移 $g_{i,j,k}=g_{i-1,j,k}+a_{i,p}\times g_{i-1,j-1,k}+(s_i-a_{i,p})\times g_{i-1,j,k-1}$ ，但这样时间复杂度为 $O(mn^3)$ ，考虑优化。发现 $j,k$ 的具体值我们并不关心，只关心相对大小，所以我们设 $g_{i,j}$ 表示前 $i$ 行选了 $p$ 食材次数减不选的次数为 $j$ 的方案数，转移为 $g_{i,j}=g_{i-1,j}+a_{i,p}\times g_{i-1,j-1}+(s_i-a_{i,p})\times g_{i-1,j+1}$ ，但是由于第二维可能是负的，所以我们直接同时加上 $n$ ，最后统计 $\sum_{i=1}^{n}g_{n,n+i}$ 就是要减去的情况。最终时间复杂度为 $O(mn^2)$ 。