信奥常见数列详解
Nostopathy
·
·
算法·理论
信奥中常见的有规律数列是解题的关键工具。掌握这些数列的特性、通项公式、递推关系和应用场景，能帮助您快速识别题目模型并找到解决方案。以下是 Nos 的总结。
等差数列&等比数列
定义
等差数列中相邻两数有公差 d，即 a_k=a_{k-1}+d。等比数列中相邻两数有相同比值 q，即 a_k=qa_{k-1}。
通项公式
等差数列 a_n=a_1+(n-1)d。
等比数列 a_n=a_1q^{n-1}。
求和
等差数列前 n 项和：\frac{n(a_1+a_n)}{2}。
::::info[证明]{open}
设前 n 项和为 S_n。
则
\begin{aligned}
2S_n&=(a_1+a_n)+(a_2+a_{n-1})+\dots+(a_n+a_1)\\
&=(a_1+a_n)+(a_1+d+a_n-d)+\dots+(a_1+(n-1)d+a_n-(n-1)d)\\
&=n(a_1+a_n)\\
S_n&=\frac{n(a_1+a_n)}{2}
\end{aligned}
证毕。
::::
等比数列前 n 项和：\frac{a_1(1-q^n)}{1-q}。
::::info[证明]{open}
设前 n 项和为 S_n。
则
\begin{aligned}
S_n&=a_1+a_1q+a_1q^2+\dots+a_1q^{n-1}\\
qS_n&=a_1q+a_1q^2+a_1q^3+\dots+a_1q^n\\
S_n-qS_n&=a_1-a_1q^n\\
(1-q)S_n&=(1-q^n)a_1\\
S_n&=\frac{a_1(1-q^n)}{1-q}(q \neq 1)
\end{aligned}
特别地，当 q=1，为常数列，S_n=na_1。
证毕。
::::
应用
对数组的某个区间 l \sim r 进行等差数列模式的修改。使用二阶差分，定义差分数组 d1_i=a_i-a_{i-1}，二阶差分数组 d2_i=d1_i-d1_{i-1}。此时操作等价于：
d2[L] += s;
d2[L+1] += (d - s); // 修正项
d2[R+1] -= (s + (R-L+1)*d); // 具体推导需根据差分定义
d2[R+2] += (s + (R-L)*d); // 具体推导需根据差分定义
计算等比数列前 n 项和对 M 取模，需要用快速幂计算 q^n \bmod M，同时将除法转换为乘逆元，S_n=a_1 \times (1-q^n) \times inv(1-q) \bmod M。（而快速幂的思想也源于等比数列的二分性质）
斐波那契数列（最常见）
定义
递归定义：F_0=0，F_1=1，F_n=F_{n-2}+F_{n-1}（n \geq 2）。
前缀和
::::info[证明]{open}
假设对 $n=k$ 成立，即 $S_k=F_{k+2}-1$。
则
$$
\begin{aligned}
S_{k+1}&=S_k+F_{k+1}\\
&=(F_{k+2}-1)+F_{k+1}\\
&=(F_{k+2}+F_{k+1})-1\\
&=F_{k+3}-1
\end{aligned}
$$
即 $S_{k+1}=F_{(k+1)+2}-1$，由数学归纳法，公式对任意非负整数 $n$ 都成立。
证毕。
::::
## 平方和
$F_0^2+F_1^2+\dots+F_n^2=F_n \cdot F_{n+1}$。
::::info[证明]{open}
假设对 $n=k$ 成立，即 $\sum_{i=0}^{k} F_i^2 = F_k \cdot F_{k+1}$。
则
$$
\begin{aligned}
\sum_{i=0}^{k+1} F_i^2&=\left( \sum_{i=0}^{k} F_i^2 \right) + F_{k+1}^2\\
&=F_k \cdot F_{k+1} + F_{k+1}^2=F_{k+1}(F_k \cdot F_{k+1})\\
&=F_{k+1}+F_{k+2}
\end{aligned}
$$
即 $\sum_{i=0}^{k+1} F_i^2=F_{k+1}+F_{(k+1)+1}$，由数学归纳法，公式对任意非负整数 $n$ 都成立。
证毕。
::::
## 卡西尼恒等式
对于任意正整数 $n$ 有 $F_{n+1} \cdot F_{n-1}-F_n^2=(-1)^n$。
::::info[证明]{open}
假设对 $n=k$ 成立，即 $F_{k+1} \cdot F_{k-1}-F_k^2=(-1)^k$。
则
$$
\begin{aligned}
F_{k+2} \cdot F_k-F_{k+1}^2&=(F_{k+1}+F_k)F_k-F_{k+1}^2\\
&=F_{k+1}F_k-F_{k+1}^2+F_k^2\\
&=F_{k+1}(F_k-F_{k+1})+F_k^2\\
&=-F_{k+1}F_{k-1}+F_k^2\\
&=-(F_{k+1} F_{k-1}-F_k^2)\\
&=-(-1)^k\\
&=(-1)^{k+1}
\end{aligned}
$$
即 $F_{(k+1)+1} \cdot F_{(k+1)-1}-F_{k+1}^2=(-1)^{k+1}$，由数学归纳法，公式对任意非负整数 $n$ 都成立。
证毕。
::::
## 应用
- 兔子问题：直接模型即可。
- 楼梯问题：每次可以走 $1$ 步或 $2$ 步，问走到第 $n$ 阶的方法数。$dp_i=dp_{i-1}+dp_{i-2}$。
- 棋盘覆盖问题：用 $2 \times 1$ 骨牌覆盖 $2 \times n$ 的棋盘，方案数为 $F_{n+1}$。
- 循环节与模运算：题目常要求结果对一个大数（如 $10^9+7$）取模，斐波那契数列模任何整数都有循环节，这个性质有时可用于优化。
## 计算方法
递归法：时间复杂度 $\Theta(2^n)$。
动态规划：时间复杂度 $\Theta(n)$。
矩阵快速幂：时间复杂度 $\Theta(\log n)$，参考 [this](https://www.cnblogs.com/MMMMMMMW/p/12300262.html)。
## 拓展：卢卡斯数列
递推关系：$L_0=2$，$L_1=1$，$L_n=L_{n-2}+L_{n-1}$（$n \geq 2$）。
该数列与斐波那契数列有密切联系，$L_n=F_{n-1}+F_{n+1}$。
# 卡特兰数（组合数学）
## 定义
$H_0=1$，$H_n=\sum_{i=0}^n H_i \cdot H_{n-i}$。
## 通项公式
$H_n=\frac{C_{2n}^n}{n+1}$ 或 $H_n=\frac{2n!}{n!(n+1)!}$。
::::info[证明]{open}
从一个等价问题出发：在一个平面直角坐标系中从 $(0,0)$ 走到 $(n,n)$，每次只能 $x$、$y$ 轴正方向走一步，且路线始终不越过对角线 $y=x$ 的方案数。
正难则反，一共需走 $2n$ 步，向右、向上分别 $n$ 步，因此总路径数为 $C_{2n}^n$。
非法路径是指至少有一次穿过对角线 $y=x$ 的路径（即某个时刻，向右步数超过了向上步数）。更精确地说，一条非法路径至少会碰到直线 $y=x+1$。
设 P 是一条非法路径，第一次碰到直线 $l$：$y=x+1$ 的点为点 A。
将路线 P 在点 A 前的部分关于直线 $l$：$y=x+1$ 作反射，此时起点 $(0,0)$ 被映射到了新起点 $(-1,1)$。这样，我们得到了一条从 $(-1,1)$ 到 $(n,n)$ 的新路径 P'。
从起点到终点需要向右、向上分别移动 $n+1$，$n-1$ 步，方案数为 $C_{2n}^{n+1}$（等价于 $C_{2n}^{n-1}$）。
合法路径数等于总路径数减去非法路径数。
$$
\begin{aligned}
H_n&=C_{2n}^n-C_{2n}^{n+1}\\
&=\frac{2n!}{n! \cdot n!}-\frac{2n!}{(n+1)! \cdot (n-1)!}\\
&=\frac{2n!}{n! \cdot n!}-\frac{2n!}{(n+1) \cdot n! \cdot (n-1)!}\\
&=\frac{2n!}{n! \cdot (n-1)!}(\frac{1}{n}-\frac{1}{n+1})\\
&=\frac{2n!}{n! \cdot (n-1)!} \cdot \frac{1}{n(n+1)}\\
&=\frac{2n!}{n! \cdot n!} \cdot \frac{1}{n+1}\\
&=\frac{1}{n+1}C_{2n}^{n}
\end{aligned}
$$
证毕。
::::
## 应用
- 括号序列：$n$ 对括号的合法匹配序列的数量。
- 出栈序列：一个栈的进栈序列为 $1,2,3,\dots,n$，有多少种不同的合法出栈序列。
- 二叉树计数：$n$ 个节点可以构成多少种不同的无标号二叉树（节点相同）。
- 凸多边形三角划分：将一个凸 $n+2$ 边形用不相交的对角线划分成三角形的方法数。
- 乘法顺序：计算 $n+1$ 个矩阵连乘，用括号改变乘法顺序的方案数。
## 计算方法
递推法：时间复杂度 $\Theta(n^2)$。
通项公式法：结合预处理阶乘和逆元来快速计算组合数，时间复杂度 $\Theta(n)$ 预处理，$\Theta(1)$ 查询。这是信奥中最常用的方法。
```cpp
// 假设已预处理好阶乘数组 fac[] 和逆元数组 inv[]
long long catalan(int n) {
return fac[2*n] * inv[n] % MOD * inv[n+1] % MOD;
}
```
# 组合数数列（杨辉三角）
## 定义
$C_n^k$ 表示从 $n$ 个不同元素中取 $k$ 个元素的组合数。有通项公式 $C_n^k=\frac{n!}{k! \cdot (n-k)!}$，是由 $C_n^k=\frac{A_n^k}{A_k^k}$ 推导的。
## 递推关系
$C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$。
::::info[证明]{open}
$C_n^k$ 表示从 $n$ 个不同元素中取 $k$ 个元素的组合数，在这 $n$ 个元素中固定一个特殊的元素，就叫他 A。
分情况：
- 选出的 $k$ 个元素中包含 A，那么只需要在剩下的 $n-1$ 个元素中选 $k-1$ 个，方案数 $C_{n-1}^{k-1}$。
- 选出的 $k$ 个元素中不包含 A，那么必须在 A 以外的 $n-1$ 个元素中选全部 $k$ 个，方案数 $C_{n-1}^k$。
根据加法原理，总的方案数就等于 $C_{n-1}^{k-1}+C_{n-1}^k$。
::::
这同时也是杨辉三角的规律。
## 应用
- 二项式定理：$(a+b)^n=\sum_{k=0}^n C_n^k \cdot a^{n-k} \cdot b^k$。
- 多重集合组合数：$n$ 种元素，每种无限多，选 $k$ 个的方案数为 $C_{n+k-1}^k$。
## 计算方法
递推打表：时间复杂度 $\Theta(n^2)$。
预处理阶乘和逆元：预处理 $\Theta(n)$，查询 $\Theta(1)$。
```cpp
// 假设已经预处理阶乘数组 fac[]、阶乘的逆元数组 inv_fac[]
inline long long C(int n, int k) {
if (k < 0 || k > n) return 0;
return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}
```
卢卡斯定理：预处理 $\Theta(p)$，查询 $\Theta(1)$，参考 [this](https://oi-wiki.org/math/number-theory/lucas/)。
# 第一类斯特林数（集合划分）
## 定义
将 $n$ 个不同的元素划分成 $k$ 个循环排列（即圆排列）的方案数，记为 $s(n,k)$。
## 递推关系
$s(n,k)=(n-1) \cdot s(n-1,k)+s(n-1,k-1)$。（考虑第 $n$ 个元素：独自成一个环，或者插入到前 $n-1$ 个元素形成的 $k$ 个环的任何一个空隙中）
## 应用
第一类斯特林数是上升幂展开成普通幂的系数：$x(x+1)(x+2)\dots(x+n-1)=\sum_{k=1}^ns(n,k) \cdot x^k$。
# 第二类斯特林数（更重要）
## 定义
将 $n$ 个不同的元素划分成 $k$ 个非空的、无标号的集合的方案数，记为 $S(n,k)$ 或 $\{n,k\}$。
## 递推关系
$S(n,k)=k \cdot S(n-1,k)+S(n-1,k-1)$。（考虑第 $n$ 个元素：独自成一个集合，或者插入到前 $n-1$ 个元素形成的 $k$ 个集合的任何一个中）
## 通项公式
$S(n,k)=\frac{1}{k!}\sum_{i=0}^k (-1)^i \dbinom{k}{i}(k-i)^n$。
::::info[证明]{open}
设 $A$ 表示将 $n$ 个不同的球放入 $k$ 个不同的盒子中，且每个盒子至少有一个球的方案数。
考虑容斥原理。设全集 $U$ 为任意放置的方案（允许空盒），则 $|U| = k^n$。
设 $P_i$ 表示第 $i$ 个盒子为空的性质（$i=1,2,...,k$）。我们需要计算不满足任何 $P_i$ 的方案数。
由容斥原理：
$A = \sum_{i=0}^k (-1)^i \dbinom{k}{i}(k-i)^n
各项含义：
$k$ 个不同盒子的每种放置方案对应 $k!$ 种排列，故：
$S(n,k) = \frac{A}{k!} = \frac{1}{k!}\sum_{i=0}^k (-1)^i \dbinom{k}{i}(k-i)^n
证毕。
::::
应用
球盒问题：可以由第二类斯特林数推导出：
| 球是否相同 |
盒是否相同 |
是否允许空盒 |
方案数 |
| 不同 |
不同 |
不允许 |
k! \cdot S(n, k) |
| 不同 |
不同 |
允许 |
k^n |
| 不同 |
相同 |
不允许 |
S(n,k) |
| 不同 |
相同 |
允许 |
\sum_{i=0}^{k} S(n,i) |
贝尔数 B(n) 是第二类斯特林数的前缀和，表示将 n 个不同的元素划分成任意个非空集合的方案数。
B(n) = \sum_{k=0}^{n} S(n,k)
贝尔数本身也有递推公式：B(n+1) = \sum_{k=0}^{n} \dbinom{n}{k} \cdot B(k)。
结语
以上就是 Nos 总结的全部内容。在信奥中更应该灵活运用，善于找出是否与上述模型等价或相似，并将上述数列的常用计算方法（特别是矩阵快速幂、组合数预处理）写成可靠的模板代码，在比赛时可以直接使用。
希望这份总结能对你的信奥学习有所帮助！
第一次写专栏，管理大大求过。