题解 P4238 【【模板】多项式乘法逆】

· · 题解

题意：

求多项式 \ F(x)\ 的逆元。即求 \ G(x)\ 令 \ F(x)G(x) \equiv 1 \pmod{x^n}

(算法：分治FFT)

(下面一律都把同余符号去掉了）

考虑关系式

F(x)G(x)=1

我们有：

对于所有的 k\in [0,n]

\sum\limits_{i+j=k}a_ib_j=[k=0]

对 k=0 情况特殊处理后有

\sum\limits_{i+j=k}a_ib_j=0

考虑进行递推。

如果我们已经求出了前 x-1 项，那么：

b_xa_0=\sum\limits_{i+j=x\ \&\&\ j \not=x}-a_ib_j

即：

b_x=\sum\limits_{i+j=x\ \&\&\ j \not=x}-a_ib_j\cdot\dfrac{1}{a_0}

于是分治FFT即可。时间复杂度 Θ(n log^2n)。

（注意卡常）

#include<bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=400010;
const ll mod=998244353;
int i,j,k,n,m;
ll A[maxn],B[maxn],a[maxn],b[maxn];
ll M[25][2];
int R[maxn];
inline ll ksm(re ll sum,re int num){
    re ll ans=1;
    while(num){
        if(num&1)
            ans=ans*sum%mod;
        sum=sum*sum%mod;
        num>>=1;
    }return ans;
}
inline void NTT(int len,ll *a,bool op){
    for(re int i=0;i<=len;i++)
        if(i<R[i])swap(a[i],a[R[i]]);
    for(re int i=1,I=1;i<len;i<<=1,++I){
        ll Wn;if(op)Wn=0;else Wn=1;
//      if(op)Wn=3;else Wn=332748118;
//      Wn=ksm(Wn,(mod-1)/(i*2));
        Wn=M[I][Wn];
        for(re int j=0;j<len;j+=i<<1){
            ll w=1;
            for(re int k=0;k<i;k++,w=w*Wn%mod){
                int K=k+j;
                ll S1=a[K],S2=w*a[K+i]%mod;
                a[K]=(S1+S2)%mod;
                a[K+i]=(S1-S2+mod)%mod; 
            }
        }
    }
}
inline void solov(int len,int l,int r){
    NTT(len,A,1);NTT(len,B,1);
    for(re int i=0;i<=len;i++)A[i]=A[i]*B[i]%mod;
    NTT(len,A,0);
    for(re int i=(l+r)/2+1-l;i<=r-l;i++)A[i]=A[i]*ksm(len,mod-2)%mod;
}
ll T;
inline void work(int l,int r){
    if(l==r)return;
    int Mid=l+r>>1; 
    work(l,Mid);

    int x=Mid-l+1,y=n,len=1,L=0;
    while(len<=x<<1)len<<=1,++L;
    for(re int i=0;i<=len;i++)
        R[i]=(R[i>>1]>>1)+((i&1)<<L-1);

    B[0]=0;
    for(re int i=Mid-l+1;i<=len;i++)B[i]=0;
    for(re int i=min(len,n);i<=len;i++)A[i]=0;
    for(re int i=l;i<=Mid;i++)B[i-l]=b[i];
    for(re int i=0;i<min(len,n);i++)A[i]=a[i];
    solov(len,l,r);
    for(re int i=Mid+1;i<=r;i++)b[i]=(b[i]-A[i-l]*T%mod+mod)%mod;
    work(Mid+1,r);
    return;
}
int main(){
    cin>>n;
    for(i=1;i<=23;i++)
        M[i][0]=ksm(3,(mod-1)/(1<<i))%mod,M[i][1]=ksm(332748118,(mod-1)/(1<<i))%mod;
    for(i=1;i<=n;i++)a[i-1]=read();
    b[0]=ksm(a[0],mod-2);
    int L=1;
    T=ksm(a[0],mod-2);
    while(L<n)L<<=1;
    work(0,L-1);
    for(i=0;i<n;i++)printf("%lld ",b[i]);
    cout<<endl;
    return 0;
}