题目概述

给出多项式 $A(x),B(x)$ ，求 $C(x),D(x)$ 满足 $A(x)=C(x)B(x)+D(x)$ 。

解题报告

显然求出 $C(x)$ 或 $D(x)$ 就能求出另外一个，所以我们可以只考虑 $C(x)$ 或 $D(x)$ 怎么求。

• 求 $D(x)$ ：

  $$ B(x)\equiv0(mod\ B(x))\\ \sum_{i=0}^{m}b_ix^i\equiv0(mod\ B(x))\\ x^m=-\sum_{i=0}^{m-1}{b_i\over b_m}x^i(mod\ B(x)) $$

  所以可以 $O(n^2)$ 把所有 $A(x)$ 中 $\ge m$ 的项都代换掉，就得到了 $D(x)​$ 。

• 求 $C(x)$ ：

  考虑如何把 $D(x)$ 去掉，由于 $D(x)$ 的次数 $<m$ ，可以通过系数翻转然后 $mod\ x^{n-m+1}$ 的方法去掉 $D(x)$ 。

  因此，我们代入 $1\over x$ 然后乘上 $x^{n}$ 就可以得到翻转后的多项式（记为 $f^R(x)$ ）之间的关系：

  $$ A({1\over x})=C({1\over x})B({1\over x})+D({1\over x})\\ x^nA({1\over x})=x^{n-m}C({1\over x})x^mB({1\over x})+x^nD({1\over x})\\ A^R(x)=C^R(x)B^R(x)+x^{n-m+1}D^R(x)\\ A^R(x)\equiv C^R(x)B^R(x)(mod\ x^{n-m+1})\\ C^R(x)\equiv {A^R(x)\over B^R(x)}(mod\ x^{n-m+1}) $$

  这样只需要多项式求逆就行了，复杂度 $O(nlog_2n)​$ 。

因此采用第二种方法，那么 $D(x)=A(x)-B(x)C(x)$ 。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=262144,MOD=998244353;

int n,m,a[maxn+5],b[maxn+5],c[maxn+5],rev[maxn+5],pw[2][maxn+5],tem[maxn+5];

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
inline void Inv(int *a,int *b,int n){
    if (n==1) {b[0]=Pow(a[0],MOD-2);return;}Inv(a,b,n>>1);Pre(n<<1);
    for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=b[i+n]=0;NTT(tem,n<<1,1);NTT(b,n<<1,1);
    for (int i=0;i<(n<<1);i++) tem[i]=(LL)b[i]*(2+MOD-(LL)b[i]*tem[i]%MOD)%MOD;
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) b[i]=tem[i],b[i+n]=0;
}
inline void Div(int *a,int *b,int *c,int n,int m){
    static int A[maxn+5],B[maxn+5],C[maxn+5],t;for (t=1;t<n-m+1;t<<=1);
    for (int i=0;i<(t<<1);i++) A[i]=B[i]=0;for (int i=0;i<n-m+1;i++) A[i]=a[n-i],B[i]=m-i<0?0:b[m-i];
    Inv(B,C,t);Pre(t<<1);NTT(A,t<<1,1);NTT(C,t<<1,1);for (int i=0;i<(t<<1);i++) C[i]=(LL)C[i]*A[i]%MOD;
    NTT(C,t<<1,-1);for (int i=0;i<n-m+1;i++) c[i]=C[n-m-i];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=0;i<=n;i++) scanf("%d",&a[i]);for (int i=0;i<=m;i++) scanf("%d",&b[i]);
    Div(a,b,c,n,m);for (int i=0;i<=n-m;i++) i?putchar(' '):0,printf("%d",c[i]);puts("");
    int t;for (t=1;t<=n;t<<=1);Pre(t);NTT(b,t,1);NTT(c,t,1);for (int i=0;i<t;i++) c[i]=(LL)b[i]*c[i]%MOD;
    NTT(c,t,-1);for (int i=0;i<m;i++) i?putchar(' '):0,printf("%d",(a[i]+MOD-c[i])%MOD);puts("");return 0;
}