第二类斯特林数·列
题目描述
第二类斯特林数 \(\begin{Bmatrix} n \\m \end{Bmatrix}\) 表示把 \(n\) 个不同元素划分成 \(m\) 个相同的集合（不能有空集）的方案数。
给定 \(n,k\)，对于所有的整数 \(i\in[0,n]\)，你要求出 \(\begin{Bmatrix} i \\k \end{Bmatrix}\)。
由于答案会非常大，所以你的输出需要对 \(167772161\)（\(2^{25}\times 5+1\)，是一个质数）取模。
输入格式
一行两个正整数 \(n,k\)，意义见题目描述。
输出格式
共一行 \(n+1\) 个非负整数。
你需要按顺序输出 \(\begin{Bmatrix} 0 \\k \end{Bmatrix},\begin{Bmatrix} 1 \\k \end{Bmatrix},\begin{Bmatrix} 2 \\k \end{Bmatrix},\dots,\begin{Bmatrix} n \\k \end{Bmatrix}\) 的值。
输入 #1
3 2
输出 #1
0 0 1 3
把答案设成多项式
\[H_k = \sum_{i=0}^\infty \begin{Bmatrix} i \\ k \end{Bmatrix} x^i
\]
然后,我们发现
\[H_k = \sum_{i=0}^\infty \left( \begin{Bmatrix} i-1 \\ k-1 \end{Bmatrix} + k \begin{Bmatrix} i-1 \\ k \end{Bmatrix} \right) x^i
\]
\[= \sum_{i=0}^\infty \begin{Bmatrix} i-1 \\ k-1 \end{Bmatrix} x^i + k \sum_{i=0}^\infty \begin{Bmatrix} i-1 \\ k \end{Bmatrix} x^i
\]
\[= x \sum_{i=0}^\infty \begin{Bmatrix} i \\ k-1 \end{Bmatrix} x^i + kx \sum_{i=0}^\infty \begin{Bmatrix} i \\ k \end{Bmatrix} x^i = xH_{k-1} + kxH_k
\]
整理一下就是
\[H_k = xH_k + kxH_{k-1}
\]
那么
\[H_k = \frac{x}{1-kx} H_{k-1}
\]
根据递推公式能得到边界就是 \(H_0=1\)，那么
\[H_k = H_0 \prod_{i=1}^k \frac{x}{1-ix} = x^k \left( \prod_{i=1}^k (1-ix) \right)^{-1}
\]
重点就是怎么算
\[\prod_{i=1}^k (1-ix)
\]
有
\[\prod_{i=1}^k (1-ix) = \prod_{i=1}^k x\left( \frac{1}{x} - i \right) = x^k \prod_{i=1}^k (x^{-1} - i)
\]
又\(\prod_{i=1}^k (x-i)\)翻转过来之后就是\(x^k \prod_{i=1}^k (x^{-1} - i)\)
那么注意到
\[\prod_{i=1}^k (x-i) = \frac{x^{\underline{k+1}}}{x}
\]
我们只要求出 \(x^{\underline{k+1}}\) 就好。
又\(x^{\underline{2n}} = x^{\underline{n}} * (x-n)^{\underline{n}}\)
我们知道一个多项式 $F(x)$ 可以快速求出 $F(x-c)$，方法：
首先\(c=\text{mod}-c\),那么问题变成\(F(x+c)\)
设\(F(x)\)的系数为\(f[0...n]\)
\[F(x+c)= \sum_{i=0}^n f[i](x+c)^i
\]
,显而易见吧!
\[= \sum_{i=0}^n f[i] \sum_{j=0}^i \binom{j}{i}x^j c^{i-j}
\]
(二项式定理)
\[= \sum_{i=0}^n f[i] \sum_{j=0}^i \frac{i!}{j!(i-j)!}x^j c^{i-j}
\]
\[= \sum_{i=0}^n f[i]i! \sum_{j=0}^i \frac{x^j}{j!} \frac{c^{i-j}}{(i-j)!}
\]
\[= \sum_{j=0}^n \frac{x^j}{j!} \sum_{i=j}^n f_i i! \frac{c^{i-j}}{(i-j)!}
\]
(交换求和号)
我们要求的就是
\[g[j]*j! = \sum_{i=j}^n f[i]i! \frac{c^{i-j}}{(i-j)!}
\]
我们设\(p[n]=f[n]n!; h[n]= \frac{c^n}{n!}\),则
\[g[j]j! = \sum_{i=j}^n p[i]h[i-j]
\]
但是我们发现\(i+i-j \neq\)定值 , 我们把\(p\)翻转,得到
\[g[j]j! = \sum_{i=j}^n p'[n-i]h[i-j]
\]
那么\(n-i+i-j=n-j\)这就和\(i\)无关了。
卷起来之后翻转即可,记得最后乘上\(j!\)。
