P4948

· · 题解

记 S_k=\sum_{i=1}^n i^ka^i。

则使用错位相减法，有 aS_k=\sum_{i=1}^n i^ka^{i+1}。

上下相减，则 (a-1)S_k=(n^ka^{n+1}-a)-\sum_{x=2}^n ((x-1)^k-x^k)a^x。

然后那个 (x-1)^k 可以用二项式定理展开，则有 (x-1)^k-x^k=\sum_{i=0}^{k-1}C_k^i\times x^i\times(-1)^{k-i}。

运用这个结论，可以得到 \sum_{x=2}^n ((x-1)^k-x^k)a^x=\sum_{x=2}^n a^x\times (\sum_{i=0}^{k-1}C_k^i\times x^i\times(-1)^{k-i})。

然后求和符号换一下，我们就可以把对 n 的求和变成对 k 的求和了，可以得到 \sum_{i=0}^{k-1}C_k^i\times (-1)^{k-i}\times \sum_{x=2}^n (a^x\times x^i)。

然后你发现没法优化了。

但是你发现 \sum_{x=2}^n (a^x\times x^i) 这个形式好像在哪出现过。

这不就是题目要求的式子吗，只不过 k 变成了 i。

那么我们就努力凑出这样一个形式吧！这样就能递推求解了。

观察到他的 x 是从 2 到 n 遍历，那么我们给他加上再减去一个 a^1\times 1^i=a 即可，如下所示。

\sum_{i=0}^{k-1}C_k^i\times (-1)^{k-i}\times (\sum_{x=1}^n (a^x\times x^i)-a)=\sum_{i=0}^{k-1}C_k^i\times (-1)^{k-i}\times (S_i-a)

别忘了这个式子是 (a-1)\times S_k，所以我们还要除以 a-1。

但是你发现 i 可能等于 0。

考虑如果 k=0 怎么做。则 S_0=\sum_{i=1}^n a^i，就是一个等比数列求和，结果是 \frac{a\times (a^n-1)}{a-1}。

发现我们在好多地方都要除以 a-1，所以我们预处理 \frac 1{a-1} 的值。

时间复杂度 O(k^2)。

#include<bits/stdc++.h>
#define fs(i,x,y,z) for(register int i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(register int i=x;i>=y;i+=z)
#define int long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200001,inf=1e9+7;
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=(date<<3)+(date<<1)+(c^48);c=getchar();}
    return date*w;
}
int ksm(int a,int b){
    a%=inf;
    int ans=1ll;while(b){if(b&1)ans=ans*a%inf;a=a*a%inf;b=b>>1ll;}
    return ans;
}
int fac[N+1],inv[N+1],k,f[N],e; 
int c(int d,int u){return fac[d]*inv[u]%inf*inv[d-u]%inf;}
signed main(){
    fac[0]=inv[0]=1;
    fs(i,1,N,1) fac[i]=fac[i-1]*i%inf;
    inv[N]=ksm(fac[N],inf-2); 
    ft(i,N-1,1,-1) inv[i]=inv[i+1]*(i+1)%inf;
    int n=read(),a=read(),k=read();e=ksm(a-1,inf-2);
    f[0]=a*e%inf*(ksm(a,n)-1+inf)%inf;
    fs(i,1,k,1){
        int cur=1-2*bool(i&1);f[i]=(ksm(n,i)*ksm(a,n+1)%inf-a+inf)%inf;
        //左边的式子
        fs(j,0,i-1,1){
            f[i]=(f[i]+c(i,j)*cur*(f[j]-a)+inf)%inf;
            cur*=-1;
        }
        f[i]=(f[i]+inf)%inf*e%inf;
        //这里是(a-1)S，要除以a-1 
    }
    cout<<f[k];
    return 0;
}