①、多项式求逆求解:O(n logn):
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=4e5+100;
const int p=998244353;
const int g=3;
int fi[maxn];
int gg[maxn],ff[maxn],c[maxn];
int mypow(int a,int b)
{
if(b<0) return mypow(mypow(a,p-2),-b);
int ans=1;
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans%p;
}
void ntt(int *x,int len,int f)
{
for(int i=0;i<len;i++)
if(i<fi[i]) swap(x[i],x[fi[i]]);
for(int i=1;i<len;i<<=1)
{
int r=i<<1;
int wn=mypow(g,f*(p-1)/r);
for(int j=0;j<len;j+=r)
{
int w=1;
for(int k=0;k<i;k++)
{
int xx=x[j+k],yy=w*x[j+i+k]%p;
x[j+k]=((xx+yy)%p+p)%p;
x[j+i+k]=((xx-yy)%p+p)%p;
w=w*wn%p;
}
}
}
if(f==-1)
{
int invn=mypow(len,p-2);
for(int i=0;i<len;i++)
x[i]=x[i]*invn%p;
}
}
void dfs(int n,int *a,int *b)
{
if(n==1)
{
b[0]=mypow(a[0],p-2);
return ;
}
dfs((n+1)>>1,a,b);
int len=1,cnt=0;
while(len<=(n<<1)) len<<=1,cnt++;
for(int i=0;i<len;i++)
{
fi[i]=((fi[i>>1]>>1)|((i&1)<<(cnt-1)));
c[i]=(i<n?a[i]:0);
}
ntt(c,len,1);
ntt(b,len,1);
for(int i=0;i<len;i++)
b[i]=(2-c[i]*b[i]%p+p)%p*b[i]%p;
ntt(b,len,-1);
for(int i=n;i<len;i++)
b[i]=0;
}
signed main(void)
{
int n;//多项式项数
scanf("%lld",&n);
for(int i=1;i<n;i++)
scanf("%lld",&gg[i]),gg[i]=-gg[i]+p;
gg[0]=1;
dfs(n,gg,ff);
for(int i=0;i<n;i++)
printf("%lld ",ff[i]);
putchar('\n');
return 0;
}
②、分治 f f t 求解,O(n log2n):
可以预处理原根的阶乘以加快速度。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=4e5+100;
const int p=998244353;
const int g=3;
int fi[maxn];
int gg[maxn],ff[maxn],a[maxn],b[maxn];
int mypow(int a,int b)
{
if(b<0) return mypow(mypow(a,p-2),-b);
int ans=1;
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans%p;
}
void ntt(int *x,int len,int f)
{
for(int i=0;i<len;i++)
if(i<fi[i]) swap(x[i],x[fi[i]]);
for(int i=1;i<len;i<<=1)
{
int r=i<<1;
int wn=mypow(g,f*(p-1)/r);
for(int j=0;j<len;j+=r)
{
int w=1;
for(int k=0;k<i;k++)
{
int xx=x[j+k],yy=w*x[j+i+k]%p;
x[j+k]=((xx+yy)%p+p)%p;
x[j+i+k]=((xx-yy)%p+p)%p;
w=w*wn%p;
}
}
}
if(f==-1)
{
int invn=mypow(len,p-2);
for(int i=0;i<len;i++)
x[i]=x[i]*invn%p;
}
}
void getntt(int *a,int *b,int len)
{
ntt(a,len,1);
ntt(b,len,1);
for(int i=0;i<len;i++)
a[i]=a[i]*b[i]%p;
ntt(a,len,-1);
}
void dfs(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>1;
dfs(l,mid);
int n=mid-l,m=r-l-1;
int len=1,cnt=0;
while(len<=(n+m)) len<<=1,cnt++;
for(int i=0;i<len;i++)
{
fi[i]=((fi[i>>1]>>1)|((i&1)<<(cnt-1)));
a[i]=(i<=n?ff[i+l]:0);
b[i]=(i<=m?gg[i+1]:0);
}
getntt(a,b,len);
for(int i=mid+1;i<=r;i++) ff[i]=(ff[i]+a[i-l-1])%p;
dfs(mid+1,r);
}
signed main(void)
{
int n;//多项式项数
scanf("%lld",&n);
for(int i=1;i<n;i++)
scanf("%lld",&gg[i]);
ff[0]=1;
dfs(0,n-1);
for(int i=0;i<n;i++)
printf("%lld ",ff[i]);
putchar('\n');
return 0;
}