题目大意：给定一个$n$次多项式$F(x)$和一个$m$次多项式$G(x)$，请求出多项式$Q(x),R(x)$，满足：
1. $Q(x)$次数为$n-m$，$R(x)$次数小于$m$
2. $F(x)=Q(x)\times G(x)+R(x)$
题解：多项式除法。
$$
F(x)\equiv Q(x)G(x)+R(x)(\bmod{x^n})\\
F(\dfrac 1 x)\equiv Q(\dfrac 1 x)G(\dfrac 1 x)+R(\dfrac 1 x)(\bmod{x^n})\\
x^nF(\dfrac 1 x)\equiv x^{n-m}Q(\dfrac 1 x)\cdot x^mG(\dfrac 1 x)+x^nR(\dfrac 1 x)(\bmod{x^n})\\
F_R(x)\equiv Q_R(x)G_R(x)+x^{n-m+1}R_R(x)(\bmod{x^n})\\
F_R(x)\equiv Q_R(x)G_R(x)(\bmod{x^{n-m+1}})\\
Q_R(x)\equiv F_R(x)G_R^{-1}(x)(\bmod{x^{n-m+1}})\\
R_R(x)=F_R(x)-G_R(x)Q_R(x)
$$
卡点：无
C++ Code：
#include <algorithm>
#include <cstdio>
#include <cctype>
namespace __IO {
namespace R {
int x, ch;
inline int read() {
ch = getchar();
while (isspace(ch)) ch = getchar();
for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
return x;
}
}
}
using __IO::R::read; const int mod = 998244353, G = 3; namespace Math {
int x, y;
inline int pw(int base, int p) {
int res = 1;
for (; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
return res;
}
void exgcd(int a, int b, int &x, int &y) {
if (!b) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= a / b * x;
}
inline int inv(int a) {
exgcd(a, mod, x, y);
return x + (x >> 31 & mod);
}
} #define N 262144
inline void reduce(int &a) {a += a >> 31 & mod;}
inline void clear(int *l, const int *r) {
if (l >= r) return ;
while (l != r) *l++ = 0;
} namespace Poly {
int lim, ilim, rev[N], s;
int Wn[N + 1];
inline void init(int n) {
s = -1, lim = 1; while (lim < n) lim <<= 1, s++; ilim = Math::inv(lim);
for (register int i = 0; i < lim; i++) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
const int t = Math::pw(G, (mod - 1) / lim);
*Wn = 1; for (register int i = 1; i <= lim; i++) Wn[i] = static_cast<long long> (Wn[i - 1]) * t % mod;
}
void NTT(int *A, int op = 1) {
for (register int i = 0; i < lim; i++) if (i < rev[i]) std::iter_swap(A + i, A + rev[i]);
for (register int mid = 1; mid < lim; mid <<= 1) {
const int t = lim / mid >> 1;
for (register int i = 0; i < lim; i += mid << 1) {
for (register int j = 0; j < mid; j++) {
const int W = op ? Wn[t * j] : Wn[lim - t * j];
const int X = A[i + j], Y = static_cast<long long> (A[i + j + mid]) * W % mod;
reduce(A[i + j] += Y - mod), reduce(A[i + j + mid] = X - Y);
}
}
}
if (!op) for (register int i = 0; i < lim; i++) A[i] = static_cast<long long> (A[i]) * ilim % mod;
}
int C[N];
void INV(int *A, int *B, int n) {
if (n == 1) {
*B = Math::inv(*A);
return ;
}
INV(A, B, n + 1 >> 1);
std::copy(A, A + n, C);
init(n << 1), clear(C + n, C + lim);
NTT(B), NTT(C);
for (int i = 0; i < lim; i++) B[i] = (2 + mod - static_cast<long long> (C[i]) * B[i] % mod) * B[i] % mod;
NTT(B, 0);
clear(B + n, B + lim);
}
int D[N], E[N], F[N];
void DIV(int *A, int *B, int *Q, int n, int m) {
std::reverse_copy(A, A + n, D), std::reverse_copy(B, B + m, E);
clear(D + n - m + 1, D + n);
clear(E + n - m + 1, E + m);
INV(E, F, n - m + 1), init(n - m + 1 << 1);
NTT(D), NTT(F);
for (int i = 0; i < lim; i++) Q[i] = static_cast<long long> (D[i]) * F[i] % mod;
NTT(Q, 0);
std::reverse(Q, Q + n - m + 1);
for (int i = n - m + 1; i < lim; i++) Q[i] = 0;
}
int G[N];
void DIV_MOD(int *A, int *B, int *Q, int *R, int n, int m) {
DIV(A, B, Q, n, m);
std::copy(Q, Q + n - m + 1, G);
init(n << 1);
NTT(A), NTT(B), NTT(G);
for (int i = 0; i < lim; i++) R[i] = (A[i] + mod - static_cast<long long> (B[i]) * G[i] % mod) % mod;
NTT(R, 0);
}
} int A[N], B[N], Q[N], R[N];
int n, m;
int main() {
n = read() + 1, m = read() + 1;
for (int i = 0; i < n; i++) A[i] = read();
for (int i = 0; i < m; i++) B[i] = read();
Poly::DIV_MOD(A, B, Q, R, n, m);
for (int i = 0; i < n - m + 1; i++) printf("%d ", Q[i]); puts("");
for (int i = 0; i < m - 1; i++) printf("%d ", R[i]); puts("");
return 0;
}