[bzoj3157]-国王奇遇记

Concrete Mathematics

加强版什么的之后再说吧……

题目(BZOJ)

 

来说说这题~

我们首先构造一个函数$$F(n,k)=\sum_{i=1}^ni^{k}m^{i}$$,然后就来推:
$$\begin{flushleft}$$
$$F(n+1,k)$$

$$=\sum_{i=1}^{n+1}i^{k}m^i$$

$$=m+\sum_{i=2}^{n+1}i^{k}m^i$$

$$=m+\sum_{i=1}^n(i+1)^{k}m^{i+1}$$

$$=m+m\sum_{i=1}^n(i+1)^km^i$$

$$=m+m\sum_{i=1}^n\sum_{j=0}^{k}C_{k}^{j}i^{j}m^{i}$$

$$=m+m\sum_{j=0}^kC_{k}^{j}\sum_{i=1}^ni^{j}m^{i}$$

$$=m+m\sum_{j=0}^kC_{k}^{j}F(n,j)$$

发现这只能一个一个推,我们来考虑倍增推:

$$F(2n,k)$$

$$=\sum_{i=1}^{2n}i^km^i$$

$$=\sum_{i=1}^ni^km^i+\sum_{i=n+1}^{2n}i^km^i$$

$$=F(n,k)+\sum_{i=1}^n(i+n)^km^{i+n}$$

$$=F(n,k)+m^n\sum_{i=1}^n\sum_{j=0}^kC_{k}^{j}i^jn^{k-j}m^i$$

$$=F(n,k)+m^n\sum_{j=0}^kC_{k}^{j}n^{k-j}\sum_{i=1}^nm^ii^j$$

$$=F(n,k)+m^n\sum_{j=0}^kC_{k}^{j}n^{k-j}F(n,j)$$
然后就可以递推or递归了,然而我写的是递归,中间需要一个二维map来记忆化一下,就可以了。

 

发表评论