Educational Codeforces Round 78 (Rated for Div. 2)

前言

挺好一开局，要是D没被卡能把E也写了说不定还能上橙，可惜。

题解

F - Cards

题目要求 $\frac{\sum_{i=1}^nC_n^i*i^k*(m-1)^{n-i}}{m^n}$ 把分母拿掉，只考虑分子。
根据第二类斯特林数的性质有 $n^k=\sum_{i=0}^{n}C_n^i*S(k,i)*i!\\$
代入上式得 $\sum_{i=1}^n C_n^i*(m-1)^{n-i} \sum_{j=0}^{\min(i,k)} C_i^j*S(k,j)*j!\\$
交换求和得 $\sum_{j=0}^{min(n,k)}\sum_{i=j}^n C_n^i*C_i^j*(m-1)^{n-i}*S(k,j)*j!\\$
把组合数拆开得 $\sum_{j=0}^{min(n,k)}\sum_{i=j}^n \frac{n!}{(n-i)!*i!}*\frac{i!}{(i-j)!*j!}*(m-1)^{n-i}*S(k,j)*j!\\$
化简得 $\sum_{j=0}^{min(n,k)}S(k,j)\sum_{i=j}^n \frac{n!}{(n-i)!*(i-j)!}*(m-1)^{n-i}\\$
再给后面的组合数乘点东西 $\sum_{j=0}^{min(n,k)}S(k,j)\sum_{i=j}^n \frac{n!}{(n-j)!}*\frac{(n-j)!}{(n-i)!*(i-j)!}*(m-1)^{n-i}\\$
于是就变成了 $\sum_{j=0}^{min(n,k)}S(k,j)\frac{n!}{(n-j)!}\sum_{i=j}^n C_{n-j}^{i-j}*(m-1)^{n-i}\\$
用 $i$ 替换 $i-j$ ，得到 $\sum_{j=0}^{min(n,k)}S(k,j)\frac{n!}{(n-j)!}\sum_{i=0}^{n-j} C_{n-j}^{i}*(m-1)^{n-j-i}\\$
最终的式子为 $\sum_{j=0}^{min(n,k)}S(k,j)*\frac{n!}{(n-j)!}*m^{n-j}\\$
第二类斯特林数 $O(k^2)$ 预处理, $O(k)$ 求解。