洛谷传送门

题目描述

给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x)$ ，请求出多项式 $Q(x)$, $R(x)$，满足以下条件：

• $Q(x)$ 次数为 $n-m$，$R(x)$ 次数小于 $m$
• $F(x) = Q(x) * G(x) + R(x)$

所有的运算在模 $998244353$ 意义下进行。

输入输出格式

输入格式：

第一行两个整数 $n$，$m$，意义如上。
第二行 $n+1$ 个整数，从低到高表示 $F(x)$ 的各个系数。
第三行 $m+1$ 个整数，从低到高表示 $G(x)$ 的各个系数。

输出格式：

第一行 $n-m+1$ 个整数，从低到高表示 $Q(x)$ 的各个系数。
第二行 $m$ 个整数，从低到高表示 $R(x)$ 的各个系数。
如果 $R(x)$ 不足 $m-1$ 次，多余的项系数补 $0$。

输入输出样例

输入样例#1：

5 1 1 9 2 6 0 8 1 7

输出样例#1：

237340659 335104102 649004347 448191342 855638018 760903695

说明

对于所有数据，$1 le m < n le 10^5$，给出的系数均属于 $[0, 998244353) cap mathbb{Z}$。

解题分析

设$F_R(x)=x^nF(frac{1}{x})$， 可以发现$F_R(x)$和$F(x)$的系数正好从大到小正好相反。 那么就有：
$F(frac{1}{x})=Q(frac{1}{x})G(frac{1}{x})+R(frac{1}{x}) \ F_R(x)=Q_R(x)G_R(x)+x^{n-m+1}R_R(x) \ F_R(x)equiv Q_R(x)G_R(x)(mod x^{n-m+1}) \ Q_R(x)equiv frac{F_R(x)}{G_R(x)} (mod x^{n-m+1})$
然后就是一波求逆， 然后带入原式即可得到$R(x)$。 代码如下： #include #include #include #include #include #include #define R register #define IN inline #define W while #define gc getchar() #define ll long long #define MOD 998244353 #define g 3 #define ginv 332748118 #define MX 400500 template <class T> IN void in(T &x) { x = 0; R char c = gc; for (; !isdigit(c); c = gc); for (; isdigit(c); c = gc) x = (x << 1) + (x << 3) + c - 48; } IN int fpow(R int base, R int tim) { int ret = 1; W (tim) { if (tim & 1) ret = 1ll * ret * base % MOD; base = 1ll * base * base % MOD, tim >>= 1; } return ret; } int n, m; int F[MX], G[MX], FR[MX], GR[MX], Q[MX], rev[MX], a[MX], b[MX], GRinv[MX], sur[MX]; namespace Poly { IN void NTT(int *dat, R int len, R int typ) { for (R int i = 1; i < len; ++i) if (rev[i] > i) std::swap(dat[rev[i]], dat[i]); R int seg, step, bd, now, cur, buf1, buf2, base, deal; for (seg = 1; seg < len; seg <<= 1) { base = fpow(typ ? g : ginv, (MOD - 1) / (seg << 1)), step = seg << 1; for (now = 0; now < len; now += step) { bd = now + seg, deal = 1; for (cur = now; cur < bd; ++cur, deal = 1ll * deal * base % MOD) { buf1 = dat[cur], buf2 = 1ll * dat[cur + seg] * deal % MOD; dat[cur] = (buf1 + buf2) % MOD, dat[cur + seg] = (buf1 - buf2 + MOD) % MOD; } } } if (typ) return; int inv = fpow(len, MOD - 2); for (R int i = 0; i < len; ++i) dat[i] = 1ll * dat[i] * inv % MOD; } void Getinv(R int up, R int lg, int *ans, int *ind) { if (up == 1) return ans[0] = fpow(ind[0], MOD - 2), void(); Getinv(up >> 1, lg - 1, ans, ind); R int len = up << 1; for (R int i = 1; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg - 1); for (R int i = 0; i < len; ++i) a[i] = b[i] = 0; for (R int i = 0; i < up; ++i) a[i] = ans[i], b[i] = ind[i]; NTT(a, len, 1), NTT(b, len, 1); for (R int i = 0; i < len; ++i) a[i] = (2 * a[i] % MOD - 1ll * b[i] * a[i] % MOD * a[i] % MOD + MOD) % MOD; NTT(a, len, 0); for (R int i = 0; i < up; ++i) ans[i] = a[i