luoguP4512 【模板】多项式除法 NTT+多项式求逆+多项式除法

求 $F(x)=Q(x)\times G(x)+R(x)$ 中的 $Q(x),R(x)$

$F(\frac{1}{x})=Q(\frac{1}{x})\times 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})$

带入 $\frac{1}{x}$，再乘以 $x^{n}$ 其实就是将系数翻转了

令 $F_{R}$ 表示将 $F$ 翻转

$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)($mod $x^{n-m+1})$

$F_{R}(x)\equiv Q_{R}(x)\times G_{R}(x)$ (mod $x^{n-m+1}$)

$Q_{R}(x)\equiv F_{R}(x)\times G_{R}^{-1}(x)$(mod $x^{n-m+1}$)

这里一定要注意，对 $G_{R}$ 求逆时模的是 $x^{n-m+1}$，所以要先将 $G_{R}$ 的长度定为 $n-m+1$

$R(x)=F(x)-G(x)\times Q(x)$

// luogu-judger-enable-o2

#include <cstdio>

#include <string>

#include <algorithm>

#include <cstring>

#include <vector>

#define setIO(s) freopen(s".in","r",stdin)

typedef long long ll;

const int maxn=2100005;

const ll mod=998244353;

using namespace std;

inline ll qpow(ll base,ll k) {

    ll tmp=1;

    for(;k;k>>=1,base=base*base%mod)if(k&1) tmp=tmp*base%mod;

    return tmp;

}

inline ll inv(ll a) { return qpow(a, mod-2); }

inline void NTT(ll *a,int len,int flag) {

    for(int i=0,k=0;i<len;++i) {

        if(i>k) swap(a[i],a[k]);

        for(int j=len>>1;(k^=j)<j;j>>=1);

    }

    for(int mid=1;mid<len;mid<<=1) {

        ll wn=qpow(3, (mod-1)/(mid<<1)),x,y;

        if(flag==-1) wn=qpow(wn,mod-2);

        for(int i=0;i<len;i+=(mid<<1)) {

            ll w=1;

            for(int j=0;j<mid;++j) {

                x=a[i+j],y=w*a[i+j+mid]%mod;

                a[i+j]=(x+y)%mod, a[i+j+mid]=(x-y+mod)%mod;

                w=w*wn%mod;

            }

        }

    }

    if(flag==-1) {

        int re=qpow(len,mod-2);

        for(int i=0;i<len;++i) a[i]=a[i]*re%mod;

    }

}

ll A[maxn],B[maxn];

struct poly {

    vector<ll>a;

    int len;

    poly(){}

    inline void clear() { len=0; a.clear(); }

    inline void rev() {reverse(a.begin(), a.end()); }

    inline void push(int x) { a.push_back(x),++len; }

    inline void resize(int x) { len=x; a.resize(x); }

    void getinv(poly &b,int n) {

        if(n==1) { b.clear(); b.push(inv(a[0]));  return; }

        getinv(b,n>>1);

        int t=n<<1,lim=min(len,n);

        for(int i=0;i<lim;++i) A[i]=a[i];

        for(int i=lim;i<t;++i) A[i]=0;

        for(int i=0;i<b.len;++i) B[i]=b.a[i];

        for(int i=b.len;i<t;++i) B[i]=0;

        NTT(A,t,1),NTT(B,t,1);

        for(int i=0;i<t;++i)  A[i]=(2-A[i]*B[i]%mod+mod)*B[i]%mod;

        NTT(A,t,-1);

        b.clear();

        for(int i=0;i<n;++i) b.push(A[i]);

    }

    poly Inv() {

        int n=1;

        while(n<=len)n<<=1;

        poly b;

        b.clear(), getinv(b,n);

        return b;

    }

    poly operator * (const poly &b) const {

        int n=1;

        while(n<=len+b.len) n<<=1;

        for(int i=0;i<len;++i) A[i]=a[i];

        for(int i=len;i<n;++i) A[i]=0;

        for(int i=0;i<b.len;++i) B[i]=b.a[i];

        for(int i=b.len;i<n;++i) B[i]=0;

        NTT(A,n,1), NTT(B,n,1);

        for(int i=0;i<n;++i) A[i]=A[i]*B[i]%mod;

        NTT(A,n,-1);

        poly c;

        c.clear();

        for(int i=0;i<len+b.len-1;++i) c.push(A[i]);

        return c;

    }

    poly operator + (const poly &b) const {

        poly c;

        c.clear();

        for(int i=0;i<len;++i) c.push(a[i]);

        for(int i=0;i<b.len;++i) {

            if(i<len) c.a[i]=(c.a[i]+b.a[i])%mod;

            else c.push(b.a[i]);

        }

        return c;

    }

    poly operator - (const poly &b) const {

        poly c;

        c.clear();

        for(int i=0;i<len;++i) c.push(a[i]);

        for(int i=0;i<b.len;++i) {

            if(i<len) c.a[i]=(c.a[i]-b.a[i]+mod)%mod;

            else c.push((mod-b.a[i])%mod);

        }

        return c;

    }

    friend poly operator / (poly f,poly g) {

        poly Q;

        int l=f.len-g.len+1;

        f.rev(), g.rev(), g.resize(l), f.resize(l);

        g=g.Inv(), Q=f*g, Q.resize(l),Q.rev();

        return Q;

    }

    friend poly operator % (poly f,poly g) {

        poly u=f-(f/g)*g;

        u.resize(g.len-1);

        return u;

    }

}po[4];

inline void inv() {

    int n,x;

    scanf("%d",&n), po[0].clear();

    for(int i=0;i<n;++i) scanf("%d",&x), po[0].push(x);

    po[1]=po[0].Inv();

    for(int i=0;i<po[1].len;++i) printf("%lld ",po[1].a[i]);

}

inline void mult() {

    int n,m,x;

    scanf("%d%d",&n,&m);

    for(int i=0;i<=n;++i) scanf("%d",&x), po[0].push(x);

    for(int i=0;i<=m;++i) scanf("%d",&x), po[1].push(x);

    po[1]=po[0]*po[1];

    for(int i=0;i<po[1].len;++i) printf("%lld ",po[1].a[i]);

}

inline void divide() {

    int n,m,x;

    scanf("%d%d",&n,&m);

    for(int i=0;i<=n;++i) scanf("%d",&x), po[0].push(x);

    for(int i=0;i<=m;++i) scanf("%d",&x), po[1].push(x);

    po[2]=po[0]/po[1];

    for(int i=0;i<po[2].len;++i) printf("%lld ",po[2].a[i]);

    printf("\n");

    po[2]=po[0]%po[1];

    for(int i=0;i<po[2].len;++i) printf("%lld ",po[2].a[i]);

}

int main() {

    // setIO("input");

    divide();

    return 0;

}

巴特西

luoguP4512 【模板】多项式除法 NTT+多项式求逆+多项式除法

最新文章

热门文章