题目
https://www.luogu.com.cn/problem/P4726
思路
（略）
是个板题，但是包含了很多多项式的基础板子，适合用来练手。
据说递归版的好写（好抄），但是我猜测和fft类似，迭代版的应该常数会小一点。
而且迭代一直倍增，多项式长度一直是2的次幂，感觉也更好处理。
另外就是多项式细节很多，记得清空啥的qwq。
代码
点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define mod 998244353
#define maxn 400010
#define ll long long
using namespace std;
int pos[maxn];
ll A[maxn],B[maxn],C[maxn],w[maxn],D[maxn],E[maxn];
ll qpow(ll x,int p){
ll base,ans;
for(base=x,ans=1;p;p>>=1,base=base*base%mod){
if(p&1) ans=ans*base%mod;
}
return ans;
}
ll inv(ll x){
return qpow(x,mod-2);
}
void NTT(ll *L,int N,int type,int lg){
int i,j,t,d;
for(i=0;i<N;++i) pos[i]=pos[i>>1]>>1|((1&i)<<lg-1);
w[0]=1,w[1]=type>0?qpow(3,(mod-1)>>lg):inv(qpow(3,(mod-1)>>lg));
for(i=2;i<N;++i) w[i]=w[i-1]*w[1]%mod;
for(i=0;i<N;++i){
if(pos[i]>i) swap(L[i],L[pos[i]]);
}
for(t=1,d=N>>1;t<N;d>>=1,t<<=1){
for(i=0;i<N;i+=t<<1){
for(j=0;j<t;++j){
ll tmp=w[j*d]*L[i+j+t]%mod;
L[i+j+t]=(L[i+j]+mod-tmp)%mod;
L[i+j]=(L[i+j]+tmp)%mod;
}
}
}
}
void poly_diff(ll *L,int N){
for(int i=0;i<N;++i) L[i]=L[i+1]*(i+1)%mod;
L[N-1]=0;
}
void poly_int(ll *L,int N){
for(int i=N;i>0;--i) L[i]=L[i-1]*inv(i)%mod;
L[0]=0;
}
void poly_inv(ll *L1,ll *L2,int N,int lg){
int i,len,j;
L2[0]=1;
for(i=0,len=1;i<=lg;++i,len<<=1){
for(j=0;j<(len<<1);++j) C[j]=j<len?L1[j]:0;
NTT(C,len<<1,1,i+1);NTT(L2,len<<1,1,i+1);
for(j=0;j<(len<<1);++j) L2[j]=(mod+2-L2[j]*C[j]%mod)%mod*L2[j]%mod;
NTT(L2,len<<1,-1,i+1);
for(j=0;j<len;++j) L2[j]=L2[j]*inv(len<<1)%mod;
for(j=len;j<(len<<1);++j) L2[j]=0;
}
for(i=N;i<(1<<lg);++i) L2[i]=0;
}
void poly_ln(ll *L1,ll *L2,int N,int lg){
int i;
for(i=0;i<(N<<1);++i) D[i]=i<N?L1[i]:0;
poly_diff(D,N);
for(i=0;i<(N<<1);++i) L2[i]=0;
poly_inv(L1,L2,N,lg);
NTT(D,N<<1,1,lg+1);NTT(L2,N<<1,1,lg+1);
for(i=0;i<(N<<1);++i) L2[i]=L2[i]*D[i]%mod;
NTT(L2,N<<1,-1,lg+1);
for(i=0;i<(N<<1);++i) L2[i]=L2[i]*inv(N<<1)%mod;
poly_int(L2,N);
}
void poly_exp(ll *L1,ll *L2,int N,int lg){
int i,j,len;
L2[0]=1;
for(i=0,len=1;i<=lg;++i,len<<=1){
poly_ln(L2,E,len,i);
for(j=len;j<(len<<1);++j) E[j]=0;
for(j=0;j<(len<<1);++j) C[j]=j<len?L1[j]:0;
NTT(L2,len<<1,1,i+1);NTT(E,len<<1,1,i+1);NTT(C,len<<1,1,i+1);
for(j=0;j<(len<<1);++j) L2[j]=(1-E[j]+C[j]+mod)%mod*L2[j]%mod;
NTT(L2,len<<1,-1,i+1);
for(j=0;j<(len<<1);++j) L2[j]=L2[j]*inv(len<<1)%mod;
}
}
int main(){
int i,n,m,u;
scanf("%d",&n);
for(m=1,u=0;m<n;m<<=1,++u);
for(i=0;i<n;++i) scanf("%lld",&A[i]);
poly_exp(A,B,m,u);
for(i=0;i<n;++i) printf("%lld ",B[i]);
// system("pause");
return 0;
}