为什么不能直接用 \(F(x) \times G(x)^{-1}\) 做？
\(G(x)^{-1}\) 是模 \(x^{m+1}\) 意义下的，\(n - m > m\) 时得到的 \(Q(x)\) 就是错的。
记 \(F'(x)\) 为 \(F(x)\) 系数翻转后的多项式，即若 \(F(x) = \sum\limits_{i = 0}^nf_ix^i\)，则 \(F'(x) = \sum\limits_{i = 0}^nf_{n - i}x^i = \sum\limits_{i = 0}^nf_ix^{n - i}\)。
有
\[F'(x) = x^nF(\dfrac1x) \]\(G'(x), Q'(x), R'(x)\) 同理。
然后开始推式子，目标是把模 \(x^{m+1}\) 替换为模 \(x^{n-m+1}\)。
代入 \(\dfrac1x\)，得
\[F(\dfrac1x) = Q(\dfrac1x) * G(\dfrac1x) + R(\dfrac 1x) \]同乘 \(x^n\)，注意 \(Q(\dfrac1x) * G(\dfrac1x)\) 的次数正好是 \(n\)，\(R(\dfrac1x)\) 的次数不大于 \(m - 1\)，得
\[F'(x) = Q'(x) * G'(x) + x^{n-m+1}R'(x) \]其实到这就已经推完了，加个模意义就好
\[F'(x) \equiv Q'(x) * G'(x) \pmod{x^{n-m+1}} \]也即
\[Q'(x) = F'(x) * G'(x)^{-1} \pmod{x^{n-m+1}} \]求出 \(Q(x)\) 之后用 \(F(x) = Q(x) * G(x) + R(x) \Rightarrow R(x) = F(x) - Q(x) * G(x)\) 求出 \(R(x)\) 即可。
时间复杂度是 \(\mathcal O(n \log n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1 << 18, MOD = 998244353;
int n, m, f[N], g[N], r[N], q[N];
int bits, len, rev[N], Wn[2][18];
ll qp(ll base, int e = MOD - 2) {
ll res = 1;
while (e) {
if (e & 1) res = res * base % MOD;
base = base * base % MOD;
e >>= 1;
}
return res;
}
void NTT(int *A, bool I = 0) {
for (int i = 0; i < len; i++) if (i < rev[i]) swap(A[i], A[rev[i]]);
for (int i = 1; i < len; i <<= 1) {
ll wn = Wn[I][__builtin_ctz(i)];
for (int j = 0; j < len; j += (i << 1)) {
ll w = 1;
for (int k = j; k < j + i; k++) {
int t = w * A[k + i] % MOD;
A[k + i] = (A[k] - t + MOD) % MOD, A[k] = (A[k] + t) % MOD;
w = w * wn % MOD;
}
}
}
if (I) {
ll invlen = qp(len);
for (int i = 0; i < len; i++) A[i] = A[i] * invlen % MOD;
}
}
inline void init(int n) {
bits = -1, len = 1; while (len < n) len <<= 1, bits++;
for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bits);
}
int tmp[N];
void getinv(int n, int *const res, const int * f) {
if (n == 1) {res[0] = qp(f[0]); return;}
getinv((n + 1) >> 1, res, f);
init((n << 1) - 1); memcpy(tmp, f, n << 2), fill(tmp + n, tmp + len, 0); NTT(tmp), NTT(res);
for (int i = 0; i < len; i++) res[i] = res[i] * ((2 - (ll)tmp[i] * res[i]) % MOD + MOD) % MOD;
NTT(res, 1); fill(res + n, res + len, 0);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for (int i = 0; i <= n; i++) cin >> f[n - i];
for (int i = 0; i <= m; i++) cin >> g[m - i];
for (int i = 0; i < 18; i++) Wn[0][i] = qp(3, (MOD - 1) / (1 << (i + 1))), Wn[1][i] = qp(Wn[0][i], MOD - 2);
n++, m++; getinv(n - m + 1, q, g);
init((n << 1) - 1); memcpy(tmp, f, len << 2); NTT(q), NTT(tmp);
for (int i = 0; i < len; i++) q[i] = (ll)q[i] * tmp[i] % MOD;
NTT(q, 1); fill(q + n - m + 1, q + len, 0), reverse(q, q + n - m + 1);
for (int i = 0; i <= n - m; i++) cout << q[i] << ' '; cout << '\n';
reverse(f, f + n), reverse(g, g + m); init(n); NTT(g), NTT(q);
for (int i = 0; i < len; i++) r[i] = (ll)g[i] * q[i] % MOD;
NTT(r, 1); for (int i = 0; i < m; i++) r[i] = (f[i] - r[i] + MOD) % MOD;
for (int i = 0; i < m - 1; i++) cout << r[i] << ' ';
return 0;
}