扩展欧几里得：
令 \(c = \gcd(a, b)\)，则：
\[ax_0 + by_0 = c \]考虑求出一个 \(x_1, y_1\) 满足：
\[bx_1 + (a \bmod b)y_1 = c \]若 \(x_1, y_1, a, b\) 已知，我们如何找到 \(x, y\) 的一组解？
\[\begin{aligned} LHS & = bx_1 + (a \bmod b)y_1 \\ & = bx_1 + (a - b\lfloor \frac{a}{b} \rfloor)y_1 \\ & = ay_1 + b(x_1 - \lfloor \frac{a}{b} \rfloor y_1)\end{aligned} \]故可以令 \(x_0 \gets y_1, y_0 \gets x_1 - \lfloor \frac{a}{b} \rfloor y_1\)。
那我们如何去找 \(x_1, y_1\) 呢？考虑递归处理，递归到 \((b, a \bmod b)\)。
若 \(b\) 为 \(0\) 了，故可以令 \(x_n = 1, y_n = 0\)。
母函数/生成函数：
对于序列 \(a_0, a_1, a_2, \cdots\)，构造函数：
\[G(x) = a_0 + a_1x + a_2x^2 + \cdots = \sum\limits_{i = 0}^{+\inf} a_ix^i \]则称 \(G(x)\) 是序列 \(a\) 的母函数/生成函数。
\[G(x) = 0 + x + 2^2x^2 + 3^2x^3 + 16x^4 + \cdots + n^2x^n \]\[xG(x) = x^2 + 2^2x^3 + 3^2x^4 + \cdots + n^2x^{n + 1} \]\[(1-x)G(x) = x + 3x^2 + 5x^3 + \cdots + (2n-1)x^n \]\[(1-x)xG(x) = x^2 + 3x^3 + 5x^4 + \cdots + (2n - 1)x^{n +1} \]\[(1-x)^2G(x) = x + 2x^2 + 2x^3 + \cdots + 2x^n \]\[x(1-x)^2G(x) = x^2 + 2x^3 + 2x^4 + \cdots + 2x^{n + 1} \]\[(1-x)^3G(x) = x + x^2 \]\[G(x) = \frac{x^2 + x}{(1-x)^3} \]泰勒展开：
\[(1 + x)^{-1} = \sum_{i = 0}^{+\inf} (-1)^i x^i \]\[(1 - x)^{-1} = \sum_{i = 0}^{+\inf} x^i \]\[(1 - ax)^{-1} = \sum_{i = 0}^{+\inf} a^ix^i \]\[(1 - x^a)^{-1} = \sum_{i = 0}^{+\inf} [a |i] x^i \]Ferrers 图像（杨表）
性质：
-
非递增性。
-
每一层至少有一个格子。
-
绕 \(y = -x\) 旋转后形成新图像也是 Ferrers 图像（即旧的第 \(i\) 行为新的第 \(i\) 列）。
整数 \(n\) 拆分为最大数为 \(k\) 的方案数与拆分为 \(k\) 个数的方案数是相等的；两者的 Ferrers 的图像是共轭的（一一对应）。
故可以得到整数 \(n\) 拆为为最多不超过 \(m\) 个数的和的方案数与拆分成最大不超过 \(m\) 的方案数是相等的。
若一个 Ferrers 图像的共轭图像不变，则称该图像为自共轭图像。
一个自共轭图像就是一个奇数拆分数的表示方法。
组合数学的一些式子：
1.
\[\binom{n}{m} = \binom{n}{n - m} \]证明：
考虑组合意义，在 \(n\) 个物品中选了 \(m\) 个物品后，还剩下 \(n - m\) 个物品，每种情况是一一对应的；故 \(\binom{n}{m} = \binom{n}{n - m}\)。
2.
递推公式：
\[\binom{n}{m} = \binom{n - 1}m + \binom{n - 1}{m - 1} \]证明：
考虑组合意义，在 \(n\) 个物品中选 \(m\) 个物品的方案数：
- 若不选第一个，则在剩下的 \(n - 1\) 个中选 \(m\) 个；方案数是 \(\binom{n - 1}{m}\)。
- 若选择第一个，则在剩下的 \(n - 1\) 个中选 \(m - 1\) 个；方案数是 \(\binom{n - 1}{m - 1}\)。
3.
\[\binom{n}{x} \binom{x}{y} = \binom{n}{y} \binom{n - y}{x - y} \]证明：
也是考虑组合意义，是先在 \(n\) 个物品中选 \(x\) 个，然后再从 \(x\) 个物品中选择 \(y\) 个；等价于先在 \(n\) 个物品中选 \(y\) 个，因为有 \(S_y \subseteq S_x\)（其中 \(S_i\) 表示选择的这 \(i\) 个物品的集合），故只需要在剩下 \(n - y\) 个物品中选中 \(x - y\) 个与这 \(y\) 凑在一起就是这 \(x\) 个；方案数是 \(\binom{n}{y} \binom{n - y}{x - y}\)。
4：
从 \((0, 0)\) 走到 \((n, m)\)，每次只能横/纵坐标加 \(1\)，方案数是：
\[\binom{n + m}{n} = \binom{n + m}{m} \]证明：
注意到总共走的次数是 \(n + m\) 次，故在其中选择 \(n\) 次是横坐标加 \(1\)，其它的都是纵坐标加 \(1\)；则方案数是 \(\binom{n + m}{n}\)。
5.
\[\sum\limits_{i = 0}^n \binom{n}{i} = 2^n \]证明：
法 \(1\) 是使用楼下的二项式定理带入 \(a = b = 1\) 即可。
法 \(2\) 是考虑组合意义；有 \(2^n\) 是这 \(n\) 个物品中选任意个的方案数；则考虑枚举选的个数 \(i\)，方案数是 \(\binom{n}{i}\)。
6.
二项式定理：
\[(a + b)^n = \sum_{i = 0}^n \binom{n}{i} a^{n - i} b^i \]证明：
注意到 \((a + b)^n = a (a + b)^{n - 1} + b(a + b)^{n - 1} = a(a (a + b)^{n - 2} + b(a+b)^{n-2}) + b(a (a + b)^{n - 2} + b(a+b)^{n-2})\)；这样暴力展开后共有 \(2^n\) 系数为 \(1\) 的项。
相当于对于 \((a + b) \cdots (a + b)\) 中的每一个 \((a + b)\) 中选一个 \(a\) 或 \(b\) 出来与其它的乘积之和。
则考虑设这 \(n\) 个式子中选出了 \(i\) 个 \(b\)，则乘积是 \(a^{n - i}b^i\)，有 \(\binom{n}{i}\) 种选法；故有 \((a + b)^n = \sum\limits_{i = 0}^n \binom{n}{i} a^{n - i} b^i\)。
7.
套入楼上的二项式定理，令 \(a = 1, b = -1\)，则有：
\[\sum_{i = 0}^n (-1)^i \binom{n}{i} = 0 \]证明：
首先当 \(n\) 为奇数时，容易得到 \((-1)^i \binom{n}{i} + (-1)^{n - i} \binom{n}{n - i} = 0\)，故原式等于 \(0\)。
然后考虑 \(n\) 是偶数的情况，待补。
8.
范德蒙雷卷积：
\[\binom{m + n}{r} = \sum_{i = 0}^r \binom{m}{i}\binom{n}{r - i} \]证明：
考虑组合意义：
- 左边指在 \(m + n\) 个物品中选 \(r\) 个物品的方案数。
- 右边是考虑将这 \(m + n\) 个物品分为数量为 \(m\) 和 \(n\) 的两组，枚举第一组选的数量 \(i\)，则第二组选的数量是 \(r - i\)；方案数是 \(\binom{m}{i}\binom{n}{r - i}\)。
9.
一个长度为 \(n\) 的圆排列数量是 \((n - 1)!\) 种。
证明：
考虑断环为链，称为一个长度为 \(n\) 的排列，有 \(n!\) 种。
但是由于一个圆断开的位置有 \(n\) 种，故总方案数是 \(\frac{n!}{n} = (n - 1)!\)。
故从 \(n\) 个物品中选出 \(m\) 个组成圆排列的方案数是 \(\frac{A_n^m}{m}\)。
然后考虑项链排列，即在圆排列的基础上增添了可以进行翻转，则方案数要除以 \(2\)；故长度为 \(n(n > 2)\) 的项链排列方案数是 \(\frac{(n - 1)!}{2}\)。
故从 \(n\) 个物品中选出 \(m\) 个组成项链排列的方案数是 \(\frac{A_n^m}{2m}\)。
10.
多重集排列问题：共有 \(n\) 个物品，有 \(m\) 种物品，第 \(i\) 种物品有 \(a_i\) 个，即 \(\sum\limits_{i = 1}^m a_i = n\)，则这 \(n\) 个物品的排列数为：
\[\frac{n!}{\prod\limits_{i = 1}^n a_i!} \]证明：
考虑这 \(a_i\) 个相同物品，将其标号为 \(1,2, \cdots, a_i\)。
则对于这 \(n\) 个物品的全排列来说，若固定除了 \(i\) 这种物品以外的物品，那么有 \(a_i!\) 种情况，但是由于这些元素全部相同，这 \(a_i\) 个物品无论怎么排都是本质相同的；故对于每个 \(a_i\) 都要除以 \(a_i!\)。
11.
二项式定理扩展为高次项：
\[(\sum_{i = 1}^m a_i)^n = \sum\limits_{\sum\limits_{i = 1}^m r_i = n}^{b_i \ge 0} \frac{n!}{\prod\limits_{i = 1}^m b_i!} \Big( \prod_{i = 1}^m a_i^{b_i}\Big) \]证明：
与二项式定理差不多，即从这 \(n\) 个括号中，每个括号选一个 \(a_i\)，最后乘在一起的和。
然后枚举第 \(i\) 个数选的次数 \(b_i\)，则系数变为楼上的多重集排列问题。
12.
可重组合模型： 在 \(n\) 种物品中选出 \(m\) 个物品的方案数，即令 \(a_i\) 表示第 \(i\) 种物品选择的个数，需要满足 \(\sum\limits_{i = 1}^n a_i = m\)；方案数是 \(\binom{n + m - 1}{m}\)。
证明：
问题相当于将 \(m\) 个相同物品放入到 \(n\) 个不同盒子中的方案数。
考虑插板法，插入 \(n - 1\) 个板；则总共有 \(n + m - 1\) 个元素，选出其中的 \(m\) 个作为物品其它做法插板，方案数为 \(\binom{n + m - 1}{m}\)。
13：
不相邻组合问题： 在 \(1, 2, \cdots, n\) 中选取 \(m\) 个不同的数字，且没有相邻数字的方案数是：
\[\binom{n - m + 1}{m} \]证明：
考虑令选择的数为 \(a_0 < a_1 < \cdots a_{m - 1}\)。
我们需要满足 \(a_{i + 1} - a_i > 1\)，即 \(a_{i + 1} > a_i + 1\)；两边同时减去 \((i + 1)\) 得 \(a_{i + 1} - (i + 1) > a_i - i\)。
则考虑构造序列 \(b_i = a_i - i\)，则有 \(b_i < b_{i + 1}\)；故问题为满足 \(b_1 < b_2 < \cdots < b_m\) 的序列 \(b\) 的数量。
考虑 \(b_i\) 的值域为 \([1, n - m + 1]\)，则相当于在 \(1 \sim (n - m + 1)\) 个数中选出 \(m\) 个作为序列 \(b\)；故方案数为 \(\binom{n + m - 1}{m}\)。
14：
拿钥匙问题： 有 \(7\) 个人，每个人中手持一些钥匙；能打开大门当且仅当所有种类的钥匙至少都有一把；且任意三个人都打不开大门，任意四个人都打的开大门。
问：
-
至少有多少种钥匙？
-
每个人至少拿多少只钥匙？
因为任意三个人都至少缺一把钥匙；则任意三个人缺的钥匙种类都不同。
证明： 考虑反证法，若 \(a, b, c\) 这三个人缺 \(X\) 这个钥匙，且 \(a', b', c'\) 这三个人也缺 \(X\) 这个钥匙，则对于 \(a, b, c, a'\) 这四个人来说也缺 \(X\) 这个钥匙，无法打开大门，与题意不符。
故每 \(3\) 个人都会至少造成一把全新的钥匙，故钥匙种类数至少是 \(\binom{7}{3} = 35\)。
考虑对于一个人来说，其它 \(6\) 个人中任意 \(3\) 个人所缺的钥匙（至少缺一个）这个人都有，因为缺的钥匙种类不同；故每个人至少要拿 \(\binom{6}{3} = 20\) 个钥匙。
15：
阶乘的近似（Stirling 数）：
\[n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n \]证明： 咕咕咕。
16：
一个有趣的问题，对于有 \(n\) 个 \(1\) 和 \(m\) 个 \(0\) 的字符串中，问有多少个字符串满足 \(01\) 子串的数量加上 \(10\) 子串的数量为 \(k\)。
思路：
先按照 \(0 - 0 - \cdots - 0\) 这样放，则对于中间的某个空位，只要放了 \(1\)（无论放多少个），都会造成一个 \(01\) 子串和一个 \(10\) 子串，贡献为 \(2\)；若将 \(1\) 放到最左边或者最右边（无论放多少个），只会贡献一个 \(10\) 子串或者 \(01\) 子串，贡献只有 \(1\)。
故考虑分类讨论：
- 当 \(2|k\) 时：
- 在中间 \(m - 1\) 个空位中选出 \(\frac{k}{2}\) 个，方案数为 \(\binom{m - 1}{\frac{k}{2}}\)，然后是将 \(n\) 个 \(1\) 放到这 \(\frac{k}{2}\) 个空位中。
- 考虑隔板法，共有 \(n - 1\) 个空位，放 \(\frac{k}{2} - 1\) 个板，方案数为 \(\binom{n - 1}{\frac{k}{2} - 1}\)；故这种情况的方案数是 \(\binom{m - 1}{\frac{k}{2}}\binom{n - 1}{\frac{k}{2} - 1}\)。
- 然后还有一种情况，就是在最左边和最右边同时都要放 \(1\)（若只在一边放，由于放在中间空位贡献是 \(2\)，贡献只能是奇数，不合法）；然后再在中间选 \(\frac{k}{2} - 1\) 个位置。
- 首先中间 \(m - 1\) 个空位选 \(\frac{k}{2} - 1\) 的方案数是 \(\binom{m - 1}{\frac{k}{2} - 1}\)；然后还要将这 \(n\) 个 \(1\) 分到 \(\frac{k}{2} + 1\) 个位置去，插板法得方案数为 \(\binom{n - 1}{\frac{k}{2}}\)；故这种情况的方案数是 \(\binom{m - 1}{\frac{k}{2} - 1} \binom{n - 1}{\frac{k}{2}}\)。
- 故对于 \(2|k\) 的情况的总方案数是 \(\binom{m - 1}{\frac{k}{2}}\binom{n - 1}{\frac{k}{2} - 1} + \binom{m - 1}{\frac{k}{2} - 1} \binom{n - 1}{\frac{k}{2}}\)。
- 当 \(2 \not| k\) 时：
- 首先是在最左边或最右边至少放一个 \(1\)，贡献为 \(1\)，方案数为 \(2\)。
- 然后需要在中间 \(m - 1\) 个空位中选出 \(\frac{k - 1}{2}\) 个位置，方案数为 \(\binom{m - 1}{\frac{k - 1}{2}}\)。
- 最后相当于将 \(n\) 个 \(1\) 放在这 \(\frac{k + 1}{2}\) 个位置去，插板法得方案数是 \(\binom{n - 1}{\frac{k - 1}{2}}\)。
- 故对于 \(2 \not| k\) 的情况的总方案数是 \(2 \binom{m - 1}{\frac{k - 1}{2}} \binom{n - 1}{\frac{k - 1}{2}}\)
17：
将 \(n\) 个相同的球放在 \(m\) 个相同的盒子中，考虑动态规划算法，令 \(dp_{i, j}\) 表示这 \(j\) 个自然数的和为 \(i\) 的方案数：
\[dp_{n, m} = dp_{n - m, m} + dp_{n, m - 1} \]18：
求 \(n\) 位十进制数中出现偶数次 \(5\) 的数的个数。
法一：生成函数
考虑动态规划，令 \(f_i\) 表示 \(i\) 位十进制数出现偶数次的个数，\(g_i\) 表示出现奇数次的个数：
\[f_i = 9 f_{i - 1} + g_{i - 1} \]\[g_i = 9 g_{i - 1} + f_{i - 1} \]有 \(f_1 = 8, g_1 = 1\)，考虑构造生成函数：
\[F(x) = f_1 + f_2x + f_3x^2 + \cdots \]\[G(x) = g_1 + g_2x + g_3x^2 + \cdots \]有：
\[9xF(x) = 9f_1x + 9f_2x^2 + 9f_3x^3 + \cdots \]\[(1 - 9x)F(x) = f_1 + g_1x + g_2x^2 + g_3x^3 + \cdots = f_1 + xG(x) \]同理：
\[(1 - 9x)G(x) = g_1 + f_1x + f_2x^3 + f_3x^3 + \cdots = g_1 + xF(x) \]得到：
\[G(x) = \frac{1}{1 - 9x} + \frac{xF(x)}{1 - 9x} \]代入得：
\[(1 - 9x)F(x) = 8 + \frac{x}{1 - 9x} + \frac{x^2F(x)}{1 - 9x} \]\[(1 - 9x)^2 F(x) = 8(1- 9x) + x + x^2F(x) \]\[(1 - 8x)(1 - 10x) F(x) = 8 - 71x \]\[F(x) = \frac{8 - 71x}{(1 - 8x)(1 - 10x)} = \frac{\frac{7}{2}}{1 - 8x} + \frac{\frac{9}{2}}{1 - 10x} \]\[F(x) = \sum_{k = 0}^{+\inf} (\frac{7}{2} 8^k + \frac{9}{2}10^k)x^i = \frac{1}{2}\sum_{k = 0}^{+\inf} (7 \times 8^k + 9 \times 10^k)x^i \]法二：递推
在上面的基础下，注意到 \(f_i + g_i = 9 \times 10^{n - 1}\)。
则有：
\[f_i = 9f_{i - 1} +g_{i - 1} = 8f_{i - 1} +9 \times 10^{i - 2} \]构造生成函数：
\[F(x) = f_1 + f_2x + f_3x^2 + f_4x^3 + \cdots \]有：
\[8xF(x) = 8f_1x + 8f_2x^2 + 8f_3x^3 + 8f_4x^4 + \cdots \]则：
\[(1 - 8x)F(x) = f_1 + (9 \times 10^0)x + (9 \times 10^1)x + \cdots = 8 + 9x + 90x + \cdots \]\[(1 - 8x) F(x) = 8 + \sum_{i = 1}^{+\inf} (9 \times 10^{i - 1}) x^i \]\[10x(1 - 8x)F(x) = 80x + \sum_{i = 1}^{+\inf} ( 9 \times 10^i) x^{i + 1} \]相减有：
\[(1 - 8x)(1 - 10x) F(x) = 8-71x \]故：
\[F(x) = \sum_{k = 0}^{+\inf} (\frac{7}{2} 8^k + \frac{9}{2}10^k)x^i = \frac{1}{2}\sum_{k = 0}^{+\inf} (7 \times 8^k + 9 \times 10^k)x^i \]19：
正整数 \(n\) 拆分成 \(1,2,3,\cdots\) 不允许重复的拆分数 \(p(n)\) 与那些命题等价？
生成函数形式为：
\[\begin{aligned} G(x) &= (1 + x)(1 + x^2)(1 + x^3)(1 + x^4) \dots \\ & = \frac{1 - x^2}{1 - x} \frac{1 - x^4}{1 - x^2} \frac{1 - x^6}{1 - x^3} \frac{1 - x^8}{1 - x^4} \cdots \\ & = \frac{1}{1 - x} \frac{1}{1 - x^3} \frac{1}{1 - x^5} \cdots \\ & = (1 + x + x^2 + x^3 + \cdots)(1 + x^3 + x^6 + \cdots)(1 + x^5 + \cdots)\end{aligned} \]故可以等价于拆分为可重复的奇数方案数。
20：
求由直线 \(x + ky = n\) 与坐标轴围成的三角形内（含边界）整点的个数 \(S(k, n)\)。
即 \(y = -\frac{x}{k} + \frac{n}{k}\)，其在 \(y\) 轴上的截距为 \(\frac{n}{k}\)，考虑从枚举 \((x, y)\) 的 \(y \in [0, \lfloor \frac{n}{k} \rfloor]\)，求最大的 \(x\) 使得 \((x, y)\) 在直线下方，容易发现是 \(x = n - ky\)，故符合要求的整点数是：
\[\sum_{i = 0}^{\lfloor \frac{n}{k} \rfloor} n - ki = (\lfloor \frac{n}{k} \rfloor +1)n -k\frac{\lfloor \frac{n}{k} \rfloor (\lfloor \frac{n}{k} \rfloor + 1)}{2} \] 标签：frac,sum,2x,cdots,数学,binom,随笔,数是 From： https://www.cnblogs.com/rgw2010/p/18596268