题目概述

给出一个数组，求这个数组的 $k$ 次前缀和（前缀和的前缀和的前缀和……）。

解题报告

就是这题套个NTT，水博客真开心。可能略有卡常……

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxt=1<<18,MOD=998244353;

int n,INV[maxn+5],a[maxt+5],c[maxt+5];LL K;
int rev[maxt+5],pw[2][maxt+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void writei(int x){
    static int buf[30],len=0;do buf[len++]=x%10,x/=10; while (x);
    while (len) putchar(buf[--len]+48);
}
inline void Make(int n){
    INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    c[0]=1;for (int i=1;i<=n;i++) c[i]=(K-1+i)%MOD*INV[i]%MOD*c[i-1]%MOD;
}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,a[i+j]=(x+y)%MOD,a[i+j+k]=(x+MOD-y)%MOD;
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(K);Make(n);for (int i=0;i<n;i++) readi(a[i]);
    int t;for (t=1;t<(n<<1);t<<=1);Pre(t);NTT(a,t,1);NTT(c,t,1);
    for (int i=0;i<t;i++) a[i]=(LL)a[i]*c[i]%MOD;NTT(a,t,-1);
    for (int i=0;i<n;i++) writei(a[i]),puts("");return 0;
}