给你一个 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)。
考虑到如果没有余数就是直接多项式求逆,但是有余数,所以问题就在于怎么把余数消掉。
那我们一般的取模是消掉高项的,但是余数是低项的,所以我们考虑一个操作叫做翻转,然后有一个这样的定义方法:
\(F^T(x)=x^nF(x^{-1})\)
其实挺显然的,就原本在 \(x^i\) 的变成了 \(x^{n-i}\)。
然后考虑推给的式子:\(F(x)=Q(x)*G(x)+R(x)\)
然后换元:\(F(x^{-1})=Q(x^{-1})*G(x^{-1})+R(x^{-1})\)
集体乘 \(x^n\):\(x^nF(x^{-1})=x^nQ(x^{-1})*G(x^{-1})+x^nR(x^{-1})\)
然后你可以看这几个多项式的项数分别是多少:
\(F(x)\):\(n\),\(G(x)\):\(m\),\(Q(x)\):\(n-m\),\(R(x)\):\(m-1\)
\(x^nF(x^{-1})=x^{n-m}Q(x^{-1})*x^mG(x^{-1})+x^{n-m+1}*x^{m-1}R(x^{-1})\)
\(F^T(x)=Q^T(x)*G^T(x)+x^{n-m+1}R^T(x)\)
然后你会发现它(\(R^T(x)\))变成了高项的,然后你可以在 \({\pmod {x^{n-m+1}}}\) 的条件下进行。
\(F^T(x)=Q^T(x)*G^T(x)\pmod{x^{n-m+1}}\)
然后后面的操作都能看出了:
\(Q^T(x)=F^T(x)*G^T(x)^{-1}\pmod{x^{n-m+1}}\)
那就可以做了,先得到翻转的 \(F^T,G^T\)。
然后 \(G^T\) 逆元求出来,然后乘起来就是答案啦。
然后通过 \(F(x)=Q(x)*G(x)+R(x)\) 有 \(R(x)=F(x)-Q(x)*G(x)\),所以乘一下减一下就有了。
然后要小小注意的是范围要注意一下,因为你有取模所以你要把以外的都直接清空掉。
然后就没什么了。
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define mo 998244353 #define clr(f, n) memset(f, 0, (n) * sizeof(int)) #define cpy(f, g, n) memcpy(f, g, (n) * sizeof(int)) using namespace std; const int N = 100000 * 8 + 1; int n, m, f[N], g[N], an[N], inv[N], G = 3, Gv; int jia(int x, int y) {return x + y >= mo ? x + y - mo : x + y;} int jian(int x, int y) {return x < y ? x - y + mo : x - y;} int cheng(int x, int y) {return 1ll * x * y % mo;} int ksm(int x, int y) {int re = 1; while (y) {if (y & 1) re = cheng(re, x); x = cheng(x, x); y >>= 1;} return re;} void Init() { Gv = ksm(G, mo - 2); inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = cheng(inv[mo % i], mo - mo / i); } void get_an(int limit, int l_size) { for (int i = 0; i < limit; i++) an[i] = (an[i >> 1] >> 1) | ((i & 1) << (l_size - 1)); } void NTT(int *f, int limit, int op) { for (int i = 0; i < limit; i++) if (an[i] < i) swap(f[an[i]], f[i]); for (int mid = 1; mid < limit; mid <<= 1) { int Wn = ksm(op == 1 ? G : Gv, (mo - 1) / (mid << 1)); for (int R = (mid << 1), j = 0; j < limit; j += R) { int w = 1; for (int k = 0; k < mid; k++, w = cheng(w, Wn)) { int x = f[j | k], y = cheng(w, f[j | mid | k]); f[j | k] = jia(x, y); f[j | mid | k] = jian(x, y); } } } if (op == -1) { int limv = ksm(limit, mo - 2); for (int i = 0; i < limit; i++) f[i] = cheng(f[i], limv); } } void px(int *f, int *g, int limit) { for (int i = 0; i < limit; i++) f[i] = cheng(f[i], g[i]); } void times(int *f, int *g, int n, int m) { static int tmp[N]; int limit = 1, l_size = 0; while (limit <= n + n) limit <<= 1, l_size++; cpy(tmp, g, n); clr(tmp + n, limit - n); get_an(limit, l_size); NTT(f, limit, 1); NTT(tmp, limit, 1); px(f, tmp, limit); NTT(f, limit, -1); clr(f + m, limit - m); clr(tmp, limit); } void invp(int *f, int n) { static int w[N], r[N], tmp[N]; w[0] = ksm(f[0], mo - 2); int limit = 1, l_size = 0; for (int len = 2; (len >> 1) <= n; len <<= 1) { limit = len; l_size++; get_an(limit, l_size); cpy(r, w, len >> 1); cpy(tmp, f, limit); NTT(tmp, limit, 1); NTT(r, limit, 1); px(r, tmp, limit); NTT(r, limit, -1); clr(r, limit >> 1); cpy(tmp, w, len); NTT(tmp, limit, 1); NTT(r, limit, 1); px(r, tmp, limit); NTT(r, limit, -1); for (int i = (len >> 1); i < len; i++) w[i] = jian(cheng(w[i], 2), r[i]); } cpy(f, w, n); clr(w, n); clr(r, n); clr(tmp, n); } void dao(int *f, int n) { for (int i = 1; i < n; i++) f[i - 1] = cheng(f[i], i); f[n - 1] = 0; } void jifen(int *f, int n) { for (int i = n; i >= 1; i--) f[i] = cheng(f[i - 1], inv[i]); f[0] = 0; } void lnp(int *f, int n) { static int g[N]; cpy(g, f, n); dao(g, n); invp(f, n); times(f, g, n, n); jifen(f, n - 1); clr(g, n); } void mof(int *f, int n, int *g, int m) { static int f_[N], g_[N]; int L = n - m + 1; reverse(f, f + n); cpy(f_, f, L); reverse(f, f + n); reverse(g, g + m); cpy(g_ , g, L); reverse(g, g + m); invp(g_, L); times(g_, f_, L, L); reverse(g_, g_ + L); times(g, g_, n, n); for (int i = 0; i < m - 1; i++) g[i] = jian(f[i], g[i]); clr(g + m - 1, L); cpy(f, g_, L); clr(f + L, n - L); } int main() { Init(); 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]); mof(f, n, g, m); for (int i = 0; i < n - m + 1; i++) printf("%d ", f[i]); printf("\n"); for (int i = 0; i < m - 1; i++) printf("%d ", g[i]); return 0; }