第一类斯特林数·列
第一类斯特林数·列
题目描述
第一类斯特林数 \(\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
输入 #1
3 2
输出 #1
0 0 1 3
说明/提示
\(1\leqslant k,n< 131072\)。
我们可以对\(k=1\)的情况构造指数级生成函数，即：
\[S(x)= \sum_{i=0}^n \frac{i!x^i}{(i-1)!}
\]
因为很显然\(\begin{bmatrix} n \\ 1 \end{bmatrix}=(n-1)!\)。
那么，我们就可以得到，对于\(k\)为任意数情况的指数级生成函数就是：
\[\frac{S(x)^k}{k!}
\]
除以\(k!\)的主要原因是我们用指数级生成函数的环排列其实是有顺序。就比如\([2,3,1][1,2]\)和\([1,2][2,3,1]\)是等价的，但是我们算重了。
上面这个式子如果要美观一点就是：
\[\frac{\left(\ln \frac{1}{1-x}\right)^k}{k!}
\]
这个可以通过泰勒展开得到。
不过不管用哪种表达方式都可以，直接多项式快速幂就好了。