VII.【模板】多项式除法
首先，为了方便，我们将\(n\)和\(m\)各自加一。
我们设\(F^T\)为\(F\)的翻转，更准确的定义为
\[F^T(x)=x^{n-1}F(\dfrac{1}{x}) \]现在我们考虑推式子。
由题意，
\[F(x)=(GQ)(x)+R(x) \]因为这个\(x\)是无实意的，故我们可以直接将其替换成\(\dfrac{1}{x}\)。
所以
\[F(\dfrac{1}{x})=(GQ)(\dfrac{1}{x})+R(\dfrac{1}{x}) \]我们两边同乘\(x^{n-1}\)，则有
\[x^{n-1}F(\dfrac{1}{x})=(x^{m-1}G\times x^{n-m}Q)(\dfrac{1}{x})+x^{n-1}R(\dfrac{1}{x}) \]套用我们之前\(F^T\)的定义，则有
\[F^T=G^TQ^T+x^{n-m+2}R^T \]我们前面的定义都是在\(\bmod\ x^n\)下有效的，但是我们为了求出\(Q\)，不需要那么多有效位，只需要保留\(x^{n-m+1}\)位即可，故我们模上一个\(x^{n-m+2}\)，就有
\[F^T\equiv G^TQ^T\pmod{x^{n-m+2}} \]现在我们想要\(Q\)，于是
\[Q^T\equiv F^T(G^T)^{-1}\pmod{x^{n-m+2}} \]然后再翻转一次，最终得到
\[Q\equiv\Big(F^T\big(G^T\big)^{-1}\Big)^T\pmod{x^{n-m+2}} \]注意到这里\(G_T\)的求逆只需要求前\(n-m+1\)位的逆即可——再往后的逆就可能出问题了。
我们求出\(Q\)后，就可以直接由\(F-GQ\equiv R\)算出\(R\)来。
则总复杂度\(O(n\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1<<20;
const int mod=998244353;
const int G=3;
int n,m,rev[N],f[N],g[N],u[N],v[N];
int ksm(int x,int y){
int rt=1;
for(;y;x=(1ll*x*x)%mod,y>>=1)if(y&1)rt=(1ll*rt*x)%mod;
return rt;
}
void NTT(int *a,int tp,int LG){
int lim=(1<<LG),invlim=ksm(lim,mod-2);
for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(LG-1));
for(int i=0;i<lim;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int md=1;md<lim;md<<=1){
int rt=ksm(G,(mod-1)/(md<<1));
if(tp==-1)rt=ksm(rt,mod-2);
for(int stp=md<<1,pos=0;pos<lim;pos+=stp){
int w=1;
for(int i=0;i<md;i++,w=(1ll*w*rt)%mod){
int x=a[pos+i],y=(1ll*w*a[pos+md+i])%mod;
a[pos+i]=(x+y)%mod;
a[pos+md+i]=(x-y+mod)%mod;
}
}
}
if(tp==-1)for(int i=0;i<lim;i++)a[i]=(1ll*a[i]*invlim)%mod;
}
int A[N],B[N],C[N],D[N];
void mul(int *a,int *b,int *c,int LG){
int lim=(1<<LG);
for(int i=0;i<lim;i++)A[i]=B[i]=0;
for(int i=0;i<(lim>>1);i++)A[i]=a[i],B[i]=b[i];
NTT(A,1,LG),NTT(B,1,LG);
for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,-1,LG);
for(int i=0;i<lim;i++)c[i]=A[i];
}
void inv(int *a,int *b,int LG){
b[0]=ksm(a[0],mod-2);
for(int k=1;k<=LG+1;k++){
mul(b,a,C,k);
for(int i=0;i<(1<<k);i++)C[i]=(mod-C[i])%mod;
(C[0]+=2)%=mod;
mul(C,b,b,k);
}
}
void rever(int *a,int *b,int lim){
for(int i=0;i<lim;i++)b[i]=a[i];
reverse(b,b+lim);
}
void div(int *a,int *b,int *q,int *r,int lima,int limb){
rever(b,D,limb);
for(int i=lima-limb+1;i<limb;i++)D[i]=0;
int all=0;
while((1<<all)<lima-limb+1)all++;
inv(D,q,all);
rever(a,D,lima);
all=0;
while((1<<all)<lima)all++;
for(int i=lima;i<(1<<all);i++)D[i]=0;
for(int i=lima-limb+1;i<(1<<all);i++)q[i]=0;
mul(D,q,q,all+1);
rever(q,q,lima-limb+1);
for(int i=lima-limb+1;i<(1<<all);i++)q[i]=0;
mul(q,b,D,all+1);
for(int i=0;i<limb-1;i++)r[i]=(f[i]-D[i]+mod)%mod;
}
int main(){
scanf("%d%d",&n,&m),n++,m++;
for(int i=0;i<n;i++)scanf("%d",&f[i]);
for(int i=0;i<m;i++)scanf("%d",&g[i]);
div(f,g,u,v,n,m);
for(int i=0;i<n-m+1;i++)printf("%d ",u[i]);puts("");
for(int i=0;i<m-1;i++)printf("%d ",v[i]);puts("");
return 0;
}