如果不会伯努利数可以先看看本人的学习笔记
然后给出来了式子就直接往上套,因为要求关于x^i的系数所以我们只能做0~x-1的自然数幂和,先把x^k单独提出来,最后再给每一项加上a_k即可.
显然最后一部分是一个翻转套路,然后求一遍FFT即可.
#include<bits/stdc++.h> #define vi vector<int> using namespace std; int mod=998244353; int ksm(int x,int t){ int tot=1; while(t){ if(t&1) tot=1ll*tot*x%mod; x=1ll*x*x%mod; t/=2; } return tot; } const int N=600010;//2<<18 int poor[2400010]; int fac[N],finv[N],n,limit,where[N]; int*w[2][19],*now=poor; inline char nc() { static const int BS = 1 << 22; static unsigned char buf[BS],*st,*ed; if(st == ed) ed = buf + fread(st=buf,1,BS,stdin); return st == ed ? EOF : *st++; } #define nc getchar inline int read() { char ch; int res = 0; while (!isdigit(ch = nc())); while (ch >= '0' and ch <= '9') { res = (res << 1) + (res << 3) + (ch - '0'); ch = nc(); } return res; } inline void write(int x){ if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } void pre(){ fac[0]=1;for(int i=1;i<=600000;i++) fac[i]=1ll*fac[i-1]*i%mod; finv[600000]=ksm(fac[600000],mod-2); for(int i=599999;i>=0;i--) finv[i]=1ll*finv[i+1]*(i+1)%mod; for(int u=0,l=2;u<19;u++,l<<=1){ w[1][u]=now;now+=l+1; w[0][u]=now;now+=l+1; w[1][u][0]=1;w[1][u][1]=ksm(3,(mod-1)/l); for(int i=2;i<=l;i++) w[1][u][i]=1ll*w[1][u][i-1]*w[1][u][1]%mod; for(int i=0;i<=l;i++) w[0][u][i]=w[1][u][l-i]; } } void prepare(int n){ int l=0;limit=1; while(limit<=n) limit<<=1,l++; for(int i=0;i<limit;i++) where[i]=((where[i>>1]>>1) | ((i&1)<<(l-1))); } void DFT(int*now,int op){ int**w0=w[op]; for(int i=0;i<limit;i++) if(i<where[i]) swap(now[i],now[where[i]]); for(int l=1,c=0;l<limit;l*=2,++c){ for(int i=0;i<limit;i+=l+l){ register int*s=now+i,*t=now+i+l,*w=w0[c]; for(register int u=0;u<l;++u){ register int b=1ll*t[u]*w[u]%mod; t[u]=(s[u]<b)?(s[u]-b+mod):(s[u]-b); s[u]=(s[u]+b>=mod)?(s[u]+b-mod):(s[u]+b); } } } if(!op){ int tmp=ksm(limit,mod-2); for(int i=0;i<limit;i++) now[i]=1ll*now[i]*tmp%mod; } } void MUL(int*f,int*g,int n,int m){ static int b[N]; int tot=n+m-2; prepare(tot); for(int i=n;i<limit;i++) f[i]=0; for(int i=m;i<limit;i++) g[i]=0; for(int i=0;i<limit;i++) b[i]=g[i]; DFT(f,1);DFT(b,1); for(int i=0;i<limit;i++) f[i]=1ll*f[i]*b[i]%mod; DFT(f,0); } void INV(int*f,int n){ if(n==1) {f[0]=ksm(f[0],mod-2);return ;} int f0[n<<2]; for(int i=0;i<(n+1)/2;i++) f0[i]=f[i]; INV(f0,(n+1)/2);prepare(n+(n+1)/2*2-3); for(int i=n;i<limit;i++) f[i]=0; for(int i=(n+1)/2;i<limit;i++) f0[i]=0; DFT(f,1);DFT(f0,1); for(int i=0;i<limit;i++) f[i]=1ll*f0[i]*(mod+2-1ll*f[i]*f0[i]%mod)%mod; DFT(f,0); } int A[N],B[N],f[N],g[N]; int main(){ //freopen("P3711_2.in","r",stdin); //freopen("ans.out","w",stdout); n=read();pre(); for(int i=0;i<=n;i++) A[i]=B[i]=read(),A[i]=1ll*A[i]*fac[i]%mod; for(int i=0;i<=n;i++) f[i]=finv[i+1]; INV(f,n+1); for(int i=0;i<=n/2;i++) swap(f[i],f[n-i]); MUL(f,A,n+1,n+1);write(B[0]); for(int i=1;i<=n+1;i++){ putchar(' ');write((1ll*f[n+i-1]*finv[i]+B[i])%mod); } }
