快速求斯特林数总结（洛谷模板题解）

题目链接

第一类斯特林数·行

第一类斯特林数·列

第二类斯特林数·行

第二类斯特林数·列

求一行第一类斯特林数

由第一类斯特林数的推论，(x^{overline{n}}=sum_iegin{bmatrix}n\iend{bmatrix}x^i)，分治FFT计算上升幂即可 (O(nlog^2n))。

求一列第一类斯特林数

由第一类斯特林数的定义，(egin{bmatrix}n\mend{bmatrix}) 是把 (N) 个不同的球划分成 (m) 个无区别的圆排列的方案数。

而把 (N) 个球排成圆排列的方案数的EGF为 (F(x)=sum_{i=1}^infty frac{(i-1)!}{i!}x^i)，那么答案的EGF则为 (frac{F^m(x)}{m!})，多项式快速幂即可。

求一行第二类斯特林数

考虑有 (n) 个球，染成 (c) 种不同颜色的方案数。

[c ^ n = sum_{i = 0} ^ c {cchoose i} * egin{Bmatrix} n \i end{Bmatrix} * i!]

二项式反演得

[egin{Bmatrix} n \m end{Bmatrix} * m! = sum_{i = 0} ^ m (-1)^{m-i} * {mchoose i} * i^n ]

卷积即可 (O(nlogn))。

求一列第二类斯特林数

由第二类斯特林数的定义，(egin{Bmatrix}n\mend{Bmatrix}) 是把 (N) 个不同的球划分成 (m) 个无区别的非空集合的方案数。

而把 (N) 个球组成非空集合的方案数的EGF为 (F(x)=sum_{i=1}^infty frac{x^i}{i!}=e^x-1)，那么答案的EGF则为 (frac{F^m(x)}{m!})，多项式快速幂即可。

求一排贝尔数

由贝尔数的定义，(Bell(n)) 表示 (n) 个不同的球划分成若干个非空集合的方案数。

而把 (N) 个球组成非空集合的方案数的EGF为 (F(x)=sum_{i=1}^infty frac{x^i}{i!}=e^x-1)，根据集合与划分的关系，那么答案的EGF则为 (e^{e^x-1})，多项式 Exp 即可。