题解 P5809 【【模板】多项式复合逆】
mrsrz
2019-12-13 22:43:34
[可能更好的体验](https://mrsrz.github.io/2019/12/13/lg5809/)
对于满足 $G(F(x))=x$ 且 $F(x)$ 的常数项为 $0$，一次项有逆元的多项式 $F(x),G(x)$，有拉格朗日反演公式：
$$[x^n]G(x)=\frac 1{n}[x^{n-1}](\frac{x}{F(x)})^n$$
这个可以求单项系数。我们要求所有系数。
按多项式复合的做法来就可以了。
令 $L=\sqrt n$。
那么有：
$$G(x)=\sum_{i=1}^n \left(\frac{1}{i}[x^{i-1}](\frac{x}{F(x)})^i\right)x^i$$
$$=\sum_{i=0}^{L-1} \sum_{j=1}^L \left(\frac{1}{iL+j}[x^{iL+j-1}](\frac{x}{F(x)})^{iL+j}\right)x^{iL+j}$$
$$=\sum_{i=0}^{L-1}\sum_{j=1}^L \left(\frac{1}{iL+j}[x^{iL+j-1}](\frac{x}{F(x)})^{iL}(\frac{x}{F(x)})^j\right)x^{iL+j}$$
其中，$(\frac{x}{F(x)})^{iL}$ 和 $(\frac{x}{F(x)})^{j}$ 我们可以直接 FFT 预处理。时间复杂度 $O(n\sqrt n\log n)$。
观察 $[x^{iL+j-1}] (\frac{x}{F(x)})^{iL}(\frac{x}{F(x)})^j$，这部分相当于给出两个多项式，求它们的乘积的某一项系数。这个可以 $O(n)$ 暴力求得。常数很小。
总时间复杂度 $O(n^2+n\sqrt n\log n)$，可以通过。
## Code：
```cpp
#include<iostream>
#include<algorithm>
#include<cmath>
#define lg2(x)(31-__builtin_clz((x)))
using namespace std;
typedef long long LL;
const int N=32769,BS=140,md=998244353;
int n,a[N],b[N],rev[N],lim,LG,L;
int G[15][N];
int B[BS][N],B_[BS][N];
inline void upd(int&a){a+=a>>31&md;}
inline int pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
return ret;
}
void init(int n){
int l=-1;
for(lim=1;lim<n;lim<<=1)++l;LG=l+1;
for(int i=1;i<lim;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
}
void FFT(int*a,int f){
for(int i=1;i<lim;++i)
if(i<rev[i])swap(a[i],a[rev[i]]);
for(int i=0;i<LG;++i){
const int*g=G[i],c=1<<i;
for(int j=0;j<lim;j+=c<<1)
for(int k=0;k<c;++k){
const int x=a[j+k],y=g[k]*(LL)a[j+k+c]%md;
upd(a[j+k]+=y-md),upd(a[j+k+c]=x-y);
}
}
if(!f){
const int iv=pow(lim,md-2);
for(int i=0;i<lim;++i)a[i]=(LL)a[i]*iv%md;
reverse(a+1,a+lim);
}
}
void INV(int*a,int*B,int n){
if(n==1){
*B=pow(*a,md-2);
return;
}
INV(a,B,n+1>>1);
init(n<<1);
static int A[N];
for(int i=0;i<n;++i)A[i]=a[i];
for(int i=n;i<lim;++i)A[i]=0;
FFT(A,1),FFT(B,1);
for(int i=0;i<lim;++i)B[i]=B[i]*(2-B[i]*(LL)A[i]%md+md)%md;
FFT(B,0);
for(int i=n;i<lim;++i)B[i]=0;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>a[0];--n;
for(int i=0;i<15;++i){
int*g=G[i];
g[0]=1;
const int gi=pow(3,(md-1)/(1<<i+1));
for(int j=1;j<1<<i;++j)
g[j]=(LL)g[j-1]*gi%md;
}
for(int i=0;i<n;++i)cin>>a[i];
cout.put('0');
INV(a,b,n);
L=sqrt(n)+1;
init(n<<1);
**B=1;
FFT(*B,1);
for(int i=0;i<lim;++i)B_[0][i]=B[0][i];
for(int i=0;i<n;++i)B[1][i]=b[i];
FFT(B[1],1);
for(int i=2;i<=L;++i){
for(int j=0;j<lim;++j)
B[i][j]=(LL)B[i-1][j]*B[1][j]%md;
FFT(B[i],0);
for(int j=n;j<lim;++j)B[i][j]=0;
FFT(B[i],1);
}
for(int i=0;i<lim;++i)B_[0][i]=B[0][i],B_[1][i]=B[L][i];
for(int i=2;i<=L;++i){
for(int j=0;j<lim;++j)
B_[i][j]=(LL)B_[i-1][j]*B_[1][j]%md;
FFT(B_[i],0);
for(int j=n;j<lim;++j)B_[i][j]=0;
FFT(B_[i],1);
}
for(int i=0;i<=L;++i)FFT(B[i],0),FFT(B_[i],0);
for(int i=0;i<L;++i){
int*g_=B_[i];
for(int j=1;j<=L;++j){
const int x=i*L+j-1;
if(x>=n)return 0;
int*g=B[j];
int ans=0;
for(register int t=0;t<=x;++t)
ans=(ans+(LL)g_[t]*g[x-t])%md;
cout<<' '<<(LL)ans*pow(x+1,md-2)%md;
}
}
return 0;
}
```