P5396 第二类斯特林数·列
第二类斯特林数·列
第二类斯特林数\(\begin{Bmatrix} n \\m \end{Bmatrix}\)表示把n个不同元素划分成m个相同的集合（不能有空集）的方案数。
给定\(n,k\)，对于所有的整数\(i\in[0,n]\)，你要求出\(\begin{Bmatrix} i \\k \end{Bmatrix}\)
由于答案会非常大，所以你的输出需要对\(167772161(2^{25}\cdot 5+1)\)，是一个质数）取模。
\(n,k\le 131072=2^{17}\)
\(s(n,m)=ms(n-1,m)+s(n-1,m-1)\)
设\(F_k=\sum a_ix^i=\sum s(i,k)x^i\)
\(F_k=\sum (s(i-1,k-1)+ks(i-1,k))x^i=xF_{k-1}+xkF_k=\frac{x}{1-kx}F_{k-1}\)
显然\(F_0=1\)故\(F_k=x^k\Pi_{i=1}^{k}\frac{1}{1-ix}\)
而\(\Pi_{i=1}^k(1-ix)=x^k\Pi_{i=1}^k(x^{-1}-i)\)
设\(y=x^{-1}\)则\(RHS=y^{-(k+1)}y^{\underline {k+1}}\)
考虑求\(y^{\underline {n}}\)
若\(n\&1==1\)，\(y^{\underline {n}}=y^{\underline {n-1}}(y-n+1)\)
若\(n\&1==0\)，设\(m=\frac{n}{2}\)，\(y^{\underline {n}}=y^{\underline {2m}}=y^{\underline {m}}(y-m)^{\underline {m}}\)
设\(g(y)=y^{\underline {m}}=\sum_{i=0}^ma_iy^i,g(y-m)=\sum_{i=0}^ma_i(y-m)^i=\sum_{i=0}^ma_i\sum_{j=0}^iC(i,j)y^j(-m)^{i-j}=\sum_{j=0}^m\sum_{i=j}^mC(i,j)a_iy^j(-m)^{i-j}=\sum_{j=0}^m\frac{y^j}{j!}\sum_{i=j}^ma_ii!\frac{(-m)^{i-j}}{(i-j)!}\)
卷积即可这部分可以复杂度为\(nlogn\)
之后将序列翻转即可得到\(\Pi_{i=1}^k(1-ix)\)
再利用多项式求逆可得\(\Pi_{i=1}^{k}\frac{1}{1-ix}\)
就可以求出\(F_k\)。