求\(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!}\)
卷积即可。