给定一个$n$次多项式$F(x)$和一个$m$次多项式$G(x)$，满足$m<n$，要求求出$n-m$次多项式$Q(x)$和次数小于$m$的多项式$R(x)$，满足$$F(x)=Q(x)*G(x)+R(x)\tag{1}$$

推导

首先我们定义一种运算，对于$n$次多项式$A(x)$$$A^R(x)=x^n\cdot A(\frac{1}{x})$$用人话说，这种运算就是翻转$A(x)$的系数，举个例子，$$A(x)=a_0+a_1\cdot x+a_2\cdot x^2+a_3\cdot x^3$$ $$A^R(x)=x^3\cdot A(\frac{1}{x})\\=x^3\cdot (a_0+a_1\cdot \frac{1}{x}+a_2\cdot \frac{1}{x^2}+a_3\cdot \frac{1}{x^3})\\=a_3+a_2\cdot x+a_1\cdot x^2+a_0\cdot x^3$$将$x=\frac{1}{x}$代入式$(1)$，得$$F(\frac{1}{x})=Q(\frac{1}{x})*G(\frac{1}{x})+R(\frac{1}{x})\tag{2}$$将式$(2)$两边同时乘上$x^n$，得$$x^n\cdot F(\frac{1}{x})=x^{n-m}\cdot Q(x) * x^m\cdot G(x)+x^{n-m+1}\cdot x^{m-1}\cdot R(\frac{1}{x})\tag{3}$$将式$(3)$转化一下形式得$$F^R(x)=Q^R(x)G^R(x)+x^{n-m+1}\cdot R^R(x)\tag{4}$$如果将$(4)$放到$\bmod {x^{n-m+1}}$意义下，可以发现$x^{n-m+1}\cdot R^R(x)$可以直接消去，而$Q^R(x)$不会受任何影响，那么可以得到$$Q^R(x)\equiv F^R(x)G^R(x)^{-1}\pmod{x^{n-m+1}}$$这样求出$Q(x)$后，带回原式即可得到$R(x)$

实现

#include <iostream>
#include <cstdio>
#include <algorithm>

const int MOD=998244353, g=3, ig=332748118, MX=262150;
int n, m, F[MX], G[MX], inv[MX], Q[MX], tmp[MX], rev[MX];

int ksm(int _, int __){
    int ans=1;
    while(__){
        if(__&1) ans=1LL*_*ans%MOD;
        _=1LL*_*_%MOD;
        __>>=1;
    }
    return ans;
}

void get_rev(int l){
    for(int i=0; i<l; i++)
        rev[i]=(rev[i>>1]>>1)|((i&1) ? l>>1 : 0);
}

void NTT(int *P, int l, int opt){
    for(int i=0; i<l; i++) if(rev[i]>i)
        std::swap(P[i], P[rev[i]]);
    for(int i=1; i<l; i<<=1){
        int W=opt>0 ? g : ig;
        W=ksm(W, (MOD-1)/(i<<1));
        for(int j=0, p=i<<1; j<l; j+=p)
            for(int k=0, w=1; k<i; k++, w=1LL*w*W%MOD){
                int X=P[j+k], Y=1LL*P[i+j+k]*w%MOD;
                P[j+k]=(X+Y)%MOD, P[i+j+k]=((X-Y)%MOD+MOD)%MOD;
            }
    }
    if(opt>0) return;
    int inv=ksm(l, MOD-2);
    for(int i=0; i<l; i++) P[i]=1LL*P[i]*inv%MOD;
}

void get_inv(int *a, int *b, int len){
    if(len==1) {b[0]=ksm(a[0], MOD-2); return;}
    get_inv(a, b, (len+1)/2);
    int l=1; while(l<2*len) l<<=1;
    for(int i=0; i<len; i++) tmp[i]=a[i];
    for(int i=len; i<l; i++) tmp[i]=0;
    get_rev(l);
    NTT(tmp, l, 1); NTT(b, l, 1);
    for(int i=0; i<l; i++) b[i]=((2LL-1LL*tmp[i]*b[i]%MOD)%MOD+MOD)%MOD*b[i]%MOD;
    NTT(b, l, -1);
    for(int i=len; i<l; i++) b[i]=0;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=0; i<=n; i++) scanf("%d", &F[i]);
    for(int i=0; i<=m; i++) scanf("%d", &G[i]);
    std::reverse(G, G+m+1);
    std::reverse(F, F+n+1);
    get_inv(G, inv, n-m+1);
    for(int i=0; i<=n-m; i++) Q[i]=F[i];
    std::reverse(G, G+m+1);
    std::reverse(F, F+n+1);
    int l=1; while(l<=2*(n-m)) l<<=1;
    get_rev(l);
    NTT(Q, l, 1); NTT(inv, l, 1);
    for(int i=0; i<l; i++) Q[i]=1LL*Q[i]*inv[i]%MOD;
    NTT(Q, l, -1); std::reverse(Q, Q+n-m+1);
    for(int i=n-m+1; i<l; i++) Q[i]=0;
    for(int i=0; i<=n-m; i++) printf("%d ", Q[i]); putchar('\n');
    l=1; while(l<=n) l<<=1;
    get_rev(l);
    NTT(Q, l, 1); NTT(G, l, 1);
    for(int i=0; i<l; i++) G[i]=1LL*G[i]*Q[i]%MOD;
    NTT(G, l, -1);
    for(int i=0; i<m; i++) printf("%d ", ((F[i]-G[i])%MOD+MOD)%MOD);
    return 0;
}

说实话哪怕这辈子都考不到这种东西，当NTT练手题也不错

参考资料

多项式除法及求模 – Miskcoo