F. Bags with Balls 第二类斯特林数

Bags with Balls

标号为奇数的个数为\(c=\frac{m+1}{2}\)

标号为偶数个数为\(w=m-c\)

答案显然为\(ANS=\sum_{i=1}^{n}C(n,i)c^iw^{n-i}i^k\)

直接算是\(O(n)\)的，但这道题\(n\)为\(1e9\)

考虑第二类斯特林数化简\(i^k\)

\(x^k=\sum_{i=1}^kC(x,i)s(k,i)i!\)

\(ANS=\sum_{i=1}^{n}C(n,i)c^iw^{n-i}\sum_{j=1}^kC(i,j)s(k,j)j!=\sum_{j=1}^ks(k,j)\sum_{i=j}^{n}c^iw^{n-i}\frac{n!}{(i-j)!(n-i)!}=\sum_{j=1}^ks(k,j)\sum_{i=j}^{n}c^iw^{n-i}\frac{n!(n-j)!}{(n-j)!(i-j)!(n-i)!}=\sum_{j=1}^ks(k,j)\frac{n!}{(n-j)!}\sum_{i=j}^{n}c^iw^{n-i}C(n-j,n-i)=\sum_{j=1}^ks(k,j)\frac{n!}{(n-j)!}\sum_{i=0}^{n-j}c^ic^jw^{n-i-j}C(n-j,n-i-j)=\sum_{j=1}^ks(k,j)\frac{n!c^j}{(n-j)!}\sum_{i=0}^{n-j}c^iw^{n-j-i}C(n-j,i)=\sum_{j=1}^ks(k,j)\frac{n!c^j}{(n-j)!}(c+w)^{n-j}=\sum_{j=1}^ks(k,j)\frac{n!c^j}{(n-j)!}m^{n-j}\)

做完啦。