第一类斯特林数\(\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\)，是一个质数）取模。
\(1\le k,n< 131072\)
\(S(n,k)=S(n-1,k-1)+(n-1)S(n-1,k)\)
考虑利用指数型生成函数来做
当\(k=1\)时，有\(F(x)=\sum_i(i-1)!\frac{x^i}{i!}\)
则答案为\(\frac{F(x)^k}{k!}\)
利用快速幂可以实现\(nlog^2\)
更快的采用多项式快速幂\(ln+exp\)实现\(nlogn\)
代码有空再写 需要很复杂的东西。