为了方便: 简记第一类斯特林数为S_1,第二类斯特林数为S_2

\begin{aligned} {n\brack k}&=(n-1){n-1\brack k}+{n – 1\brack k – 1} \\ \binom nm &= m\binom {n-1}{m}+\binom {n-1}{m-1}\\ \end{aligned}


1. S2-行

  • S_2(n,i) (i\in[0,n]) n\le 10^5

递推显然不可取, 可以考虑S_2本身的意义在于将元素分成若干不区分的集合的方案数.

那么有较为显然的式子:

n^m=\sum_{i=0}^n \binom{n}{i} S_2(m, i)

直接对它进行二项式反演即可.

转化后的通项公式也许有点用处:

S2(n,m)=\sum_{i=0}^m \frac{(-1) ^{m-i}\cdot i ^ n}{i!\cdot (m-i)!}

利用\text{fft}优化变成O(n\log n).

2. S2-列

  • S_2(i,k) (i\in[0,n]) n, k\le 10^5

仔细观察它的递推式:

\binom nm = m\binom {n-1}{m}+\binom {n-1}{m-1}

发现mS_2的递推系数都仅与m有关, 而不是n (n为第n行的意思).

即用生成函数的方法表示为:

S_m(x)=S_m(x)\cdot mx + S_{m-1}x\\

即:

\begin{array}{c}{S_{m}(x)=\frac{x}{1-m x} S_{m-1}(x)} \\ {S_{m}(x)=\frac{x^{m}}{\prod_{i=1}^{m}(1-i x)}}\end{array}

求逆+分治\text{fft}即可, 复杂度O(n\log^2 n)

跑的会比另一种\exp做法快…

3. S1-行

  • S_1(n,i) (i\in[0,n]) n\le 10^5

同样, 仔细观察它的递推式:

{n\brack k}=(n-1){n-1\brack k}+{n – 1\brack k – 1}

发现nS_1的递推系数都仅与n有关, 而不是m (m为第m列的意思).

同样可表示为:

s_n(x) = (n-1)\cdot s_{n-1}(x) + x\cdot s_{n-1}(x)\\

进一步展开, 发现:

x^{\overline{n}}=\sum_{i}\left[\begin{array}{l}{n} \\ {i}\end{array}\right] x^{i}

如何求n阶下降幂?

考虑倍增的方法, 设f(x)=x^{\overline{n}}=\sum_{i} a_i x^i,\ g(x)=(x+n)^{\overline{n}}

我们要求x^{\overline{2n}}

即所求为f* g, 关键在于如何求g

\begin{aligned} g=&f(x+n) \\ =& \sum_{i} f_{i}(x+n)^{i} \\ =& \sum_{j} x^{j} \sum_{i} f_{i}\left(\begin{array}{c}{i} \\ {j}\end{array}\right) n^{j-i} \\ =& \sum_{j} x^{j} \frac{1}{j !} \sum_{i} i ! f_{i} \frac{n^{j-i}}{(j-i) !} \end{aligned}

就是一个卷积形式, 只不过贡献i,j\to i-j

那么下标移位就好了.

4. S1-列

  • S_1(i,k) (i\in[0,n]) n, k\le 10^5

口胡一波

类比”S2-行”的做法: S_1本身的意义在于将元素分成若干不区分的环的方案数.

故:

n!=\sum_i S_1(n,i)

该式子证明请见: zzd的偷学笔记

没用, 因为不能够二项式反演.

进一步的, 考虑生成函数:

记答案的S(x), B(x)=k!\cdot S(x), 且A(x) = \sum_i \frac {(i-1)!}{i!} x^i .

(i-1)!表示圆排列.

那么我们有B(x)=A^k(x), 然后多项式快速幂即可…