斯特林数

一、斯特林数的准确定义与组合意义

1. 第二类斯特林数 $\begin{Bmatrix} n \\ k \end{Bmatrix}$

组合定义：将 $n$ 个不同的元素划分成 $k$ 个非空且无区别的集合（盒子）的方案数。 递推公式（考虑第 $n$ 个元素）： $$ \begin{Bmatrix} n \ k \end{Bmatrix} = k \cdot \begin{Bmatrix} n-1 \ k \end{Bmatrix} + \begin{Bmatrix} n-1 \ k-1 \end{Bmatrix} $$ 边界条件为 $\begin{Bmatrix} 0 \\ 0 \end{Bmatrix}=1$。

2. 第一类斯特林数

分为无符号 $\begin{bmatrix} n \\ k \end{bmatrix}$ 与有符号 $s(n,k)$ 两种，关系为： $$ s(n,k) = (-1)^{n-k} \begin{bmatrix} n \ k \end{bmatrix} $$

无符号第一类斯特林数 $\begin{bmatrix} n \\ k \end{bmatrix}$ 的组合定义：将 $n$ 个不同元素排成 $k$ 个非空循环排列（圆排列） 的方案数。
递推公式（同样考虑第 $n$ 个元素，它可自成一环，或插入到前 $n-1$ 个元素形成的环中任意一个元素右侧，共 $n-1$ 个空位）： $$ \begin{bmatrix} n \ k \end{bmatrix} = (n-1) \cdot \begin{bmatrix} n-1 \ k \end{bmatrix} + \begin{bmatrix} n-1 \ k-1 \end{bmatrix} $$

二、斯特林数的核心作用：幂的转换桥梁

这是斯特林数在竞赛中唯一且最重要的代数作用，它们负责在普通幂与下降幂之间自由切换：

转换方向	使用哪类斯特林数	核心公式
普通幂 $\to$ 下降幂	第二类斯特林数	$$ x^n = \sum_{k=0}^{n} \begin{Bmatrix} n \ k \end{Bmatrix} \cdot x^{\underline{k}} $$
下降幂 $\to$ 普通幂	第一类斯特林数（有符号）	$$ x^{\underline{n}} = \sum_{k=0}^{n} s(n,k) \cdot x^k $$
上升幂 $\to$ 普通幂	第一类斯特林数（无符号）	$$ x^{\overline{n}} = x(x+1)\cdots(x+n-1) = \sum_{k=0}^{n} \begin{bmatrix} n \ k \end{bmatrix} \cdot x^k $$

三、下降幂（Falling Factorial）的定义与竞赛特性

1. 定义

\[ x^{\underline{n}} = x(x-1)(x-2)\cdots(x-n+1) = n! \cdot \binom{x}{n} \]

2. 两大竞赛必杀技特性

特性一：离散微积分（差分算子 $\Delta$） 定义差分算子 $\Delta f(x)=f(x+1)-f(x)$，下降幂对其作用完全类比微积分中的求导： $$ \Delta x^{\underline{n}} = n \cdot x^{\underline{n-1}} $$ 由此可得定和分公式（离散版本的原函数）： $$ \sum_{a \le x < b} x^{\underline{m}} = \frac{b^{\underline{m+1}} - a^{\underline{m+1}}}{m+1} $$

特性二：平移公式（DP优化利器） $$ (x+1)^{\underline{k}} = x^{\underline{k}} + k \cdot x^{\underline{k-1}} $$ 这个公式在动态规划处理“状态长度+1”的转移时，能将单次转移复杂度从 $O(k^2)$ 直接降至 $O(k)$。

四、下降幂多项式的两种核心求法

求法一：普通多项式 $\to$ 下降幂形式（斯特林反演）

给定普通多项式 $f(x) = \sum_{i=0}^{n} a_i x^i$，要将其转化为下降幂基 $f(x) = \sum_{j=0}^{n} b_j x^{\underline{j}}$。直接代入第二类斯特林数的转换公式： $$ f(x) = \sum_{i=0}^{n} a_i x^i = \sum_{i=0}^{n} a_i \sum_{j=0}^{i} \begin{Bmatrix} i \ j \end{Bmatrix} x^{\underline{j}} = \sum_{j=0}^{n} \left( \sum_{i=j}^{n} a_i \begin{Bmatrix} i \ j \end{Bmatrix} \right) \cdot x^{\underline{j}} $$ 因此下降幂系数为： $$ b_j = \sum_{i=j}^{n} a_i \begin{Bmatrix} i \ j \end{Bmatrix} $$ 竞赛中通常 $O(n^2)$ 预处理斯特林数即可求出，配合 NTT（快速数论变换）可优化至 $O(n \log n)$。

求法二：由点值求下降幂多项式（插值）

若已知多项式在 $0, 1, \dots, n$ 处的点值 $f(0), f(1), \dots, f(n)$，可利用指数型生成函数（EGF）卷积在 $O(n \log n)$ 内求出下降幂系数，这是省选级别的常见考点。

五、竞赛实战经典例题完整精讲

例1（洛谷 P4609 / 圆排列计数）

