题解 CF932E 【Team Work】

2019-01-07 08:09:15


给个好理解一点的过程。

首先你要知道 $m^n=\sum\limits_{i=0}^mC_m^i\cdot S(n,i)\cdot i!$ 。这里的 $S(\,)$ 是第二类斯特林数。

然后就可以大力推式子:

$\quad\sum\limits_{i=1}^nC_n^i\cdot i^k$

$=\sum\limits_{i=1}^nC_n^i\sum\limits_{j=0}^iC_i^j\cdot S(k,j)\cdot j!\qquad\text{(按上面的式子展开)}$

$=\sum\limits_{i=1}^n\frac{n!}{i!(n-i)!}\sum\limits_{j=0}^i\frac{i!}{j!(i-j)!}\cdot S(k,j)\cdot j!\qquad\text{(拆组合数)}$

$=\sum\limits_{i=1}^n\frac{n!}{(n-i)!}\sum\limits_{j=0}^i\frac{S(k,j)}{(i-j)!}\qquad\text{(约分)}$

$=\sum\limits_{j=0}^nS(k,j)\sum\limits_{i=j}^n\frac{n!}{(n-i)!}\cdot\frac{1}{(i-j)!}\qquad\text{(换个位置)}$

$=\sum\limits_{j=0}^{\min(n,k)}S(k,j)\sum\limits_{i=j}^n\frac{n!}{(n-i)!}\cdot\frac{1}{(i-j)!}\qquad\text{(j>k时S(k,j)为0)}$

$=\sum\limits_{j=0}^{\min(n,k)}S(k,j)\sum\limits_{i=0}^n\frac{n!}{(n-j)!}\cdot\frac{(n-j)!}{(n-i)!(i-j)!}\qquad\text{(分式上下同乘(n-j)!再移一下)}$

$=\sum\limits_{j=0}^{k}S(k,j)\frac{n!}{(n-j)!}\sum\limits_{i=0}^nC_{n-j}^{i-j}\qquad\text{(移一下+还原组合数)}$

$=\sum\limits_{j=0}^{k}S(k,j)\frac{n!}{(n-j)!}2^{n-j}\qquad\text{(组合数的性质?)}$

$O(k^2)$ 预处理 $S(\,)$ 就行了。

代码见blog