【洛谷P5809】【模板】多项式复合逆 | Mrsrz's blog

多项式复合逆

题目大意：

令 $n-1$ 次多项式 $F(x)=\sum\limits _{i=0}^{n-1} a_ix^i$。

给定 $n$ 和 $F(x)$ 的各项系数，要求一个 $n-1$ 次多项式 $G(x)$ 满足：

$$G(F(x))\equiv x\pmod{x^n}$$

求 $G(x)$ 的各项系数对 $998,244,353$ 取模的结果。

保证 $a_0=0$，$a_1\neq 0$。

题解：

对于满足 $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：

#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;
}