题解 P4512 【【模板】多项式除法】

· · 题解

要做这道题，先保证你会多项式求逆。

再发一下我参考的博客: Miskcoo's Space。

具体来说，设多项式 A 为 n 次多项式，考虑一种操作 R ，使得

A_R(x) = x^n A(\frac{1}{x})

稍微想象一下，可以发现 A_R[i] = A[n-i] ( [i] 表示多项式的第 i 次系数)。

这个操作可以 O(n) 完成。

然后开始化式子。

F(x) = Q(x) * G(x) + R(x) F(\frac{1}{x}) = Q(\frac{1}{x}) * G(\frac{1}{x}) + R(\frac{1}{x}) x^n F(\frac{1}{x}) = x^{n-m} Q(\frac{1}{x}) * x^m G(\frac{1}{x}) + x^{n-m+1} * x^{m-1} R(\frac{1}{x}) F_R(x) = Q_R(x) * G_R(x) + x^{n-m+1} * R_R(x) F_R(x) \equiv Q_R(x) * G_R(x) + x^{n-m+1} * R_R(x)\pmod {x^{n-m+1}} F_R(x) \equiv Q_R(x) * G_R(x)\pmod {x^{n-m+1}} Q_R(x) \equiv F_R(x) * G_R^{-1}(x)\pmod {x^{n-m+1}}

求一遍 G_R 的逆，然后就可以利用多项式乘法求出 Q 。然后

R(x) = F(x) - G(x) * Q(x)

直接计算即可。时间复杂度O(n\log n)。

代码:

#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Forward(i,a,b) for(i=(a);i>=(b);--i)
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
using namespace std;
template<typename T>inline void read(T &x){
    T s=0,f=1;char k=getchar();
    while(!isdigit(k)&&k^'-')k=getchar();
    if(!isdigit(k)){f=-1;k=getchar();}
    while(isdigit(k)){s=s*10+(k^48);k=getchar();}
    x=s*f;
}
void file(void){
    #ifndef ONLINE_JUDGE
    freopen("NTT.in","r",stdin);
    freopen("NTT.out","w",stdout);
    #endif
}
const int MAXN=1<<20;

typedef long long ll;

namespace polynomial
{
    static int mod=998244353,gen=3,g[21],rev[MAXN],Len;

    inline int ad(int a,int b){return (a+=b)>=mod?a-mod:a;}

    inline int power(int a,int b)
    {
        static int sum;
        for(sum=1;b;b>>=1,a=(ll)a*a%mod)if(b&1)
            sum=(ll)sum*a%mod;
        return sum;
    }

    inline void predone()
    {
        static int i,j;
        for(i=1,j=2;i<=19;++i,j<<=1)g[i]=power(gen,(mod-1)/j);
    }

    inline void calrev(int Len)
    {
        static int Logl;Logl=(int)floor(log(Len)/log(2)+0.3)-1;
        Rep(i,1,Len-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<Logl);
    }

    inline void NTT(int X[],int typ)
    {
        Rep(i,1,Len-1)if(i<rev[i])swap(X[i],X[rev[i]]);
        static int i,j,k,kk,w,t,wn,r;
        for(k=2,kk=1,r=1;k<=Len;k<<=1,kk<<=1,++r)
        {
            wn=g[r];
            for(i=0;i<Len;i+=k)for(j=0,w=1;j<kk;++j,w=(ll)w*wn%mod)
            {
                t=(ll)w*X[i+j+kk]%mod;
                X[i+j+kk]=ad(X[i+j],mod-t);
                X[i+j]=ad(X[i+j],t);
            }
        }
        if(typ==-1)
        {
            reverse(X+1,X+Len);
            static int invn;invn=power(Len,mod-2);
            Rep(i,0,Len-1)X[i]=(ll)X[i]*invn%mod;
        }
    }

    static int x[MAXN],y[MAXN];
    inline void mul(int a[],int b[])
    {
        memset(x,0,sizeof x);memset(y,0,sizeof y);
        Rep(i,0,(Len>>1)-1)x[i]=a[i],y[i]=b[i];
        NTT(x,1);NTT(y,1);
        Rep(i,0,Len-1)x[i]=(ll)x[i]*y[i]%mod;
        NTT(x,-1);
        Rep(i,0,Len-1)a[i]=x[i];
    }

    static int c[2][MAXN];

    inline void Inv(int a[],int n)
    {
        static int t;t=0;
        memset(c,0,sizeof c);
        c[0][0]=power(a[0],mod-2);
        Len=2;
        while(Len<=(n<<1))
        {
            Len<<=1;
            calrev(Len);t^=1;
            memset(c[t],0,sizeof c[t]);
            Rep(i,0,Len)c[t][i]=ad(c[t^1][i],c[t^1][i]);
            mul(c[t^1],c[t^1]);mul(c[t^1],a);
            Rep(i,0,Len)c[t][i]=ad(c[t][i],mod-c[t^1][i]);
        }
        Rep(i,0,Len-1)a[i]=c[t][i];
    }
}
using namespace polynomial;

int n,m,F[MAXN],G[MAXN],Q[MAXN],R[MAXN],Gr[MAXN];

int main(void){
    file();
    read(n);read(m);
    Rep(i,0,n)read(F[i]),Q[n-i]=F[i];
    Rep(i,0,m)read(G[i]),Gr[m-i]=G[i];
    Rep(i,n-m+2,m)Gr[i]=0;
    predone();
    Inv(Gr,n-m+1);
    mul(Q,Gr);
    reverse(Q,Q+n-m+1);
    Rep(i,n-m+1,n)Q[i]=0;
    Rep(i,0,n-m)printf("%d ",Q[i]);
    puts("");
    while(Len<=(n<<2))Len<<=1;
    calrev(Len);
    mul(Q,G);
    Rep(i,0,m-1)printf("%d ",ad(F[i],mod-Q[i]));
    puts("");
    return 0;
}