有人问，组合数学不是就一些简单的公式吗？不是的，其实组合数学是数学中的一个非常庞大的分支，接下来就举一些例子。（更新中）
本文主要讲各种数据范围下，求组合数的方式；以及球盒模型各种情况下的公式；最后是一些球盒模型的扩展情况。
（下面部分标题里的LaTeX公式更新后炸了，就凑合着看吧）
求组合数
以下所有范围都可以当成是以下题目的某个Subtask：
给你 $p$，代表模数。
之后会给你一个 $q$，代表询问次数。
每次询问给定 $n$ 和 $m$，问 $C_n^m \bmod p$ 的值。
下面不给定 $q$ 的范围，因为不重要。
以下全部默认 $n \geq m$。
范围1：$n,m \leq 2000,p \leq 10^9+7$
先递推预处理，然后直接回答询问即可。
递推式：$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$。
- 预处理复杂度：$O(n^2)$
- 查询复杂度：$O(1)$
范围2：$n,m \leq 10^6,p \leq 10^9+7,p\text{ is prime}$
1
先预处理阶乘，然后直接回答询问即可。
回答询问式：$C_n^m=\dfrac{n!}{m!(n-m)!}$。
为了节省时间复杂度，此处还可以预处理一下阶乘的逆元。
2
- 预处理复杂度：$O(n)$
- 查询复杂度：$O(1)$
范围3：$n,m \leq 10^6,p \leq 10^9+7$
1
可以发现，范围2与范围3唯一的不同就是，范围3把质数的条件去掉了。
而把质数的条件后，就没法求逆元了，因为逆元可能不存在。
所以我们考虑换做法。
2
我们考虑把模数做个质因数分解，变成 ${p_1}^{a_1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times \dots \times {p_k}^{a_k}$。
然后，我们求出 $c$ 数组，$c_i=C_n^m \bmod {p_i}^{a_i}$，然后就可以列出以下方程：
$ \begin{cases} x \equiv c_1 \pmod{{p_1}^{a_1}} \ x \equiv c_2 \pmod{{p_2}^{a_2}} \ x \equiv c_3 \pmod{{p_3}^{a_3}} \ \dots \ x \equiv c_k \pmod{{p_k}^{a_k}} \end{cases} $
用中国剩余定理即可求出上述方程的最小正整数解 $x$，输出这个 $x$ 即可。
3
接下来考虑一下如何求 $c$ 数组。
我们设当前要求 $C_n^m \bmod q^a$。
那么，我们把 $C_n^m$ 展开为阶乘形式，变成 $\dfrac{n!}{m!(n-m)!}$。
然后，我们想，$C_n^m \bmod p$ 不能直接求的原因其实就是因为上述式子可能不会与 $p$ 互质。
进而，$C_n^m \bmod q^a$ 不能直接求的原因也是因为上述式子可能不会与 $q^a$（其实也是 $q$）互质。
所以，我们就把上述式子里（那个分数的分子和分母内）所有的 $q$ 都去掉，变成 $\Large \dfrac{\frac{n!}{q^x}}{\frac{m!}{q^y}\frac{(n-m)!}{q^z}} \times q^{x-y-z}$，其中 $x$、$y$、$z$ 就是 $n!$、$m!$、$(n-m)!$ 中含有的 $q$ 质因子数量。
这个式子中的 $\dfrac{n!}{q^x}$ 是可以直接预处理的，此处略。
由于分母中的两项都没有 $q$ 质因子，所以就有在模 $q^a$ 意义下的逆元，前项的分数可求；后项就是一个快速幂，可求。
4
这里再说最后一点细节，就是我们设 $f_n=\dfrac{n!}{q^x}$，那么 $f_i=f_{i-1} \times i \div q^c$（虽说这个式子中有除号，但显然不需要逆元），其中 $c$ 是 $i$ 含有的 $q$ 质因子个数。
这个公式中存在一个 $i \div q^c$，这可以暴力计算，但需要多带一个 $\log$。
但这其实不用带这个 $\log$，我们可以先处理出来一个 $g$ 数组，$g_i=i \div q^c$，这个 $g$ 数组很好递推：
- $i \bmod q=0$：$g_i=g_{i \div q}$
- $i \bmod q \not= 0$：$g_i=i$
有了这个 $g$ 数组，$f$ 数组的递推方程就变成了 $f_i=f_{i-1} \times g_i$，递推复杂度也变成了 $O(n)$。
5
- 预处理复杂度：$O(\sqrt{n}+n \log p)$，其中，$\sqrt{p}$ 为求出 $p$ 的唯一分解复杂度，$\log p$ 为枚举 $p$ 的所有唯一分解项复杂度，以下所有复杂度内的 $\sqrt{p}$、$\log p$ 都默认是这个意思。
- 查询复杂度：$O(\log^2 p)$，其中一个 $\log p$ 是枚举 $p$ 的所有唯一分解项复杂度，另外一个则是求逆元的复杂度。
范围4：$n,m \leq 10^6,p \leq 10^9+7$
1
这里提供范围3的另外一种做法。
其实很简单，我们只用把 $C_n^m$ 表示为 $2^? \times 3^? \times 5^? \times \dots$ 的形式即可。
有人问，这个质数要枚举到多少呢？其实显然最多只用枚举到 $n$。
实现这个做法可以借助一个函数ci(n,p)代表 $n!$ 的唯一分解中，$p$ 的指数是多少，这个函数可以用奥数知识，在 $\log_p n$ 的复杂度内求出。
细节不用多说。
2
- 预处理复杂度：$O(n)$
- 查询复杂度：$O(\text{prime}(n) \times \log n)$，其中 $\text{prime}(n)$ 代表 $n$ 及以内的质数个数，约为 $n \div \ln(n)$，以下所有 $\text{prime}$ 函数都是这个意思；$\log n$ 为
ci函数的上界复杂度。
范围5：$n \leq 10^{18},m \leq 10^6,p \leq 10^9+7,p\text{ is prime}$
1
注意到 $m \leq 10^6$，所以我们就直接用公式 $C_n^m=\dfrac{n \times (n-1) \times (n-2) \times \dots \times (n-m+1)}{1 \times 2 \times 3 \times \dots \times m}$，配合逆元求解即可。
2
- 预处理复杂度：无
- 查询复杂度：$O(m \log p)$，其中 $\log p$ 为算逆元的时间复杂度。
范围6：$n \leq 10^{18},m \leq 10^6,p \leq 10^9+7$
1
注意到 $p$ 没有保证是质数，所以分母内的那些项没有逆元。
但我们还可以用与范围3的做法1相似的做法去做。
具体地，我们先分解 $p$，然后对于唯一分解内的每一项 $q^a$，先求出 $n \times (n-1) \times (n-2) \times \dots \times (n-m+1) \bmod q^a$。
然后循环每个 $i \in [1,m]$，把 $i$ 中的 $q$ 都除尽，此时就可以求 $i$ 在模 $q^a$ 意义下的逆元了，直接更新答案即可。
2
- 预处理复杂度：$O(m \log p)$
- 查询复杂度：$O(\log^2 p)$，该复杂度解释见范围3的做法1的同地（同一个地方）。
范围7：$n,m \leq 10^{18},p \leq 10^6+3,p\text{ is prime}$
1
直接Lucas定理即可。
2
- 预处理复杂度：$O(p)$
- 查询复杂度：$O(\log m)$
范围8：$n,m \leq 10^{18},p \leq 10^6+3$
1
直接exLucas定理即可。
2
- 预处理复杂度：$O(\sqrt{p})$
- 查询复杂度：$O(\log p \log n+\log^2 p)$，其中第一个 $\log p$ 为枚举 $p$ 的所有唯一分解项复杂度，$\log n$ 为
ci函数/f函数复杂度，第二个 $\log p$ 为CRT内枚举方程复杂度，第三个 $\log p$ 为CRT内求逆元的复杂度。
范围9：$n,m \leq 10^{18},p \leq 10^9+7$
1
这个数据范围需要利用高阶多项式的知识，参考这里
2
- 预处理复杂度：未知
- 查询复杂度：未知
组合数模型：球盒模型
参考：
统一设 $n$ 为球的个数，$m$ 为盒子的个数。
在情况 $i$ 内，$f_i(n,m)$ 为这种情况下，如果球数为 $n$、盒子数为 $m$，方案数是多少。
情况1：球相同，盒相同，允许为空
这种情况下无法直接求，需要递推。
接下来考虑转移 $f_1(n,m)$：
- $n=0$：$f_1(n,m)=1$
- $m=0$：$f_1(n,m)=0$
- $n<m$：首先必然会有 $m-n$ 个盒子是空的，其次由于盒子两两相同，所以可以任意指定哪些格子为空，即 $f_1(n,m)=f_1(n,n)$
- $n \geq m$：
- 如果所有盒子都不为空：我们可以先在每个格子里拿出一个球，即 $f_1(n,m)
\text{+=}f_1(n-m,m)$ - 否则：我们就随便指定一个格子，设这个格子为空，即 $f_1(n,m)
\text{+=}f_1(n,m-1)$
- 如果所有盒子都不为空：我们可以先在每个格子里拿出一个球，即 $f_1(n,m)
情况2：球相同，盒相同，不允许为空
这种情况下可以直接求。
具体地，设要求 $f_2(n,m)$。
那么我们考虑，其实情况1和情况2就一个区别，情况1允许为空，情况2不允许。
所以我们就可以先在所有盒子内都拿出一个球，保证都非空后，就转化为了情况1，即 $f_2(n,m)=f_1(n-m,m)$。
但注意，当 $n<m$ 时，方案数为 $0$。
情况3：球相同，盒不同，允许为空
其实就是在问 $x_1+x_2+x_3+\dots+x_m=n$ 的非负整数解的个数。
由于是非负整数，所以我们要先把所有的 $x_i$ 加 $1$，就变成了问 $x_1+x_2+x_3+\dots+x_m=n+m$ 的正整数解的个数。
上述问题可以用插板法解决，答案为 $f_3(n,m)=C_{n+m-1}^{m-1}$。
情况4：球相同，盒不同，不允许为空
其实就是在问 $x_1+x_2+x_3+\dots+x_m=n$ 的正整数解的个数。
上述问题可以用插板法解决，答案为 $f_4(n,m)=C_{n-1}^{m-1}$。
情况5：球不同，盒相同，允许为空
（请先阅读情况6）
1
有了情况6的铺垫，这里就变得简单了。
我们可以考虑枚举空出来的盒子数 $i$（$0 \leq i \leq m$），然后 $f_5(n,m) \text{+=} f_6(n,m-i)$。
即，$f_5(n,m)=\sum\limits_{i=0}^m f_6(n,m-i)$。
很好懂。
2
但这里也顺便说一下 $n \leq m$ 时的另一种做法——求贝尔数。
首先，由于盒子都相同，所以其实答案与 $m$ 无关。
所以，如论是什么 $n$、$m$，只要 $n \leq m$，那么就转化为了，有 $n$ 个不同的球，放入 $n$ 个相同的盒子，每个盒子都允许为空，问方案数。
一个结论就是，若设 $b_i$ 为 $n=i,m \geq n$ 时的答案，即 $b_n=f_5(n,n)$。
那么，$b_n=\sum\limits_{i=0}^{n-1} C_{n-1}^i b_i$。
（$n=0$ 的情况直接特判，$b_0=1$）
接下来解释一下这个公式。
我们枚举的这个 $i$ 其实就是代表着，我们假设球 $n$ 所在盒子里有放了 $n-i$ 个球（包括球 $n$）。
注意到，在这个公式内，$n-i$ 的范围是 $[1,n]$，而不是 $[0,n]$，因为 $n$ 所在盒子显然要至少包含一个球。（废话）
有人问，为啥要枚举球 $n$ 所在盒子里的球数，而不是任意盒子里的球数？因为后者很容易计重，而前者肯定不会计重，也不会计漏，显然。
然后，我们就忽略那个有球 $n$ 的、放了 $n-i$ 个球的盒子，剩下的盒子里的球的总数就是 $i$ 了。
显然，$i$ 个球最多涉及 $i$ 个盒子，所以那 $i$ 个球的放置方案数就是 $b_i$。
但注意到，球是不同的，所以我们还要额外加一个选择（那 $i$ 个球）的方案数作为系数。
由于 $n$ 号球已经被确定不会被放在那 $i$ 个盒子里了，所以其实只有 $n-1$ 个球可以被选择并放入那 $i$ 个盒子中。
于是就得到了上述公式。
情况6：球不同，盒相同，不允许为空
其实就是第二类斯特林数，又写作 $n \brace m$。
其实转移很好想，一种就是当前元素单立一个集合，另一种就是加入到以前的某个集合。
即 $f_6(n,m)=f_6(n-1,m-1)+f_6(n-1,m) \times m$。
还是，如果 $n<m$，方案数为 $0$。
情况7：球不同，盒不同，允许为空
由于球、盒都不同，所以我们就可以分别去考虑每个球去哪个盒里了。
由于球的选择互相独立，所以可以直接用乘法原理乘起来。
由于允许为空，所以没有其他限制。
综上所述，$f_7(n,m)=m^n$。
情况8：球不同，盒不同，不允许为空
该情况与情况6的唯一区别就在于，盒子是两两不同的。
所以，我们可以直接拿情况6里的答案，乘上 $m!$ 返回即可。
综上所述，$f_8(n,m)=f_6(n,m) \times m!$。
球盒模型主要情况总结
情况1：球相同，盒相同，允许为空 ：- $n=0$：$f_1(n,m)=1$
- $m=0$：$f_1(n,m)=0$
- $n<m$：$f_1(n,m)=f_1(n,n)$
- $n \geq m$：$f_1(n,m)=f_1(n-m,m)+f_1(n,m-1)$
情况2：球相同，盒相同，不允许为空 ：- $n<m$：$f_2(n,m)=0$
- $n \geq m$：$f_2(n,m)=f_1(n-m,m)$
情况3：球相同，盒不同，允许为空 ：- 任何情况：$f_3(n,m)=C_{n+m-1}^{m-1}$
情况4：球相同，盒不同，不允许为空 ：- $n<m$：$f_4(n,m)=0$
- $n \geq m$：$f_4(n,m)=C_{n-1}^{m-1}$
情况5：球不同，盒相同，允许为空 ：- 任何情况：$f_5(n,m)=\sum\limits_{i=0}^m f_6(n,m-i)$
情况6：球不同，盒相同，不允许为空 ：- $n<m$：$f_6(n,m)=0$
- $n \geq m$：$f_6(n,m)=f_6(n-1,m-1)+f_6(n-1,m) \times m$
情况7：球不同，盒不同，允许为空 ：- 任何情况：$f_7(n,m)=m^n$。
情况8：球不同，盒不同，不允许为空 ：- $n<m$：$f_8(n,m)=0$
- $n \geq m$：$f_8(n,m)=f_6(n,m) \times m!$
组合数模型：球盒模型拓展
参考：
统一设 $n$ 为球的个数，$m$ 为盒子的个数。
在情况 $i$ 内，$g_i(n,m)$ 为这种情况下，如果球数为 $n$、盒子数为 $m$，方案数是多少。
（若有更多限制，可以在最后加另外参数）
拓展情况1：球相同，盒相同，不允许为空，至少 $t$ 个球
1
考虑DP。
由于球、盒都相同，所以可以将问题转化成数划分问题。
具体地，这个问题可以被转化成，数 $n$ 拆成刚好 $m$ 个数相加，且每个数至少为 $t$ 的方案数
定义状态 $d_{i,j,k}$ 代表数 $i$ 拆成刚好 $j$ 个数相加，且每个数至少为 $k$ 的方案数。
转移就枚举拆分里的某一项的值 $x$，从 $k$ 到 $n$，然后就转移到了状态 $d_{i-x,j-1,x}$。
其中，为了防止计重，最后一维要是 $x$ 而不是 $k$。
综上所述，$d_{i,j,k}=\sum\limits_{x=k}^n d_{i-x,j-1,x}$，$g_1(n,m,t)=d_{n,m,t}$。
最后，说一些边界：
- $n=0,m=0$：$g_1(n,m,t)=1$
- $n=0$：$g_1(n,m,t)=1$
- $m=0$：$g_1(n,m,t)=0$
- $n<m \times t$：$g_1(n,m,t)=0$
2
（下述做法还不能被证明完全正确，仅为参考）
首先，还是判断上面那些边界。
判断完边界后，就可以完全忽略“不允许为空”的限制了。
我们考虑事先在每个盒子里都拿走 $t$ 个球，然后就转化为了 $n-m \times t$ 个球，$m$ 个盒，球、盒都相同，盒允许为空，问方案数。
就是情况1的问题，直接调用即可。
综上所述，$g_1(n,m,t)=f_1(n-m \times t,m)$。
拓展情况2：球相同，盒不同，不允许为空，盒 $i$ 至少 $a_i$ 个球
（如果说存在某个 $a_i$ 是小于 $1$ 的，直接将其设为 $1$）
与模型3的唯一差别就在于这里有每个盒子内球个数的下界限制。
但球还是两两相同的，所以我们考虑事先在第 $i$ 个格子里放 $a_i$ 个球。
剩下的工作就交给模型3了。
注意，在初始放完之后，某个格子可能会出现说不再放任何球的情况，所以应该转化成模型3而不是模型4。
综上所述，$g_2(n,m,a)=f_3(n-\sum a_i,m)$。
但如果 $n<\sum a_i$，是无解的，显然。
拓展情况3：球相同，盒不同，允许为空，至多 $t$ 个球
该情况需要用到生成函数，生成函数学习笔记网页及本模型做法见这里的模型2B。
拓展情况4：球相同，盒不同，允许为空，至多 $1$ 个球，非空盒不可相邻
（说一个细节，题目中说的“非空盒不可相邻”指的是如果给所有盒子依次赋予 $1 \sim m$ 内的编号，那么按编号顺序排成一列后，非空盒不可相邻）
易得只有在 $2n-1 \leq m$ 的时候才有解，其中 $2n-1$ 代表 $n$ 个球如果一隔一（第一个格子里放一个球，第二个格子不放，第三个放，第四个不放，以此类推）地放，需要用多少个盒子才能满足条件；同时 $2n-1$ 也是这个 $n$ 对应的 $m$ 的下限。
接下来考虑有解情况。
（以下暂时忽略编号，在构造完一个方案后按排列顺序依次编号）
首先，我们在 $m$ 个盒子里选 $n$ 个盒子，并从盒子的集合中删去这 $n$ 个盒子（下称“第一步”），每个被选的盒子里都恰好放置 $1$ 个球，所有球都放完了。（注意，此处的选择方案不能被计算到答案中）
但这里不能直接考虑剩下 $m-n$ 个盒子要放到什么位置，因为不好处理。
具体地，我们遇到这种情况都是把最初两两盒子内的间隙（包括两旁）看成盒子，把盒子看成球。
但你会发现，这 $n+1$ 个盒子中有 $n-1$ 个盒子要求不为空，另外两个盒子不要求，所以不好求。
那咋解决呢？很简单，我们只用在那 $n-1$ 个盒子内全部事先拿一个球出来即可，即再选 $n-1$ 个盒子插入原本的 $n$ 个盒子的间隙中，并将这 $n-1$ 个格子从盒子集合中移除（下称“第二步”）。
所以，最后一共就有 $m-n-(n-1)=m-2n+1$（前项 $m-n-(n-1)$ 中，第一个 $-n$ 是第一步的影响；第二个 $-(n-1)$ 则是第二步的影响）个球，$n+1$ 个盒子，所以最终答案就是 $f_4(m-2n+1,n+1)$。
球盒模型扩展主要情况总结
拓展情况1：球相同，盒相同，不允许为空，至少 $t$ 个球 ：- $n=0,m=0$：$g_1(n,m,t)=1$
- $n=0$：$g_1(n,m,t)=1$
- $m=0$：$g_1(n,m,t)=0$
- $n<m \times t$：$g_1(n,m,t)=0$
- 其他情况：$g_1(i,j,k)=\sum\limits_{x=k}^n g_1(i-x,j-1,x)$
拓展情况2：球相同，盒不同，不允许为空，盒 $i$ 至少 $a_i$ 个球 ：- 如果说存在某个 $a_i$ 是小于 $1$ 的，直接将其设为 $1$。
- $n<\sum a_i$：$g_2(n,m,a)=0$
- 其他情况：$g_2(n,m,a)=f_3(n-\sum a_i,m)$
拓展情况3：球相同，盒不同，允许为空，至多 $t$ 个球 ：- 该情况需要用到生成函数，生成函数学习笔记网页及本模型做法见这里的模型2B。
拓展情况4：球相同，盒不同，允许为空，至多 $1$ 个球，非空盒不可相邻 ：- *注：题目中说的“非空盒不可相邻”指的是如果给所有盒子依次赋予 $1 \sim m$ 内的编号，那么按编号顺序排成一列后，非空盒不可相邻。
- $2n-1>m$：$g_4(n,m)=0$
- 其他情况：$g_4(n,m)=f_4(m-2n+1,n+1)$