排列
排列的定义与基本性质
定义 设一个集合 \(S\) 中有 \(n\) 个元素，从中有序地取出 \(m(0\leq m \leq n)\) 个元素排成一列， 称为 \(S\) 的一个 \(m\) 排列。两个排列相同，当且仅当元素相同且顺序相同。我们记 \(\text{P}_n^m\) 、 \(\text{A}_n^m\) 或 \(\text{P}(n,m)\) 表示 \(S\) 中 \(m\) 排列的总数。
约定 当 \(m>n\) 时，\(\text{P}_n^m = 0\) 。
全排列的定义 设一个集合 \(S\) 中有 \(n\) 个元素，其 \(n\) 排列称为全排列。
- C++中，
next_permutation函数可以按字典序从小到大遍历数据的全排列，prev_permutation函数与之相反。
性质1 \(\mathrm{P}_n^m = n(n-1)(n-2)\cdots(n-m+1) = \dfrac{n!}{(n-m)!}\) ，其中 \(0\leq m \leq n\)。
性质2 \(\text{P}_n^m = n\text{P}_{n-1}^{m-1}\) 。
性质3 \(\text{P}_n^m = m \text{P}_{n-1}^{m-1} + \text{P}_{n-1}^{m}\) 。
性质1的证明：
考虑乘法原理，按顺序选数，第 \(i(1\leq i\leq m)\) 个数有 \(n-i+1\) 种选法，乘在一起可得原式。
性质2的证明：
考虑乘法原理，第一个数有 \(n\) 种选法，再从剩下的 \(n-1\) 个数里选 \(m-1\) 个有 \(\text{P}_{n-1}^{m-1}\) 种排列，所以 \(\text{P}_n^m = n\text{P}_{n-1}^{m-1}\) 。
性质3的证明：
考虑加法原理，考虑分两类：
- 先指定选一个元素，有 \(m\) 个位置可放，再从剩下 \(n-1\) 元素中选 \(m-1\) 个有 \(\text{P}_{n-1}^{m-1}\) 种排列。
- 不选1指定的元素，从其他 \(n-1\) 元素里选 \(m\) 个，共 \(\text{P}_{n}^{m-1}\) 种排列。
因此 \(\text{P}_n^m = m \text{P}_{n-1}^{m-1} + \text{P}_{n-1}^{m}\) 。
错位排列
错位排列的定义与基本性质
定义 设 \(P=(p_1,p_2,\cdots,p_n)\) 是 \(S=\{1,2,\cdots,n\}\) 的一个排列，若对于任意的 \(i \in[1,n]\) 满足 \(p_i \neq i\) ，则称 \(P\) 是 \(S\) 的一个错位排列。我们记 \(D_n\) 表示 \(S\) 的错位排列的总数。
性质1 \(D_n\) 有递推公式
性质2 \(D_n\) 有通项公式 \(\displaystyle D_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}\) 。
性质3 \(D_n\) 有简单表达式 \(D_n = \left\lfloor \dfrac{n!}{\text{e}} \right\rfloor\) 。
性质4 \(\{1,2,\cdots ,n \}\) 的排列是错位排列的概率 \(P_n\) 有渐进 \(\lim_\limits{n \to \infty} P_n = \lim_\limits{n \to \infty} \dfrac{D_n}{n!} = \dfrac{1}{\text{e}}\) ，表明 \(D_n\) 的增长率与 \(n!\) 仅相差常数倍。
性质1的证明：
考虑加法原理，设 \(n\) 出现在位置 \(k(1\leq k\leq n-1)\) ，有两种情况：
- \(k\) 一定出现在位置 \(n\) ，那么除去 \(k,n\) 剩下 \(n-2\) 个数错排即可，共计 \(D_{n-2}\) 。
- \(k\) 不能出现在位置 \(n\) ，那么可把位置 \(n\) 视作 \(k\) 的新位置与除了 \(n\) 的数进行错排，共计 \(D_{n-1}\) 。
因此再根据乘法原理，有 \(D_n = (n-1)(D_{n-1}+D_{n-2})\) 。
性质2的证明：
考虑减法原理，设全集 \(U\) 为 \([1,n]\) 的全排列，则 \(|U| = n!\) ，设满足 \(p_i \neq i\) 的排列的集合为 \(S_i\) ，那么满足 \(p_i = i\) 的集合为 \(\overline{S_i}\) ，那么有 \(\displaystyle \left| \bigcap_{i=1}^n S_i \right| = |U| - \left| \bigcup_{i=1}^n \overline{S_i} \right|\) ，问题转换为求 \(\displaystyle \left| \bigcup_{i=1}^n \overline{S_i} \right|\) 。
考虑容斥原理，有 \(\displaystyle \left| \bigcup_{i=1}^n S_i\right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1<i_2< \cdots < i_k \leq n} \left| \bigcap_{j=1}^k S_{i_j} \right|\) ，其中 \(\displaystyle \left| \bigcap_{j=1}^k S_{i_j} \right|\) 为所有 \(i \in T\) 满足 \(p_i = i\) 的排列数，显然为 \((n-k)!\) ，对于 \(1\leq i_1 < i_2 < \cdots < i_k < n\) 共有 \(\dbinom{n}{k}\) 种方案，因此 \(\displaystyle \left| \bigcup_{i=1}^n S_i\right| = \sum_{k=1}^n (-1)^{k-1} \binom{n}{k}(n-k)! = \sum_{k=1}^n (-1)^{k-1} \frac{n!}{k!}\) 。
最后，错位排列数 \(\displaystyle \left| \bigcap_{i=1}^n S_i \right| = |U| - \left| \bigcup_{i=1}^n \overline{S_i} \right| = n! - \sum_{k=1}^n (-1)^{k-1} \frac{n!}{k!} = n!\sum_{k=0}^n \frac{(-1)^k}{k!}\) 。
圆排列
圆排列的定义与基本性质
定义 设一个集合 \(S\) 中有 \(n\) 个元素，从中有序地取出 \(m(0\leq m \leq n)\) 个元素排成不分首尾围成一圈， 称为 \(S\) 的一个 \(m\) 圆排列。两个圆排列相同，当且仅当元素相同且不分首位地顺序相同。我们记 \(\text{Q}_n^m\) 表示 \(S\) 的 \(m\) 圆排列的总数。
性质1 \(\text{Q}_n^m = \dfrac{\text{P}_n^m}{m}\) 。
性质1的证明：
对于每一种圆排列，我们可以规定首尾使其变成标准排列，共有 \(m\) 种首尾方案，因此有 \(\text{Q}_n^m \cdot m = \text{P}_n^m\) ，所以 \(\text{Q}_n^m = \dfrac{\text{P}_n^m}{m}\) 。
多重集排列
多重集排列的定义与基本性质
定义 设多重集 \(S = \{n_1 \cdot a_1,n_2 \cdot a_2,\cdots ,n_k \cdot a_k\}\) ，从中任选 \(m\) 个元素组成排列，称为 \(S\) 的 \(m\) 排列。
多重组合数的定义 设多重集 \(S = \{n_1 \cdot a_1,n_2 \cdot a_2,\cdots ,n_k \cdot a_k\}\) ， \(n = \displaystyle \sum_{i=1}^k n_i\) ，则 \(S\) 的 \(n\) 排列（即全排列）的总数称为多重组合数，记为 \(\dbinom{n}{n_1,n_2,\cdots ,n_k}\) 。
性质1 设多重集 \(S = \{n_1 \cdot a_1,n_2 \cdot a_2,\cdots ,n_k \cdot a_k\}\) ，\(n = \displaystyle \sum_{i=1}^k n_i\) ，则全排列数为 \(\dbinom{n}{n_1,n_2,\cdots ,n_k} = \dfrac{n!}{\displaystyle \prod_{i=1}^k n_i!}\) 。
性质2 设多重集 \(S = \{n_1 \cdot a_1,n_2 \cdot a_2,\cdots ,n_k \cdot a_k\}\) ，若 \(m\) 满足 \(m \leq n \leq +\infty(1\leq i\leq k)\) ，则 \(m\) 排列数为 \(k^m\) 。
性质1的证明：
不考虑元素重复的全排列为 \(n!\) ，再对每个元素的全排列 \(n_i!(1\leq i\leq k)\) 去重，所以 \(\dbinom{n}{n_1,n_2,\cdots ,n_k} = \dfrac{n!}{\displaystyle \prod_{i=1}^k n_i!}\) 。
性质2的证明：
因为选 \(m\) 个小于等于任意元素的个数，所以每次都能选 \(k\) 个元素，因此总数为 \(k^m\) 。
组合
组合的定义与基本性质
定义 设一个集合 \(S\) 中有 \(n\) 个元素，从中无序地取出 \(m(0\leq m \leq n)\) 个元素组成集合， 称为 \(S\) 的一个 \(m\) 组合。两个组合相同，当且仅当元素相同。我们记 \(\text{C}_n^m\) 、 \(\dbinom{n}{m}\) 或 \(\text{C}(n,m)\) 表示 \(S\) 中 \(m\) 组合的总数。
约定 当 \(m>n\) 时，\(\dbinom{n}{m} = 0\) 。
性质1 \(\dbinom{n}{m} = \dfrac{\text{P}_n^m}{m!} = \dfrac{n!}{m!(n-m)!}\) 。
性质2 \(\dbinom{n}{m} = \dbinom{n}{n-m}\) 。
性质3 \(\dbinom{n}{m} = \dfrac{n-m+1}{m} \dbinom{n}{m-1}\) 。
性质4 \(\dbinom{n}{m} = \dfrac{n}{m} \dbinom{n-1}{m-1}\) 。
性质5（杨辉三角） \(\dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1}\) 。
性质6 \(\displaystyle \sum_{i=0}^n \binom{i}{m} = \binom{n+1}{m+1}\) 。
性质7 \(\dbinom{n}{m} \dbinom{m}{k} = \dbinom{n}{k} \dbinom{n-k}{m-k}\) 。
性质8 \(\displaystyle \sum_{i=0}^n \binom{n-i}{i} = F_{n+1}\) ，其中 \(F\) 是斐波那契数列。
性质1的证明：
先考虑顺序得到的总数为 \(m\) 排列数 \(\text{P}_n^m\) ，而对于一种 \(m\) 组合有 \(m!\) 种排列方式，所以 \(m!\dbinom{n}{m} = \text{P}_n^m\) ，因此根据排列性质1可得 \(\dbinom{n}{m} = \dfrac{\text{P}_n^m}{m!} = \dfrac{n!}{m!(n-m)!}\) 。
性质2的证明：
方法1：
由性质1易得。
方法2：
\(n\) 个里选 \(m\) 个组合，等价于 \(n\) 个里选 \(n-m\) 不在组合。
性质5的证明：
方法1：
由性质1易得。
方法2：
画出杨辉三角，由数学归纳法易得。
方法3：
指定一个元素，如果一定不选它则有 \(\dbinom{n-1}{m}\) 种组合，如果一定选它则有 \(\dbinom{n-1}{m-1}\) 种组合，考虑加法原理，得证。
性质6的证明：
方法1：
根据性质5可得
\[\begin{aligned} \sum_{i=0}^n \binom{i}{m} &= \sum_{i=m}^n \binom{i}{m} \\ &= \binom{m+1}{m+1} + \binom{m+1}{m} + \binom{m+2}{m} +\cdots + \binom{n}{m} \\ &= \binom{m+2}{m+1} + \binom{m+2}{m} + \cdots + \binom{n}{m} \\ &= \binom{m+3}{m+1} + \cdots + \binom{n}{m}\\ &= \binom{n+1}{m+1} \end{aligned} \]方法2：
从 \([0,n]\) 的整数中选出 \(m+1\) 个数的组合数为 \(\dbinom{n+1}{m+1}\) ，在这些组合中最大数为 \(i(0\leq i\leq n)\) 的组合数为 \(\dbinom{i}{m}\) ，考虑加法原理得证。
性质7的证明：
方法1：
由性质1可得
\[\begin{aligned} \binom{n}{m} \binom{m}{k} &= \frac{n!}{m!(n-m)!} \cdot \frac{m!}{k!(m-k)!} \\ &= \frac{n!}{k!} \cdot \frac{1}{(m-k)!(n-m)!} \\ &= \frac{n!}{k!(n-k)!} \cdot \frac{(n-k)!}{(m-k)!(n-m)!} \\ &= \binom{n}{k} \binom{n-k}{m-k} \\ \end{aligned} \]方法2：
左式是正着选，从 \(n\) 个元素中选 \(m\) 个，对于每个 \(m\) 组合再选 \(k\) 个的 \(k\) 组合的总数的总和。
右式是倒着选，先从 \(n\) 个元素中选 \(k\) 个，对于每个 \(k\) 组合从剩下 \(n-k\) 个元素中再选 \(m-k\) 个元素，代表这个 \(k\) 组合会被所有 \(m\) 组合选到的次数，最后总和与左式意义等价。
性质8的证明：
设 \(G_n = \displaystyle \sum_{i=0}^n \binom{n-i}{i}\) ，则 \(G_0 = 1 = F_1,G_1 = 1 = F_2\) 。
假设当 \(n = k+1(k\geq 0)\) 时， \(G_k = F_{k+1},G_{k+1} = F_{k+2}\) 成立。
那么当 \(n = k+2\) 时，由性质5可得
\[\begin{aligned} G_{k}+G_{k+1} &= \sum_{i = 0}^k \binom{k-i}{i} + \sum_{i = 0}^{k+1} \binom{k+1-i}{i} \\ &= \sum_{i = 1}^{k+1} \binom{k-i+1}{i-1} + \sum_{i = 1}^{k+1} \binom{k+1-i}{i} + 1 \\ &= \sum_{i = 1}^{k+1} \left( \binom{k+1-i}{i-1} + \binom{k+1-i}{i} \right) + 1 \\ &= \sum_{i = 1}^{k+1} \binom{k+2-i}{i} + \binom{k+2}{0} + \binom{0}{k+2}\\ &= \sum_{i = 0}^{k+2} \binom{k+2-i}{i} \\ &= G_{k+2} \end{aligned} \]同时有 \(G_{k}+G_{k+1} = F_{k+1}+F_{k+2} = F_{k+3}\) ，因此 \(G_{k+1} = F_{k+2},G_{k+2} = F_{k+3}\) ，得证。
二项式定理
定理1（二项式定理） \(\displaystyle (x+y)^n = \sum_{i=0}^n \binom{n}{i}x^{n-i}y^i\) 。
-
推论1（定理1的推论） \(\displaystyle \sum_{i=0}^n \dbinom{n}{i} = 2^n\) 。
-
推论2（定理1的推论） \(\displaystyle \sum_{i=0}^n (-1)^{i}\dbinom{n}{i} = [n=0]\) 。
-
推论3（推论2的推论） \(\displaystyle \binom{n}{0} + \binom{n}{2} + \cdots = \binom{n}{1} + \binom{n}{3} + \cdots = 2^{n-1}\) ，其中 \(n \geq 1\) 。
定理2（扩展二项式定理） \(\displaystyle \left( \sum_{i = 1}^k x_i \right)^n = \sum_{n_1+n_2+\cdots + n_k = n} \binom{n}{n_1,n_2,\cdots ,n_k}\prod_{i = 1}^k x_i^{n_i}\) 。
广义组合数的定义 设 \(\alpha \in \R,m \in \N\) ，则 \(\displaystyle \binom{\alpha}{m} = \frac{\displaystyle \prod_{i = 0}^m(\alpha-i)}{m!}\) 。
定理3（广义二项式定理） \(\displaystyle (x+y)^\alpha = \sum_{i=0}^{\infty} \binom{\alpha}{i}x^{\alpha-i}y^i\) ，其中 \(\alpha \in \R\) 。
定理1的证明：
方法1：
当 \(n = 0\) 时显然得证。
假设当 \(n = k\) 时， \(\displaystyle (x+y)^k = \sum_{i=0}^k \binom{k}{i}x^{k-i}y^i\) 成立。
当 \(n = k+1\) 时，根据组合基本性质5有
\[\begin{aligned} (x+y)^{k+1} &= (x+y)\sum_{i=0}^k \binom{k}{i}x^{k-i}y^i \\ &= x\sum_{i=0}^k \binom{k}{i}x^{k-i}y^i + y\sum_{i=0}^k \binom{k}{i}x^{k-i}y^i \\ &= \sum_{i=0}^k \binom{k}{i}x^{k+1-i}y^i + \sum_{i=1}^{k+1} \binom{k}{i-1}x^{k-i+1}y^i \\ &= \binom{k}{0}x^{k+1} + \sum_{i=1}^k \binom{k}{i}x^{k+1-i}y^i + \sum_{i=1}^{k} \binom{k}{i-1}x^{k-i+1}y^i + \binom{k}{k}y^{k+1} \\ &= \binom{k}{0}x^{k+1} + \sum_{i=1}^k \binom{k+1}{i}x^{k+1-i}y^i + \binom{k+1}{k+1}y^{k+1} \\ &= \sum_{i=0}^{k+1} \binom{k+1}{i}x^{k+1-i}y^i \\ \end{aligned} \]于是得证。
方法2：
我们枚举 \(x,y\) 的指数 \(i,j\) 满足 \(i+j = n\) 的情况，等价于枚举 \(i(0\leq i \leq n)\) 得到 \(j = n - i\) 。对于一个 \(i\) 的情况，需要求在 \(n\) 个 \((x+y)\) 括号中有 \(i\) 个选 \(x\) 和 \(n-i\) 个选 \(y\) 的方案数。
我们可以 \(n\) 选 \(i\) 后 \(n-i\) 选 \(n-i\) 共 \(\dbinom{n}{i} \dbinom{n-i}{n-i} = \dbinom{n}{i}\) 种方案。
当然，我们也可以理解为一个多重集的模型，有 \(i\) 个选 \(x\) 的 \((x+y)\) 和 \(n-i\) 个选 \(y\) 的 \((x+y)\) ，选择相同的 \((x+y)\) 算相同的元素，不同的顺序算不同的方案，所以是求有限多重集的全排列数，为 \(\dbinom{n}{i,n-i} = \dbinom{n}{i}\) 种方案。
因此 \(\displaystyle (x+y)^n = \sum_{i=0}^n \binom{n}{i}x^{n-i}y^i\) 。
定理2的证明：
同样可以使用归纳法，但比较复杂，我们使用定理1的证法2，即组合意义证明。
我们枚举 \(x_i(1\leq i \leq k)\) 的指数 \(n_i\) 满足 \(n_1 + n_2 + \cdots + n_k = n\) 的情况。对于一组非负整数解 \(n_1,n_2,\cdots ,n_k\) ，需要求在 \(n\) 个 \((x_1 + x_2 + \cdots + x_k)\) 括号中有 \(n_i(1\leq i \leq k)\) 个括号内选了 \(x_i\) 的方案数。
我们设多重集有 \(n_i(1\leq i \leq k)\) 个选 \(x_i\) 的 \((x_1+x_2+\cdots + x_k)\) ， 其全排列数为 \(\dbinom{n}{n_1,n_2,\cdots,n_k}\) 。
因此 \(\displaystyle \left( \sum_{i = 1}^k x_i \right)^n = \sum_{n_1+n_2+\cdots + n_k = n} \binom{n}{n_1,n_2,\cdots ,n_k}\prod_{i = 1}^k x_i^{n_i}\) 。
范德蒙德卷积
定理1（范德蒙德卷积） \(\displaystyle \sum_{i = 0}^k \dbinom{n}{i} \dbinom{m}{k-i} = \dbinom{n+m}{k}\) 。
- 推论1（定理1的推论） \(\displaystyle \sum_{i = -s}^r \dbinom{n}{i+s} \dbinom{m}{r-i} = \dbinom{n+m}{s+r}\) 。
- 推论2（定理1的推论） \(\displaystyle \sum_{i = 0}^n \dbinom{n}{i}\dbinom{n}{i-1} = \dbinom{2n}{n-1}\) 。
- 推论3（定理1的推论） \(\displaystyle \sum_{i = 0}^n \dbinom{n}{i}^2 = \dbinom{2n}{n}\) 。
- 推论4（定理1的推论） \(\displaystyle \sum_{i = 0}^m \dbinom{n}{i} \dbinom{m}{i} = \dbinom{n+m}{m}\) 。
定理1的证明：
方法1：
由二项式定理的定理1可得
\[\begin{aligned} \sum_{k = 0}^{n+m} \binom{n+m}{k} x^k &= (1+x)^{n+m} \\ &= (1+x)^n(1+x)^m \\ &= \left( \sum_{i = 0}^n \binom{n}{i}x^i \right)\left( \sum_{j = 0}^m \binom{m}{j}x^j \right) \\ &= \sum_{i = 0}^n \sum_{j = 0}^m \binom{n}{i} \binom{m}{j} x^{i+j} \\ &= \sum_{k = 0}^{n+m} \sum_{i = 0}^k \binom{n}{i} \binom{m}{k-i} x^k \end{aligned} \]根据待定系数法 \(x^k\) 的系数相同，可得 \(\displaystyle \sum_{i = 0}^k \dbinom{n}{i} \dbinom{m}{k-i} = \dbinom{n+m}{k}\) 。
方法2：
一个集合有 \(n+m\) 个元素，从中选 \(k\) 个元素的方案数为 \(\dbinom{n+m}{k}\) 。
其等价于，将集合分成 \(n,m\) 两部分，从 \(n\) 中选 \(i(0 \leq i \leq k)\) 个再从 \(m\) 中选 \(k-i\) 个，共 \(\displaystyle \sum_{i = 0}^k \dbinom{n}{i} \dbinom{m}{k-i}\) 种方案。
推论1的证明：
由定理1简单变换可得
\[\begin{aligned} \sum_{i = 0}^k \binom{n}{i} \binom{m}{k-i} &= \sum_{i=-r}^{k-r} \binom{n}{i+r} \binom{m}{k-i-r}\\ &= \sum_{i=-r}^{s} \binom{n}{i+r} \binom{m}{s-i} \\ &= \binom{n+m}{s+r} \end{aligned} \]于是得证。
推论2的证明：
由定理1简单变换可得
\[\begin{aligned} \sum_{i = 0}^n \binom{n}{i}\binom{n}{i-1} &= \sum_{i = 0}^n \binom{n}{i}\binom{n}{n-i+1}\\ &= \binom{2n}{n+1} \\ &= \binom{2n}{n-1} \end{aligned} \]于是得证。
推论3的证明：
由定理1简单变换可得
\[\begin{aligned} \sum_{i = 0}^n \binom{n}{i}^2 &= \sum_{i = 0}^n \binom{n}{i}\binom{n}{n-i}\\ &= \binom{2n}{n} \\ \end{aligned} \]于是得证。
推论4的证明：
方法1：
由定理1简单变换可得
\[\begin{aligned} \sum_{i = 0}^n \binom{n}{i}\binom{m}{i} &= \sum_{i = 0}^n \binom{n}{i}\binom{m}{m-i}\\ &= \binom{n+m}{m} \\ \end{aligned} \]于是得证。
方法2：
在 \(n \times m\) 的网格图上，从 \((0,0)\) 走到 \((n,m)\) ，只能向右或者向下走，有多少方案。
显然会向右走 \(m\) 步和向下走 \(n\) 步共 \(n+m\) 步，所以方案数是 \(\dbinom{n+m}{m} \dbinom{n}{n} = \dbinom{n+m}{m}\) 。
其等价于，将 \(n+m\) 步分为 \(n,m\) 步，在 \(n\) 步中选 \(i(0\leq i \leq m)\) 步向右，然后在 \(m\) 步选 \(m-i\) 步向右，有 \(\displaystyle \sum_{i = 0}^m \dbinom{n}{i} \dbinom{m}{i}\) 种方案。
卢卡斯定理
定理1（卢卡斯定理） 若 \(p\) 是质数，则 \(\dbinom{n}{m} \equiv \dbinom{n \bmod p}{m \bmod p} \dbinom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \pmod p\) 。
- 推论1（定理1的推论） 若 \(p\) 是质数，整数 \(n,m(0\leq m \leq n)\) 的 \(p\) 进制表达分别为 \(n = a_ka_{k-1}\cdots a_0, m = b_kb_{k-1}\cdots b_0\) ，其中 \(a_i,b_i \in[0,p)(0\leq i \le k)\) ，则 \(\displaystyle \binom{n}{m} \equiv \prod_{i = 0}^k\binom{a_i}{b_i}\pmod p\) 。
定理1的证明：
先证明 \((x+y)^p \equiv x^p + y^p \pmod p\) ，其中 \(p\) 为素数。
考虑二项式 \((x+y)^p\) ，根据二项式定理有 \(\displaystyle (x+y)^p = \sum_{i=0}^p \binom{p}{i}x^{p-i}y^i\) ，其中 \(\dbinom{p}{i} = \dfrac{p!}{i!(p-i)!}\) ，显然当且仅当 \(i = 0\) 或 \(i = p\) 时 \(\dbinom{p}{i}\) 没有质因子 \(p\) 且此时值为 \(1\) ，因此 \(\dbinom{p}{i} \equiv [i = 0 \or i = p] \pmod p\) ，所以 \((x+y)^p \equiv x^p + y^p \pmod p\) 。
现在我们证明定理。
考虑二项式 \((1+x)^n\) ，我们有
\[\begin{aligned} (1+x)^n &\equiv (1+x)^{p \lfloor n/p \rfloor} (1+x)^{n \, \bmod \, p} \\ &\equiv (1+x^p)^{\lfloor n/p \rfloor}(1+x)^{n \, \bmod \, p} \\ &\equiv \left( \sum_{i=0}^{\lfloor n/p \rfloor} \binom{\lfloor n/p \rfloor}{i}x^{ip} \right) \left( \sum_{j=0}^{n \, \bmod \, p} \binom{n \bmod p}{j}x^j \right) \\ &\equiv \sum_{i=0}^{\lfloor n/p \rfloor} \sum_{j=0}^{n \, \bmod \, p} \binom{\lfloor n/p \rfloor}{i} \binom{n \bmod p}{j} x^{ip+j} \pmod p \end{aligned} \]其中 \(j \in [0,n \bmod p],n \bmod p<p\) ，那么不会有同一组 \((i,j)\) 使得 \(ip+j\) 相等，因此和式里的系数就是 \(x^{ip+j}\) 的系数。
根据二项式定理 \(\displaystyle (1+x)^n = \sum_{i=0}^n \dbinom{n}{i}x^i\) ， \(x^m\) 的系数为 \(\dbinom{n}{m}\) 。在模 \(p\) 下，令 \(ip + j = m\) 有 \(i = \left\lfloor \dfrac{m}{p} \right\rfloor,j = m \bmod p\) ， \(x^m\) 的系数为 \(\dbinom{n \bmod p}{m \bmod p} \dbinom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor}\) 。因此，根据待定系数法可得， \(\dbinom{n}{m} \equiv \dbinom{n \bmod p}{m \bmod p} \dbinom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \pmod p\) 。
推论1的证明：
把定理1的 \(n,m\) 持续递推，发现每次得到的都是 \(p\) 进制下的数位，因此得证。
组合数的求法
加法递推
根据性质5可得加法递推公式 \(\dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1}\) ，依次递推可得 \(0 \leq m \leq n\) 的所有组合数。
这个递推在模数为素数时，完全可以被公式法替代，其他情况可以考虑使用。
时间复杂度 \(O(n^2)\)
空间复杂度 \(O(n^2)\)
const int P = 1e9 + 7;
namespace CNM {
const int N = 2e3 + 7;
int c[N][N];
void init(int n) {
for (int i = 0;i <= n;i++)
for (int j = 0;j <= i;j++)
c[i][j] = 0 < j && j < i ? (c[i - 1][j - 1] + c[i - 1][j]) % P : 1;
}
int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
return c[n][m];
}
}
乘法递推
根据性质3可得乘法递推公式 \(\dbinom{n}{m} = \dfrac{n-m+1}{m} \dbinom{n}{m-1}\) ，可以直接求确定 \(n\) 的组合数，注意先乘法后除法。
可以利用性质2 \(\dbinom{n}{m} = \dbinom{n}{n-m}\) 去掉一半计算量。
当我们无法保存加法递推的所有组合数，但只需要一行组合数时，可以考虑此法。
注意此法不可直接取模，并且取模情况可以由公式法直接替代。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
namespace CNM {
const int N = 34;
int n, Cn[N];
void init(int _n) {
n = _n;
Cn[0] = Cn[n] = 1;
for (int i = 1;2 * i <= n;i++) Cn[i] = Cn[n - i] = 1LL * (n - i + 1) * Cn[i - 1] / i;
}
int C(int m) {
if (n < m || m < 0) return 0;
return Cn[m];
}
}
公式法
公式法是组合数取素数模时最好的解法，其利用逆元处理除法求 \(\dbinom{n}{m} = \dfrac{n!}{m!(n-m)!}\) ，可以在线性时间内处理出 \(0 \leq m \leq n\) 的所有组合数。
公式法在复杂度上优于加法递推，与乘法递推相同；在使用范围上与加法递推相同，优于乘法递推，可以完全替代前两个方法。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
const int P = 1e9 + 7;
namespace Number_Theory {
const int N = 1e7 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int fact[N], invfact[N];
void init(int n) {
fact[0] = 1;
for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
invfact[n] = qpow(fact[n], P - 2);
for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
}
}
namespace CNM {
using namespace Number_Theory;
int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;
}
}
卢卡斯定理
在模数为不大的素数，但 \(n\) 很大时，可以考虑用卢卡斯定理 \(\dbinom{n}{m} \equiv \dbinom{n \bmod p}{m \bmod p} \dbinom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \pmod p\) 分解组合数，再利用公式法求解。
时间复杂度 \(O(p+ \log n)\)
空间复杂度 \(O(n)\)
const int P = 1e5 + 3;
namespace Number_Theory {
const int N = 1e5 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int fact[N], invfact[N];
void init(int n) {
fact[0] = 1;
for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
invfact[n] = qpow(fact[n], P - 2);
for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
}
}
namespace CNM {
using namespace Number_Theory;
int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;
}
}
namespace Lucas {
int C(int n, int m) {
int ans = 1;
while (n) {
ans = 1LL * ans * CNM::C(n % P, m % P) % P;
n /= P, m /= P;
}
return ans;
}
}
扩展卢卡斯定理
扩展卢卡斯定理解决了卢卡斯定理无法解决的非素数模数情况，其主要利用了CRT将问题分解，又通过威尔逊定理相关解决了质数幂模数的组合数求模问题。
证明：
我们先将问题分解为多个质数幂的模，因为模数互质，所以最后可以用CRT合并，于是有
\[\left\{ \begin{aligned} \binom{n}{m} &\equiv a_1 \pmod {p_1^{\alpha_1}}\\ \binom{n}{m} &\equiv a_2 \pmod {p_2^{\alpha_2}}\\ &\vdots \\ \binom{n}{m} &\equiv a_k \pmod {p_k^{\alpha_k}}\\ \end{aligned} \right. \]接下来我们要求出 \(k\) 个方程中的 \(a_i\) 。
不妨我们考虑其中一个方程 \(\dbinom{n}{m} \equiv \dfrac{n!}{m!(n-m)!}\equiv a \pmod {p^{\alpha}}\) ，我们可以对各个阶乘取模后合并，其中分母取逆元。
注意到阶乘可能含有因子 \(p\) ，可能导致结果为 \(0\) 或者无法求逆元，但实际上在分式中因子 \(p\) 会被消除，因此我们可以考虑先将 \(p\) 因子全部提出，再对除去所有 \(p\) 因子的阶乘求模，于是有 \(\dfrac{\dfrac{n!}{v_p(n!)}}{\dfrac{m!}{v_p(m!)} \cdot \dfrac{(n-m)!}{v_p((n-m)!)}}\cdot p^{x-y-z} \equiv a \pmod{p^\alpha}\) 。
不妨考虑 \(\dfrac{n!}{v_p(n!)}\) 的求法，根据威尔逊定理的推论1有 \(\dfrac{n!}{v_p(n!)} \equiv (\pm 1)^{\lfloor n/p^\alpha \rfloor} \dfrac{\lfloor n/p \rfloor!}{v_p(\lfloor n/p \rfloor!)} ((n \bmod p^\alpha)!)_p \pmod{p^\alpha}\) ，其中 \(\pm 1\) 的判定根据威尔逊定理的定理5即可， \(((n \bmod p^\alpha)!)_p\) 可以预处理，于是我们可以递归求解。但这是尾递归，我们可以改为迭代形式。因此，我们将分式三部分的余数求完，对分母取逆元变为乘法， \(p^{x-y-z}\) 利用快速幂求解，最后相乘即可求出 \(a\) 。
最后，求完 \(k\) 个方程的余数后，我们通过CRT合并。
这个过程证明相当复杂，初学者可以学个板子略过了。
时间复杂度 \(O\left (\displaystyle \sum_{i}(\log_{p_i}n + \log p_i + p_i^{\alpha_i}) \right)\)
空间复杂度 \(O(\max\{p_i^{\alpha_i}\})\)
namespace Number_Theory {
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) { x = 1, y = 0; return a; }
ll d = exgcd(b, a % b, x, y);
x -= (a / b) * y, swap(x, y);
return d;
}
ll inv(ll a, ll P) {
ll x, y;
exgcd(a, P, x, y);
return (x % P + P) % P;
}
int qpow(int a, ll k, int P) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
}
namespace CRT {
using namespace Number_Theory;
ll solve(int k, const vector<int> &a, const vector<int> &p) {
ll P = 1, ans = 0;
for (int i = 1;i <= k;i++) P *= p[i];
for (int i = 1;i <= k;i++) {
ll Pi = P / p[i], invPi = inv(Pi, p[i]);
(ans += (__int128_t)a[i] * Pi * invPi % P) %= P;
}
return ans;
}
}
namespace exLucas {
using namespace Number_Theory;
int fpr(ll n, int p, int P) {
vector<int> f(P);
f[0] = 1;
for (int i = 1;i < P;i++)
f[i] = 1LL * f[i - 1] * (i % p ? i : 1) % P;
int ans = 1;
while (n) {
if ((p != 2 || P <= 4) && ((n / P) & 1)) ans = P - ans;
ans = 1LL * ans * f[n % P] % P;
n /= p;
}
return ans;
}
int Cpr(ll n, ll m, int p, int P) {
int cnt = 0;
for (ll i = n;i;i /= p) cnt += i / p;
for (ll i = m;i;i /= p) cnt -= i / p;
for (ll i = n - m;i;i /= p) cnt -= i / p;
return 1LL * qpow(p, cnt, P) * fpr(n, p, P) % P *
inv(fpr(m, p, P), P) % P * inv(fpr(n - m, p, P), P) % P;
}
int C(ll n, ll m, int P) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
int k = 0;
vector<int> a(20), p(20);
for (int i = 2;i * i <= P;i++) {
if (!(P % i)) {
p[++k] = 1;
while (!(P % i)) p[k] *= i, P /= i;
a[k] = Cpr(n, m, i, p[k]);
}
}
if (P > 1) p[++k] = P, a[k] = Cpr(n, m, P, p[k]);
return CRT::solve(k, a, p);
}
}
枚举质因子重数
对于不取模的大组合数，直接使用高精度乘除法的复杂度比较大，因此考虑先求出质因子的幂次，再高精度累乘即可。
注意先预处理 \(n\) 以内的质数，复杂度玄学，估计下面这个。
时间复杂度 \(O\left(n\log \dbinom{n}{m} \right)\)
空间复杂度 \(O\left( \log \dbinom{n}{m} \right)\)
///继承vector解决位数限制(当前最大位数是9倍整型最大值)，操作方便（注意size()返回无符号长整型，尽量不要直接把size放入表达式）
struct Huge_Int:vector<long long> {
static const int WIDTH = 9;///压位数，压9位以下 比较安全
static const long long BASE = 1e9;///单位基
static const long long MAX_INT = ~(1 << 31);///最大整型
bool SIGN;
///初始化，同时也可以将低精度转高精度、字符串转高精度
///无需单独写高精度数和低精度数的运算函数，十分方便
Huge_Int(long long n = 0) { *this = n; }
Huge_Int(const string &str) { *this = str; }
///格式化，包括进位和去前导0，用的地方很多，先写一个
Huge_Int &format(int fixlen = 1) {//去0后长度必须大于等于fixlen，给乘法用的
while (size() > fixlen && !back()) pop_back();//去除最高位可能存在的0
if (!back()) SIGN = 0;
for (int i = 1; i < size(); ++i) {
(*this)[i] += (*this)[i - 1] / BASE;
(*this)[i - 1] %= BASE;
}//位内进位
while (back() >= BASE) {
push_back(back() / BASE);
(*this)[size() - 2] %= BASE;
}//位外进位
return *this;//为使用方便，将进位后的自身返回引用
}
///归零
void reset() {
clear();
SIGN = 0;
}
///重载等于，初始化、赋值、输入都用得到
Huge_Int operator=(long long n) {
reset();
SIGN = n < 0;
if (SIGN) n = -n;
push_back(n);
format();
return *this;
}
Huge_Int operator=(const string &str) {
reset();
if (str.empty()) push_back(0);
SIGN = str[0] == '-';
for (int i = str.length() - 1;i >= 0 + SIGN;i -= WIDTH) {
long long tmp = 0;
for (int j = max(i - WIDTH + 1, 0 + SIGN);j <= i;j++)
tmp = (tmp << 3) + (tmp << 1) + (str[j] ^ 48);
push_back(tmp);
}
format();
return *this;
}
///重载输入输出
friend istream &operator>>(istream &is, Huge_Int &tmp) {
string str;
if (!(is >> str)) return is;
tmp = str;
return is;
}
friend ostream &operator<<(ostream &os, const Huge_Int &tmp) {
if (tmp.empty()) os << 0;
else {
if (tmp.SIGN) os << '-';
os << tmp[tmp.size() - 1];
}
for (int i = tmp.size() - 2;i >= 0;i--) {
os << setfill('0') << setw(WIDTH) << tmp[i];
}
return os;
}
///重载逻辑运算符，只需要小于，其他的直接代入即可
///常量引用当参数，避免拷贝更高效
friend bool operator<(const Huge_Int &a, const Huge_Int &b) {
if (a.SIGN ^ b.SIGN) return a.SIGN;
if (a.size() != b.size()) return a.SIGN ? a.size() > b.size():a.size() < b.size();
for (int i = a.size() - 1; i >= 0; i--)
if (a[i] != b[i])return a.SIGN ? a[i] > b[i] : a[i] < b[i];
return 0;
}
friend bool operator>(const Huge_Int &a, const Huge_Int &b) { return b < a; }
friend bool operator>=(const Huge_Int &a, const Huge_Int &b) { return !(a < b); }
friend bool operator<=(const Huge_Int &a, const Huge_Int &b) { return !(a > b); }
friend bool operator!=(const Huge_Int &a, const Huge_Int &b) { return a < b || b < a; }
friend bool operator==(const Huge_Int &a, const Huge_Int &b) { return !(a != b); }
///重载负号
friend Huge_Int operator-(Huge_Int a) { return a.SIGN = !a.SIGN, a; }
///绝对值函数
friend Huge_Int abs(Huge_Int a) { return a.SIGN ? (-a) : a; }
///加法，先实现+=，这样更简洁高效
friend Huge_Int &operator+=(Huge_Int &a, const Huge_Int &b) {
if (a.SIGN ^ b.SIGN) return a -= (-b);
if (a.size() < b.size()) a.resize(b.size());
for (int i = 0; i < b.size(); i++) a[i] += b[i];//被加数要最大位，并且相加时不要用未定义区间相加
return a.format();
}
friend Huge_Int operator+(Huge_Int a, const Huge_Int &b) { return a += b; }
friend Huge_Int &operator++(Huge_Int &a) { return a += 1; }
friend Huge_Int operator++(Huge_Int &a, int) {
Huge_Int old = a;
++a;
return old;
}
///减法，由于后面有交换，故参数不用引用
friend Huge_Int &operator-=(Huge_Int &a, Huge_Int b) {
if (a.SIGN ^ b.SIGN) return a += (-b);
if (abs(a) < abs(b)) {
Huge_Int t = a;
a = b;
b = t;
a.SIGN = !a.SIGN;
}
for (int i = 0; i < b.size(); a[i] -= b[i], i++) {
if (a[i] < b[i]) {//需要借位
int j = i + 1;
while (!a[j]) j++;
while (j > i) a[j--]--, a[j] += BASE;
}
}
return a.format();
}
friend Huge_Int operator-(Huge_Int a, const Huge_Int &b) { return a -= b; }
friend Huge_Int &operator--(Huge_Int &a) { return a -= 1; }
friend Huge_Int operator--(Huge_Int &a, int) {
Huge_Int old = a;
--a;
return old;
}
///乘法，不能先实现*=，因为是类多项式相乘，每位都需要保留，不能覆盖
friend Huge_Int operator*(const Huge_Int &a, const Huge_Int &b) {
Huge_Int n;
n.SIGN = a.SIGN ^ b.SIGN;
n.assign(a.size() + b.size() - 1, 0);//表示乘积后最少的位数(可能会被format消掉，因此添加了format参数)
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++)
n[i + j] += a[i] * b[j];
n.format(n.size());//提前进位
}
return n;//最后进位可能会溢出
}
friend Huge_Int &operator*=(Huge_Int &a, const Huge_Int &b) { return a = a * b; }
///带余除法函数，方便除法和模运算，暂时写不出高效的高精与高精的除法
friend Huge_Int divmod(Huge_Int &a, const Huge_Int &b) {//O(logn)，待修改
assert(b != 0);
Huge_Int n;
if (-MAX_INT - 1 <= b && b <= MAX_INT) {//除数小于等于整型才能用这个，不然会溢出
n = a;
n.SIGN = a.SIGN ^ b.SIGN;
long long rest = 0;
long long bl = 0;
for (int i = b.size() - 1;i >= 0;i--) bl = bl * BASE + b[i];
for (int i = n.size() - 1;i >= 0;i--) {
rest *= BASE;
n[i] += rest;
rest = n[i] % bl;
n[i] /= bl;
}
a = a.SIGN ? (-rest) : rest;
return n.format();
}
else {//考虑倍增或者二分优化
n.SIGN = a.SIGN ^ b.SIGN;
for (int i = a.size() - b.size(); abs(a) >= abs(b); i--) {//减法代替除法
Huge_Int c, d;
d.assign(i + 1, 0);
d.back() = 1;
d.SIGN = n.SIGN;
c = b * d;//提高除数位数进行减法
while (abs(a) >= abs(c)) a -= c, n += d;
d.pop_back();
if (!d.empty()) {//遍历压的位
d.back() = BASE / 10;
for (int i = 1;i < WIDTH;i++) {
c = b * d;
while (abs(a) >= abs(c)) a -= c, n += d;
d.back() /= 10;
}
}
}
return n;
}
}
friend Huge_Int operator/(Huge_Int a, const Huge_Int &b) { return divmod(a, b); }
friend Huge_Int &operator/=(Huge_Int &a, const Huge_Int &b) { return a = a / b; }
friend Huge_Int &operator%=(Huge_Int &a, const Huge_Int &b) { return divmod(a, b), a; }
friend Huge_Int operator%(Huge_Int a, const Huge_Int &b) { return a %= b; }
};
namespace Number_Theory {
const int N = 1e6 + 7;
bool vis[N];
vector<int> prime;
void get_prime(int n) {
for (int i = 2;i <= n;i++) {
if (!vis[i]) prime.push_back(i);
for (auto j : prime) {
if (i * j > n) break;
vis[i * j] = 1;
if (!(i % j)) break;
}
}
}
}
namespace Legendre {
using namespace Number_Theory;
int fact_pexp(int n, int p) {
int cnt = 0;
while (n) {
cnt += n / p;
n /= p;
}
return cnt;
}
}
namespace CNM {
using namespace Number_Theory;
Huge_Int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
Huge_Int ans(1);
for (int i = 0;i < prime.size();i++) {
int k =
Legendre::fact_pexp(n, prime[i]) -
Legendre::fact_pexp(m, prime[i]) -
Legendre::fact_pexp(n - m, prime[i]);
int p = prime[i];
while (k) {
if (k & 1) ans *= p;
k >>= 1;
p *= p;
}
}
return ans;
}
}