Cptraser/ 三月 19, 2019/ 2019.3/ 0 comments

题面传送门

对原数列a建生成函数:A=\sum_{i=0}^{n-1}a_ix^i

求一次前缀和相当于将A卷上生成函数B=\sum_{i=0}^{n-1}x^i\ \ (mod\ \ x^n)

相当于我们要求A·B^{k-1}\ \ (mod\ \ x^n)

直接快速幂会T,但B有一些奇妙的性质:

B^k(x)的意义是选k个自然数使得和为x

通过插板法得知B^k(x)={x+k\choose x}

那么我们直接NTT即可。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int Mod=998244353,Maxn=1000005;
int Ksm(int x,int y){
    int res=1;for(;y;y>>=1,x=(LL)x*x%Mod)if(y&1)res=(LL)res*x%Mod;return res;
}
const int g=3,invg=Ksm(g,Mod-2);

int r[Maxn],len=1,L;
void NTT(int *A,int Opt){
    for(int i=0;i<len;i++)if(i<r[i])swap(A[i],A[r[i]]);
    for(int i=1;i<len;i<<=1){
        long long Wn=Ksm(Opt>0?g:invg,(Mod-1)/(i<<1));
        for(int j=0;j<len;j+=(i<<1)){
            long long w=1;
            for(int k=0;k<i;k++,w=w*Wn%Mod){
                int x=A[j+k],y=w*A[i+j+k]%Mod;
                A[j+k]=(x+y)%Mod;
                A[i+j+k]=(x-y+Mod)%Mod;
            }
        }
    }
    if(Opt<0)for(int i=0,inv=Ksm(len,Mod-2);i<len;i++)A[i]=(LL)A[i]*inv%Mod;
}

long long K;
int A[Maxn],B[Maxn],N,Inv[Maxn];
int main()
{
    scanf("%d%lld",&N,&K),Inv[0]=Inv[1]=1;(K-=1)%=Mod;
    for(int i=0;i<N;i++)scanf("%d",&A[i]);
    while(len<=(N<<1))len<<=1,L++;B[0]=1;
    for(int i=0;i<len;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
    for(int i=2;i<N;i++)Inv[i]=(LL)(Mod-Mod/i)*Inv[Mod%i]%Mod;
    for(int i=1;i<N;i++)B[i]=(LL)B[i-1]*Inv[i]%Mod*(i+K)%Mod;
    NTT(A,1),NTT(B,1);
    for(int i=0;i<len;i++)A[i]=(LL)A[i]*B[i]%Mod;
    NTT(A,-1);
    for(int i=0;i<N;i++)printf("%d\n",A[i]);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*