题解 P4948 数列求和

· · 题解

可能更好的阅读体验

题目大意

给定 n,a,k，求

\sum_{i=1}^ni^ka^i

答案对 10^9+7 取模。

\texttt{Data Range:} 1\le n\le 10^{18},1\le a\le 10^9,1\le k\le 2000

题解

前置芝士：有限微积分

除了扰动法，本题还有一种较为简洁的有限微积分做法。

普通幂难以处理，用第二类斯特林数转为下降幂：

\sum_{i=1}^ni^ka^i=\sum_{j=0}^k{k\brace j}\sum_{i=1}^ni^{\underline{j}}a^i =\sum_{i=0}^k{k\brace i}{\sum}_1^{n+1}x^{\underline{i}}a^x\delta x

若 a=1,\displaystyle\sum x^{\underline{i}}\delta x=\dfrac{x^{\underline{i+1}}}{i+1}。

若 a\not=1，对于 \displaystyle{\sum}x^{\underline{i}}a^x\delta x，由分部求和公式易得出其递推式

\sum u\Delta v=uv-\sum \mathrm{E}v\Delta u {\sum}x^{\underline{i}}a^x\delta x=\dfrac{x^{\underline{i}}a^x}{a-1}-\sum \dfrac{a^{x+1}}{a-1}ix^{\underline{i-1}}\delta x {\sum}x^{\underline{i}}a^x\delta x=\dfrac{x^{\underline{i}}a^x}{a-1}-\dfrac{ai}{a-1}\sum a^xx^{\underline{i-1}}\delta x

求出第二类斯特林数后 \Theta(k) 递推即可。

复杂度瓶颈为求第二类斯特林数，本题可 \Theta(k^2) 递推，
亦可使用 NTT \Theta(k\log^2 k) 或 \Theta(k\log k) 求解。

Code

/* 
solution P4948 with finite calculus
made by wanrzone 2021-11-1 16:55
*/ 
#include<stdio.h>
#include<string.h>
typedef unsigned long long ull;
typedef unsigned int word;
const word mod=1e9+7;
inline ull pow_(word a,word b){//快速幂
    word ans=1;
    for(;b;b>>=1){
        if(b&1) ans=1ull*ans*a%mod;
        a=1ull*a*a%mod;
    }
    return ans;
}
word brace[2048][2048];//第二类斯特林数
word a,k,under[2048];
inline ull getans(ull num){
    if(a==1){//a=1 的情况特判
        num%=mod;
        ull ans=0,get=1;
        for(word i=0;i<=k;++i){
            get=get*(num+mod-i)%mod;
            ans+=pow_(i+1,mod-2)*brace[k][i]%mod*get%mod;
        }
        return ans%mod;
    }
    under[0]=pow_(a,num%(mod-1))*pow_(a-1,mod-2)%mod;
    num%=mod;
    for(word i=0;i<k;++i)
        under[i+1]=(num+mod-i)*under[i]%mod;
    //O(n) 递推 $\dfrac{x^{\underline{i}}a^x}{a-1}$
    ull ans=0,get=0;
    num=pow_(a-1,mod-2)*(mod-a)%mod;
    for(word i=0;i<=k;++i){
        get=(get*num%mod*i+under[i])%mod;
        //O(k) 递推 $\sum x^{\underline{i}}a^x\delta x$
        ans+=get*brace[k][i]%mod; //计入答案
    }
    return ans%mod;
}
ull n;
int main(){
    scanf("%llu%u%u",&n,&a,&k);
    brace[0][0]=1;
    for(word n=1;n<=k;++n)//预处理第二类斯特林数
        for(word m=1;m<=n;++m)
            brace[n][m]=(1ull*m*brace[n-1][m]
                +brace[n-1][m-1])%mod;
    printf("%llu\n",(getans(n+1)+mod-getans(1))%mod);//不定和式->定和式
    return 0;
}