P5395 第二类斯特林数·行

求\(s(n,i),i\le n,n\le 2^{18}\)

\(k^n=\sum_{i=1}^ks(n,i)i!C(k,i)\)

设\(f_k=k^n,g_i=s(n,i)i!\)

\(f_k=\sum_{i=0}^kg_iC(k,i)\)

由二项式反演

\(g_k=\sum_{i=0}^k(-1)^{k-i}f_iC(k,i)\)

展开来\(s(n,k)k!=\sum_{i=0}^k(-1)^{k-i}i^nC(k,i)\)

即\(s(n,k)=\sum_{i=0}^k(-1)^{k-i}\frac{i^n}{(k-i)!i!}\)

卷积即可。