题解 P4948 【数列求和】

· · 题解

稍微扰动一下就好了。

\sum_{i=1}^n i^k a^i=\sum_{i=1}^{n-1}i^k a^i +n^k a^n=\sum_{i=1}^{n-1}(i+1)^k a^{i+1}+a \therefore \sum_{i=1}^{n-1}[(i+1)^ka^{i+1}-i^k a^i]=n^ka^n-a

对(i+1)^k二项式展开

\sum_{i=1}^{n-1}[a^{i+1}\sum_{j=0}^k\binom{k}{j}i^j -i^k a^i]=n^ka^n-a \sum_{i=1}^{n-1}[a^{i+1}\sum_{j=0}^{k-1}\binom{k}{j}i^j + i^ka^{i+1} -i^k a^i]=n^ka^n-a \sum_{i=1}^{n-1}a^{i+1}\sum_{j=0}^{k-1}\binom{k}{j}i^j + (a-1)\sum_{i=1}^{n-1}i^k a^i=n^ka^n-a \sum_{j=0}^{k-1}\binom{k}{j}\sum_{i=1}^{n-1}a^{i+1}i^j + (a-1)\sum_{i=1}^{n-1}i^k a^i=n^ka^n-a a\sum_{j=0}^{k-1}\binom{k}{j}\sum_{i=1}^{n-1}i^j a^i + (a-1)\sum_{i=1}^{n-1}i^k a^i=n^ka^n-a

设F(k)=\sum_{i=0}^{n-1} i^k a^i

a\sum_{j=0}^{k-1}\binom{k}{j}F(j) + (a-1)F(k)=n^ka^n-a (a-1)F(k)=-a\sum_{j=0}^{k-1}\binom{k}{j}F(j) +n^ka^n-a F(k)=\dfrac{-a\sum_{j=0}^{k-1}\binom{k}{j}F(j) +n^ka^n-a}{a-1}

我们可以很容易算出F(0)的值，然后预处理组合数，就可以在O(k^2)时间内递推出F(k)。

最后的答案为F(k)+n^k a^n。

那a=1呢？

此时有

\sum_{j=0}^{k-1}\binom{k}{j}F(j)=n^k-1 F(k-1)\times\binom{k}{k-1}+ \sum_{j=0}^{k-2}\binom{k}{j}F(j)=n^k-1 F(k-1)\times \binom{k}{k-1}=n^k-1-\sum_{j=0}^{k-2}\binom{k}{j}F(j) F(k-1)=\dfrac{n^k-1-\sum_{j=0}^{k-2}\binom{k}{j}F(j)}{\binom{k}{k-1}}

即

F(k)=\dfrac{n^{k+1}-\sum_{j=0}^{k-1}\binom{k+1}{j}F(j)}{\binom{k+1}{k}}