题解 P4948 【数列求和】

· · 题解

诶，我来搬运一下出题人的题解吧。

以下是我结合自己的理解所写，如有不对请大佬指出。

解析

观察到k的值很小，从此处下手。

设f_{n}(x)=\sum_{i=1}^n{i^x}\times{a^i},答案即为f(k).

那么有a\times{f_{n}(x)}=\sum_{i=1}^n{i^x}\times{a^{i+1}}.

考虑$\sum^n_{i=2}((i-1)^x-i^x)\times{a^i}$, $\because (a-1)^k=\sum^k_{j=0}C(k,j)\times{a^j}\times(-1)^{k-j}$, $\therefore \sum_{i=2}^n((i-1)^x-i^x)\times{a^i} =\sum^n_{i=2}(\sum^{x-1}_{j=0}C(x,j)\times{i^j}\times(-1)^{x-j})\times{a^i} =\sum^{x-1}_{j=0}C(x,j)\times(-1)^{x-j}\times(\sum^n_{i=2}i^j\times{a^i}) $\therefore f_n(x)=\frac{n^x\times{a^{n+1}}-a+\sum^{x-1}_{j=0}C(x,j)\times(-1)^{x-j}\times(f_n(j)-a)}{a-1}

观察到上式可以O(n)计算，一共n个值，所以可以O(n^2)完成递推。

代码如下


#include<iostream>
#include<cstdio>
#include<cstdlib>
#define re register
#define LL long long
#define N 3005
using namespace std;
const int Mod=1e9+7;
LL n,a,k,power_a,c[N][N],inv_a,f[N];
LL power(LL x,LL P){
    LL r=1; x%=Mod;
    while(P){ if(P&1) r=r*x%Mod; x=x*x%Mod; P>>=1; }
    return r;
}
int main(){
    scanf("%lld%lld%lld",&n,&a,&k);
    power_a=power(a,n+1);
    for(re int i=0;i<=k;++i){
        c[i][0]=1ll;
        for(re int j=1;j<=i;++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%Mod;
    }
    inv_a=power(a-1,Mod-2);
    f[0]=inv_a*a%Mod*(power(a,n)-1)%Mod;
    for(re int i=1;i<=k;++i){
        f[i]=power_a*power(n,i)%Mod-a;
        for(re int j=i-1,t=-1;~j;--j,t=-t) f[i]=(f[i]+c[i][j]*t*(f[j]-a))%Mod;
        f[i]=(f[i]+Mod)*inv_a%Mod;
    }
    printf("%lld\n",f[k]);
    return 0;
}

后记

此题要点：

$2.$利用错位相减处理数列和式。 $3.$和式变换中，交换求和符号是常用的技巧。