给定一个$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练手题也不错