定义
第二类斯特林数 \(n\brace m\) 表示 \(n\) 个两两不同的元素划分为 \(m\) 个互不区分的非空子集的方案数；第一类斯特林数 \(n \brack m\) 表示 \(n\) 个两两不同的元素划分为 \(m\) 个互不区分的非空轮换（可以理解为环）的方案数。
第二类斯特林数的递推式：\({n\brace m}={n-1\brace m-1}+m{n-1\brace m}\)。
第一类斯特林数的递推式：\({n\brack m}={n-1\brack m-1}+(n-1){n-1\brack m}\)。
第二类斯特林数 \(\bullet\) 行
用容斥原理和二项式反演可以证明：
\[{n \brace m}=\sum_{i=0}^m \frac{(-1)^{m-i}i^n}{i!(m-i)!} \]可以用卷积计算，\(O(n\log n)\)。
第二类斯特林数 \(\bullet\) 列
一个集合装 \(i\) 个元素且非空的方案的 EGF：\(\sum _{i=1}^{+\infty} \frac{x^i}{i!}=e^x-1\)。
求它的 \(m\) 次方就得到 \(m\) 个集合的 EGF，也就得到一列的第二类斯特林数。
因为是 EGF，所以要乘上 \(i!\)；因为集合互不区分，所以要除以 \(m!\)。
先 \(\ln\) 再 \(\exp\) 做多项式快速幂，\(O(n\log n)\)。
第一类斯特林数 \(\bullet\) 列
类似的，列出一个轮换的 EGF：\(\sum_{i=1}^{+\infty} \frac{(i-1)!x^i}{i!}=\sum_{i=1}^{+\infty}\frac{x^i}{i}\)。
这里乘以 \((i-1)!\) 是因为有 \((i-1)!\) 种轮换的排法。
同样求 \(m\) 次幂，\(O(n\log n)\)。
第一类斯特林数 \(\bullet\) 行
感觉是最难写的，也是 OI-Wiki 这四种中唯一一个没给代码的。
根据公式，构造同一行第一类斯特林数的生成函数：
\[\begin{aligned} F_n(x)&=(n-1)F_{n-1}(x)+xF_{n-1}(x)\\ &=\prod_{i=0}^{n-1}(x+i)\\ &=\frac{(x+n-1)!}{(x-1)!}\\ &=x^{\overline n} \end{aligned} \]考虑倍增，\(x^{\overline {2n}}=x^{\overline n}(x+n)^{\overline n}\)。已经求出了 \(x^{\overline n}=f(x)=\sum_{i=0}^n a_ix^i\)，要求出 \(f(x+k)\)。
\[\begin{aligned} f(x+k)&=\sum_{i=0}^na_i(x+k)^i\\ &=\sum_{i=0}^na_i\sum_{j=0}^i {i\choose j}x^jk^{i-j}\\ &=\sum_{i=0}^nx_i\sum_{j=i}^n{j\choose i}k^{j-i}a_j\\ &=\sum_{i=0}^n\frac{x^i}{i!}\sum_{j=i}^n \frac{k^{j-i}}{(j-i)!}j!a_{j} \end{aligned} \]是一个差卷积的形式，时间复杂度是 \(O(n\log n)\)。
标签：overline,frac,斯特林,sum,笔记,学习,brace,EGF From： https://www.cnblogs.com/fydj/p/-/stirling