斯特林数是组合数学概念，分为第一类斯特林数和第二类斯特林数。
第一类斯特林数是啥
第一类斯特林数表示为 \(\begin{bmatrix}n\\m \end{bmatrix}\)，表示的意义通俗得说就是 \(n\) 个不同的人坐 \(m\) 张圆桌的方案数（圆桌彼此相同，每张圆桌至少坐一人）。
考虑递推式，新加入一个人，要么是新开一张桌子，要么是插入到前面的桌子，由于是圆桌，所以可以考虑坐在哪个人的左边，得到递推式：
\[\begin{bmatrix}n\\m \end{bmatrix}=(n-1)\begin{bmatrix}n-1\\m \end{bmatrix}+\begin{bmatrix}n-1\\m-1 \end{bmatrix}
\]
暴力推时间复杂度 \(O(nm)\)。
第二类斯特林数是啥
第二类斯特林是表示为 \(\begin{Bmatrix}n\\m\end{Bmatrix}\)，表示把 \(n\) 个不同的求放到 \(m\) 个相同盒子的方案数，且不能有空盒。
还是考虑递推，本质上和上面一样，要么新开一个盒子，要么放前面的一个盒子里。
\[\begin{Bmatrix}n\\m\end{Bmatrix}=m\begin{Bmatrix}n-1\\m\end{Bmatrix}+\begin{Bmatrix}n-1\\m-1\end{Bmatrix}
\]
时间复杂度同样 \(O(nm)\)。
如果只需要求单点的值，那么可以考虑容斥，枚举一下有多少个盒子空着，然后就可以直接求，注意盒子相同，需要除以 \(m!\)。
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^{m-1} (-1)^i\binom{m}{i}(m-i)^n
\]
可以通过递推式来求其生成函数。
可以发现 \(F_k(x)=xF_{k-1}(x)+kxF_k(x)\)，然后可以得到
\[\sum_{i\ge k} \begin{Bmatrix}i\\k\end{Bmatrix} x^i=\frac{x^k}{\prod_{j=1}^k(1-jx)}
\]
快速求斯特林数。
可以在 \(O(n\log n)\) 的时间复杂度求出第一类，第二类斯特林数的一行或者一列上的值。
建议先学习 多项式计数。
第一类斯特林数·列
第一类斯特林数·行
第二类斯特林数·行
已知 \(n\)，对于每个 \(0\le m\le n\)，求 \(\begin{Bmatrix}n\\m\end{Bmatrix}\)。
\(n\le 10^5\)。
直接列出容斥式子。
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^{m-1} (-1)^i\binom{m}{i}(m-i)^n\\=\frac{1}{m!}\sum_{i=0}^{m-1} (-1)^i\frac{m!}{i!(m-i)!}(m-i)^n\\=\sum_{i=0}^{m-1} \frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!}
\]
显然卷积形式，预处理直接算就好了。
code
第二类斯特林数·列
咕咕咕
关于下降幂
形如 \(n^{\underline m}\) 的式子，表示
\[n^{\underline m} =\prod_{i=n-m+1}^n i=\frac{n!}{(n-m)!}
\]
一般写成后者。
有啥用呢，后面会介绍这个东西和普通幂的相互转换，它与组合数相乘有优美的性质：
\[\binom{n}{k} k^{\underline i}=\frac{n!}{k!(n-k)!}\frac{k!}{(k-i)!}=\frac{(n-i)!}{(n-k)!(k-i)!}\frac{n!}{(n-i)!}\\=\binom{n-i}{k-i}n^{\underline i}
\]
第一类斯特林数性质
\[x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}x^i\tag{1}
\]
考虑咋证明，先考虑 \(x=1\) 的特殊情况：
\[n!=\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}
\]
这个东西比较显然，因为每个排列 \(p\)，可以把 \(i\) 向 \(p_i\) 连一条边边，然后会形成一堆置换环，所以可以发现排列与任意放环的方案一一对应。
然后考虑证明最上面的式子，组合意义推一下，可以发现右边的 \(\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}x^i\) 的意思是把 \(n\) 个数分成任意个环，然后把每个环染成 \(1...x\) 的一种颜色。
令 \(f_x=\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}x^i\)，然后考虑再加入一个点，这个点要么是一个自环，有 \(x\) 种染色方案，要么是放在前面一个点的后面，有 \(n-1\) 种方案，所以可以得到转移式子：
\[f_{x+1}=(x+n-1)f_x
\]
由于 \(f_1\) 显然成立，所以归纳得证原结论正确。
可以发现，\((1)\) 式实际上就表示 \(x^{\overline n}\) 是第一类斯特林数的生成函数。
接下来证明
\[x^{\underline n}=\sum_{i=0}^n (-1)^{n-i} \begin{bmatrix}n\\i \end{bmatrix}x^i\tag{2}
\]
可以发现
\[x^{\underline n}=(-1)^n{(-x)}^{\overline n}=(-1)^n\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}(-x)^i=\\ \sum_{i=0}^n (-1)^{n-i} \begin{bmatrix}n\\i \end{bmatrix}x^i
\]
因此我们得到了上升下降幂转普通幂的方法。
第二类斯特林数性质
\[x^n=\sum_{i=1}^x \begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}\tag{3}
\]
证明比较简单：
\[x^n=\sum_{i=1}^x \begin{Bmatrix}n\\i\end{Bmatrix}i!\binom{x}{i}\\
=\sum_{i=1}^x \begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}
\]
注意此处 \(i\) 的上界也可以改成 \(n\)，因为当 \(i>n\) 时，后面的 \(\begin{Bmatrix}n\\i\end{Bmatrix}\) 就变成 \(0\)，如果 \(i>x\)，那么 \(\binom{x}{i}\) 就是 \(0\)。
就是考虑有 \(n\) 个不同的球放入 \(x\) 个不同的箱子，可以为空，那么右边就是枚举放了多少个箱子，第二步直接组合数展开就好了。
我们得到了普通幂转下降幂的方法。
结合 \((1),(2),(3)\)，我们做到了下降幂和普通幂的转换。
斯特林反演
和二项式反演形式上一模一样。
\[f(n)=\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix} g(i)\iff g(n)=\sum_{i=0}^n \begin{Bmatrix}n\\i \end{Bmatrix}(-1)^{n-i} f(i)
\]
证明这个，首先证明一个反转公式：
\[\displaystyle \sum\limits_{k=m}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \begin{bmatrix}k\\m\end{bmatrix}=[m=n]
\]
直接推式子：
\[m^n=\sum_{i=1}^m \begin{Bmatrix}n\\i\end{Bmatrix} m^{\underline i}=\sum_{i=1}^m \begin{Bmatrix}n\\i\end{Bmatrix}\sum_{j=0}^i(-1)^{i-j}\begin{bmatrix}i\\j \end{bmatrix}m^j
\]
交换一下枚举顺序：
\[=\sum_{j=0}^n m^j\sum_{i=j}^n (-1)^{i-j}\begin{Bmatrix}n\\i\end{Bmatrix}\begin{bmatrix}i\\j \end{bmatrix}
\]
可以发现，只有 \(j=n\) 时，后面部分等于 \(1\) ，然后可以发现 \(j\) 换成 \(n\) 后就直接证明了原式。
继续证明反演式子，如果 \(f(n)=\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix} g(i)\) 已经满足。
\[g(n)=\sum_{i=0}^n [i=n]g(i)=\sum_{i=0}^n g(i)\displaystyle \sum\limits_{k=i}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \begin{bmatrix}k\\i\end{bmatrix}\\
=\sum_{k=0}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \sum_{i=0}^kg(i)\begin{bmatrix}k\\i\end{bmatrix}\\
=\sum_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}(-1)^{n-k} f(k)
\]
证毕，斯特林反演和二项式反演本质差不多。
做题记录
思维难度基本递增。
P4609 \(\color{purple}{省选/NOI-}\)
问有多少个长度为 \(n\) 的排列 \(p\) 满足有 \(A\) 个不同的前缀最大值，有 \(B\) 个不同的后缀最大值，\(T\) 组数据，对 \(10^9+7\) 取模。
\(T\le 2\times 10^5,n\le 50000,A,B\le 100\)。
简单题，可以发现 \(n\) 必然出现在前缀和后缀最大值中，并且把序列分成两半，两边的最大值不相互影响，所以只需要考虑前缀最大值即可。
用 dp，设 \(f_{i,j}\) 表示 \(i\) 个数，\(j\) 个前缀最大值的方案数，考虑加入一个更小的值，那么这个值要么放在最前面形成一个新的前缀最大值，要么随便放在一个数的后面，容易得到转移方程。
\[f_{i,j}=(i-1)f_{i-1,j}+f_{i-1,j-1}
\]
会发现这个东西其实就是第一类斯特林数，然后枚举一下 \(n\) 的左边有多少个数，得到答案：
\[\sum_{i=1}^{n-1} \begin{bmatrix}i\\A-1 \end{bmatrix} \begin{bmatrix}n-i-1\\B-1 \end{bmatrix}\binom{n}{i}
\]
预处理之后时间复杂度 \(O(Tn)\)，寄。
考虑组合意义，上面的式子实际上就是把 \(n-1\) 个数放到 \(A+B-2\) 个环里去，然后把其中 \(A-1\) 个放到前面去，所以得到 \(O(1)\) 的式子：
\[\begin{bmatrix}n-1\\A+B-2 \end{bmatrix}\binom{A+B-2}{A-1}
\]
code
有个 加强版，\(n,A,B\le 10^5\)，一次询问。
直接分治 NTT 求，先鸽着。
P4827 \(\color{black}{NOI/NOI+/CTSC}\)
已知一棵 \(n\) 个点的树，令 \(dis(i,j)\) 表示 \(i\) 到 \(j\) 的最短路径上的边数，给定 \(k\)，对于每个 \(i\)，求 \(\sum_{j=1}^n dis(i,j)^k\)。
\(n\le 5\times 10^4,k\le 150\)。
简单题，适合斯特林数入门。
直接看式子，为了方便，设 \(D\) 表示两点距离：
\[D^k=\sum_{i=1}^D \begin{Bmatrix}k\\i \end{Bmatrix} i!\binom{D}{i}
\]
由于 \(k\) 不变，所以变化一下 \(i\) 的上界。
\[D^k=\sum_{i=1}^k \begin{Bmatrix}k\\i \end{Bmatrix} i!\binom{D}{i}
\]
可以发现只有最后一项 \(\binom{D}{i}\) 与 \(D\) 有关，也就是说只需要对于每个 \(i\) 求 \(\binom{D}{i}\) 之和即可。
直接树形 dp，\(f_{x,i}\) 表示 \(x\) 子树中的和，\(g_{x,i}\) 表示子树外的答案。
然后考虑转移，\(f\) 从下到上，\(g\) 从下到上。
每次相当于把 \(\sum \binom{D}{i}\) 变成 \(\sum \binom{D+1}{i}\)，显然 \(\binom{D+1}{i}=\binom{D}{i}+\binom{D}{i-1}\)，所以可以直接转移。
code
CF932E *2400
已知 \(n,k\)，求
\[\sum_{i=1}^n \binom{n}{i} i^k
\]
\(n\le 10^9,k\le 5000\)。
简单题，和上面一题差不多。
\[\sum_{i=1}^n \binom{n}{i} i^k=\sum_{i=1}^n \binom{n}{i} \sum_{j=1}^k \begin{Bmatrix}k\\j \end{Bmatrix} j!\binom{i}{j}\\
=\sum_{j=1}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \sum_{i=1}^n \binom{n}{i}\binom{i}{j}=\sum_{j=1}^k \begin{Bmatrix}k\\j \end{Bmatrix}j!\binom{n}{j}2^{n-j}
\]
预处理斯特林数后直接做就好了，时间复杂度 \(O(k^2)\)，用多项式预处理可以 \(O(k\log k)\)，神鱼的做法可以 \(O(k)\)。
code
P6620 \(\color{purple}{省选/NOI-}\)
已知 \(n,x\) 和一个 \(m\) 次多项式 \(f(k)=\sum_{i=0}^m a_ik^i\)，求
\[\sum_{k=0}^n f(k)\times x^k\times \binom{n}{k}
\]
答案对给定的 \(p\) 取模。
\(n,x\le 10^9,m\le \min(1000,n)\)
比较进阶的题，一开始一直在考虑 \(x^k\) 咋拆，结果发现根本不用。
考虑 \(f(k)\) 比较难处理，把它变成 \(f(k)=\sum_{i=0}^m b_ik^{\underline i}\) 的形式，这个可以直接斯特林做。
然后大力推就好了。
\[\sum_{k=0}^n f(k)\times x^k\times \binom{n}{k}=\sum_{k=0}^n \sum_{i=0}^m b_ik^{\underline i} \times x^k\times \binom{n}{k}\\
=\sum_{k=0}^n\sum_{i=0}^m b_ix^k\times n^{\underline i}\binom{n-i}{k-i}=\sum_{i=0}^m b_in^{\underline i}\sum_{k=0}^n x^k\times \binom{n-i}{k-i}
\]
此时把后面的 \(k-i\) 换成 \(k\)。
\[=\sum_{i=0}^m b_in^{\underline i}\sum_{k=0}^{n-i} x^{k+i}\times \binom{n-i}{k}=\sum_{i=0}^m b_in^{\underline i}x^i\sum_{k=0}^{n-i} x^k\times \binom{n-i}{k}=\\
\sum_{i=0}^m b_in^{\underline i}x^i(x+1)^{n-i}
\]
然后就算完了，预处理斯特林数，时间复杂度 \(O(m^2)\)。
code