题意：求长为 $n$ 的排列，从左往右看最大值为前缀最大值，从右往左看最大值为后缀最大值，已知前缀最大值个数为 $A$，后缀最大值个数为 $B$，求方案数。解：最大值 $n$ 必然同时属于两者。将剩下的 $n-1$ 个数分成 $A+B-2$ 组，每组内部构成一个圆排列（每组最大值视为该组可视的“楼顶”），再从 $A+B-2$ 组中选 $A-1$ 组放左边。答案可直接化为： $$ f(n,A,B) = \binom{A+B-2}{A-1} \cdot \begin{bmatrix} n-1 \ A+B-2 \end{bmatrix} $$ 即组合数乘以无符号第一类斯特林数。预处理斯特林数后即可 $O(1)$ 回答每组询问。

例2（CF 932E Team Work）

题意：给定 $n, k$（$n$ 极大，$k \le 5000$），求 $\sum_{i=1}^{n} \binom{n}{i} i^k \pmod{10^9+7}$。解：$i^k$ 是难点。利用第二类斯特林数展开： $$ \sum_{i=1}^{n} \binom{n}{i} i^k = \sum_{i=1}^{n} \binom{n}{i} \sum_{j=0}^{k} \begin{Bmatrix} k \ j \end{Bmatrix} i^{\underline{j}} $$ 交换求和顺序，并利用组合恒等式 $\binom{n}{i} i^{\underline{j}} = n^{\underline{j}} \binom{n-j}{i-j}$： $$ = \sum_{j=0}^{k} \begin{Bmatrix} k \ j \end{Bmatrix} n^{\underline{j}} \sum_{i=j}^{n} \binom{n-j}{i-j} = \sum_{j=0}^{k} \begin{Bmatrix} k \ j \end{Bmatrix} n^{\underline{j}} \cdot 2^{n-j} $$ 复杂度 $O(k^2)$（预处理第二类斯特林数），完全避开 $O(n)$。

例3（省选联考 2020 A 卷 P6620 组合数问题）

题意：给定 $n, x, p$ 和一个 $m$ 次多项式 $f(k)=\sum_{i=0}^{m} a_i k^i$，求： $$ \sum_{k=0}^{n} f(k) \cdot x^k \cdot \binom{n}{k} \pmod{p} $$ 解：这是下降幂最经典的降维打击场景。

换底：先将 $f(k)$ 转化为下降幂形式，设 $f(k)=\sum_{j=0}^{m} b_j k^{\underline{j}}$（用上述求法一求出 $b_j$）。
化简核心项：代入并用恒等式 $\binom{n}{k} k^{\underline{j}} = n^{\underline{j}} \binom{n-j}{k-j}$： $$ \sum_{k=0}^{n} k^{\underline{j}} \binom{n}{k} x^k = n^{\underline{j}} x^j \sum_{k=j}^{n} \binom{n-j}{k-j} x^{k-j} = n^{\underline{j}} x^j (1+x)^{n-j} $$
得出答案： $$ Ans = \sum_{j=0}^{m} b_j \cdot n^{\underline{j}} \cdot x^j \cdot (1+x)^{n-j} $$ 总复杂度 $O(m^2 + m \log n)$。下降幂的引入让原本无法下手的高次幂求和变成了简单的代数运算。

例4（DP优化 / 期望长度 $k$ 次方）

题意：在 01 串期望题（如 OSU! 变种）中，需要维护当前连续段长度 $len$ 的 $k$ 次方期望，$n$ 极大，$k \le 10$。解：直接维护 $E(len^k)$ 难度大，因为新增一个 $1$ 时长度变为 $len+1$，需要展开 $(len+1)^k$，涉及二项式卷积。改为维护下降幂 $E(len^{\underline{i}})$（$i=0..k$），新增 $1$ 时利用平移公式： $$ (len+1)^{\underline{i}} = len^{\underline{i}} + i \cdot len^{\underline{i-1}} $$ 这样单次转移仅需 $O(k)$，无需卷积。最后用第二类斯特林数反推 $E(len^k) = \sum \begin{Bmatrix} k \\ i \end{Bmatrix} E(len^{\underline{i}})$ 即可得到答案。

六、终极总结：竞赛解题闭环逻辑

工具	核心作用	竞赛典型场景
第二类斯特林数	普通幂 $\to$ 下降幂（$x^n = \sum \begin{Bmatrix} n \\ k \end{Bmatrix} x^{\underline{k}}$）	处理含 $k^i$ 的求和、自然数幂和、幂期望
第一类斯特林数	下降幂 $\to$ 普通幂（$x^{\underline{n}} = \sum s(n,k)x^k$）	圆排列计数、多项式逆转换
下降幂	差分/定和分公式优美、平移操作 $O(1)$	连续点值求和、省选组合数求和、DP状态转移优化

竞赛中的黄金三步走策略：遇到含普通幂 $k^i$ 的复杂求和（或期望）时： 1. 换底：用第二类斯特林数将 $k^i$ 转为下降幂 $k^{\underline{j}}$。 2. 化简：利用恒等式 $\binom{n}{k} k^{\underline{j}} = n^{\underline{j}} \binom{n-j}{k-j}$ 提取公因式，消除对 $k$ 的依赖。 3. 求解：结合二项式定理或预处理的斯特林数，在 $O(k^2)$（或 $O(k \log k)$）内出解。