多项式除法

扫码查看

P4512 【模板】多项式除法

给定一个\(n\)次多项式\(F(x)\)和一个\(m\)次多项式\(G(x)\),请求出多项式\(R(x),R(x)\),满足:

\(Q(x)\)次数为\(n-m\)\(R(x)\)次数小于\(m\)

\(F(x)=Q(x)*G(x)+R(x)\)

前置芝士:多项式乘法逆

假设对于任意多项式\(A(x)\),有\(A_R(x)=x^nA(\frac{1}{x})\)

展开一下可以发现,&A_R(x)&就是将\(A(x)\)各项系数翻转

大力化式子

\[F(x)=Q(x)*G(x)+R(x)\]

代入\(x=\frac{1}{x}\)

\[F(\frac{1}{x})=Q(\frac{1}{x})*G(\frac{1}{x})+R(\frac{1}{x})\]

两边日上一个\(x^n\),右边稍微分布一下

\[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)\]

先考虑求\(Q\),由于\(Q\)最高次是\(n-m\),我们模上一个\(x^{n-m+1}\)

\[F_R(x)\equiv Q_R(x)*G_R(x)+x^{n-m+1}*R_R(x) (mod\ x^{n-m+1})\]

发现右边有个\(x^{n-m+1}*R_R(\frac{1}{x})\),可以被模掉

\[F_R(x)\equiv Q_R(x)*G_R(x) (mod\ x^{n-m+1})\]

\[Q_R(x)\equiv F_R(x)*G_R^{-1}(x) (mod\ x^{n-m+1})\]

我们求一个\(G_R\)的乘法逆,就可以求出\(Q_R\)

最初的式子

\[F(x)=Q(x)*G(x)+R(x)\]

变形

\[R(x)=F(x)-Q(x)*G(x)\]

完成,注意多项式加减法直接在系数上进行……

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int N=5e5+10,p=998244353,G=3,gi=332748118;
    int n,m;
    int f[N],g[N],grn[N],c[N];
    int gr[N],fr[N],q[N];
    int pos[N];
    inline int fast(int x,int k)
    {
        int ret=1;
        while(k)
        {
            if(k&1) ret=ret*x%p;
            x=x*x%p;
            k>>=1;
        }
        return ret;
    }
    inline void ntt(int limit,int *a,int inv)
    {
        for(int i=0;i<limit;++i)
            if(i<pos[i]) swap(a[i],a[pos[i]]);
        for(int mid=1;mid<limit;mid<<=1)
        {
            int Wn=fast(inv?G:gi,(p-1)/(mid<<1));
            for(int r=mid<<1,j=0;j<limit;j+=r)
            {
                int w=1;
                for(int k=0;k<mid;++k,w=w*Wn%p)
                {
                    int x=a[j+k],y=w*a[j+k+mid]%p;
                    a[j+k]=x+y;
                    if(a[j+k]>=p) a[j+k]-=p;
                    a[j+k+mid]=x-y;
                    if(a[j+k+mid]<0) a[j+k+mid]+=p;
                }
            }
        }
        if(inv) return;
        inv=fast(limit,p-2);
        for(int i=0;i<limit;++i) a[i]=a[i]*inv%p;
    }
    inline void poly_inv(int pw,int *a,int *b)
    {
        if(pw==1) {b[0]=fast(a[0],p-2);return;}
        poly_inv((pw+1)>>1,a,b);
        int len=0,limit=1;
        while(limit<(pw<<1)) limit<<=1,++len;
        for(int i=0;i<limit;++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(len-1));
        for(int i=0;i<pw;++i) c[i]=a[i];
        for(int i=pw;i<limit;++i) c[i]=0;
        ntt(limit,c,1);ntt(limit,b,1);
        for(int i=0;i<limit;++i) b[i]=((2-c[i]*b[i]%p)+p)%p*b[i]%p;
        ntt(limit,b,0);
        for(int i=pw;i<limit;++i) b[i]=0;
    }
    inline void main()
    {
        n=read(),m=read();
        for(int i=0;i<=n;++i) f[i]=fr[n-i]=read();
        for(int i=0;i<=m;++i) g[i]=gr[m-i]=read();
        for(int i=n-m+2;i<=m;++i) gr[i]=0;
        poly_inv(n-m+1,gr,grn);
        int limit=1,len=0;
        while(limit<=n+n)   limit<<=1,++len;
        for(int i=0;i<limit;++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(len-1));
        ntt(limit,fr,1);ntt(limit,grn,1);
        for(int i=0;i<limit;++i) fr[i]=fr[i]*grn[i]%p;
        ntt(limit,fr,0);
        for(int i=0;i<=n-m;++i) q[i]=fr[i];
        reverse(q,q+n-m+1);
        for(int i=0;i<=n-m;++i) printf("%lld ",q[i]);
        putchar('\n');
        ntt(limit,q,1);ntt(limit,g,1);
        for(int i=0;i<limit;++i) q[i]=q[i]*g[i]%p;
        ntt(limit,q,0);
        for(int i=0;i<m;++i) printf("%lld ",(f[i]-q[i]+p)%p);
    }
}
signed main()
{
    red::main();
    return 0;
}
12-16 11:15
查看更多