LuoguP5488 差分与前缀和

题意

给定一个长为\(n\)的序列\(a\)，求出其\(k\)阶差分或前缀和。结果的每一项都需要对\(1004535809\)取模。

打表找规律

先看前缀和，设\(n=5\)，\(k=4\)，按照阶从小到大把\(a_1\)在每个位置出现的次数列出来：

\[0阶：1,0,0,0,0\\
1阶：1,2,3,4,5\\
2阶：1,3,6,10,15\\
3阶：:1,4,10,20,35
\]

再把\(a_2\)的列出来可以发现就是\(a_1\)的表往后移了一位,所以第\(k\)阶前缀和第\(i\)位\(S_{k,i}=\sum_{j=1}^{i}{k-1+i-j\choose k-1}a_j\)，发现是卷积的形式，可以用NTT做。

再看差分，还是设\(n=5\)，\(k=4\)，把表列出来：

\[0阶：1,0,0,0,0\\
1阶：1,-1,0,0,0\\
2阶：1,-2,1,0,0\\
3阶：1,-3,3,-1,0\\
4阶：1,-4,6,-4,1
\]

类似于前缀和，可以归纳出\(S_{k,i}=\sum_{j=1}^i(-1)^{i-j}{k\choose i-j}\times a_j\)，也是卷积的形式，用NTT做。

最后注意\(k\)很大。所以组合数需要递推地来求，但\(k\)仍然很大。

注意到前缀和的组合数，设\(g_i={k-1+i\choose k-1}\)，列出\(g\)的递推式：

\[g_i=\frac{g_{i-1}\times (k+i-1)}{i}\%p\\
=(\frac{g_{i-1}}{i}\%p)\times ((k+i-1)\%p)\\
=(\frac{g_{i-1}}{i}\%p)\times ((k\%p+i-1)\%p)
\]

差分的递推式可以类似地推导，可以总结出我们可以直接对\(k\)取模。

#include<bits/stdc++.h>

#define rg register

#define il inline

#define cn const

#define gc getchar()

#define fp(i,a,b) for(rg int i=(a),ed=(b);i<=ed;++i)

using namespace std;

typedef cn int cint;

cint maxn=100010,G=3,invG=334845270,mod=1004535809;

il int rd(){

    rg int x(0),f(1); rg char c(gc);

    while(c<'0'||'9'<c)c=gc;

    while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc;

    return x*f;

}

il int read(){

    rg int x(0),f(1); rg char c(gc);

    while(c<'0'||'9'<c)c=gc;

    while('0'<=c&&c<='9')x=(10ll*x%mod+(c^48))%mod,c=gc;

    return x*f;

}

int n,m,t,a[maxn<<2],b[maxn<<2],inv[maxn],p[maxn];

int lim=1,l,rev,r[maxn<<2];

il int fpow(int a,int b,int ans=1){

    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;

    return ans;

}

il int finv(cint &n){return fpow(n,mod-2);}

il void ntt(int *a,cint &f){

    fp(i,0,lim)if(i<r[i])swap(a[i],a[r[i]]);

    for(rg int md=1;md<lim;md<<=1){

        rg int len=md<<1,Gn=fpow(f?G:invG,(mod-1)/len);

        for(rg int l=0;l<lim;l+=len){

            rg int Pow=1;

            for(rg int nw=0;nw<md;++nw,Pow=1ll*Pow*Gn%mod){

                rg int x=a[l+nw],y=1ll*a[l+nw+md]*Pow%mod;

                a[l+nw]=(x+y)%mod,a[l+nw+md]=(x-y+mod)%mod;

            }

        }

    }

}

int main(){

    n=rd(),m=read(),t=rd(); fp(i,1,n)a[i]=rd();

    inv[1]=1; fp(i,2,n)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

    p[0]=1; fp(i,1,n)p[i]=mod-p[i-1];

    if(!t){

        b[0]=1;

        fp(i,1,n)b[i]=1ll*(m+i-1)*inv[i]%mod *b[i-1]%mod;

    }

    else{

        b[0]=1;

        fp(i,1,n)b[i]=1ll*inv[i]*(m-i+1)%mod *b[i-1]%mod;

        fp(i,1,n)b[i]=1ll*b[i]*p[i]%mod;

    }

    while(lim<=n<<1)lim<<=1,++l; rev=finv(lim);

    fp(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

    ntt(a,1),ntt(b,1);

    fp(i,0,lim)a[i]=1ll*a[i]*b[i]%mod; ntt(a,0);

    fp(i,1,n) printf("%lld ",1ll*a[i]*rev%mod);

    return 0;

}

巴特西