洛谷P4512 【模板】多项式除法题解

题意：

给定一个 $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 \le m < n \le 10^5$，给出的系数均属于 $[0, 998244353) \cap \mathbb{Z}$。

给定多项式 $f(x),g(x)$ ，求 $g(x)$ 除 $f(x)$ 的商 $Q(x) $和余数 $R(x)$ 。

考虑构造变换

$f^R(x)=x^{\operatorname{deg} f} f\left(\frac{1}{x}\right)$

观察可知其实质为反转 $f(x)$ 的系数。

设 $n=\operatorname{deg} f,~m = \operatorname{deg} g$ （多项式的次数）

将 $f(x)=Q(x) g(x)+R(x)$ 中的 $x$ 替换成 $\frac{1}{x}$ 并将其两边都乘上 $x^n$ ，得到

$\begin{aligned} x^n f\left(\frac{1}{x}\right) & =x^{n-m} Q\left(\frac{1}{x}\right) x^m g\left(\frac{1}{x}\right)+x^{n-m+1} x^{m-1} R\left(\frac{1}{x}\right) \\[6pt] f^R(x) & =Q^R(x) g^R(x)+x^{n-m+1} R^R(x) \end{aligned}$

注意到上式中 $R^R(x)$ 的 $x^{n-m+1}$ ，则将其放到模 $x^{n-m+1}$ 意义下即可消除 $R^R(x)$ 带来的影响.

又因为 $Q^R(x)$ 的次数为 $(n - m) < (n - m + 1)$ ，故 $Q^R(x)$ 不会受到影响，则

$f^R(x) \equiv Q^R(x) g^R(x) \quad\left(\bmod x^{n-m+1}\right)$

使用多项式求逆即可求出 $Q(x)$ ，将其反代回去即可得到 $R(x)$ 。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1048576 + 15))

const int P = 998244353;
const int G = 3, Gi = 332748118;
int a[N], b[N], c[N], d[N], t[N], ans1[N], ans2[N], r[N];
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % P;
        b >>= 1; a = a * a % P;
    }
    return r;
}
void NTT(int *A, int limit, int type)
{
    for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid *= 2)
    {
        int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
        for(int j = 0; j < limit; j += (mid * 2))
        {
            int w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P)
            {
                int x = A[j + k], y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
            }
        }
    }
    if(type == -1)
    {
        int Inv = qpow(limit, P - 2);
        for(int i = 0; i < limit; i++) A[i] = A[i] * Inv % P;
    }
}
void Inv(int n, int *a, int *b)
{
    if(n == 1) { b[0] = qpow(a[0], P - 2); return; }
    Inv((n + 1) / 2, a, b);
    int l = 0, limit = 1;
    for(; limit <= (n - 1) * 2; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    for(int i = 0; i < n; i++) t[i] = a[i];
    for(int i = n; i < limit; i++) t[i] = 0;
    NTT(t, limit, 1); NTT(b, limit, 1);
    for(int i = 0; i < limit; i++)
        b[i] = (2 - t[i] * b[i] % P + P) % P * b[i] % P;
    NTT(b, limit, -1);
    for(int i = n; i < limit; i++) b[i] = 0;
    for(int i = 0; i < limit; i++) t[i] = 0;
}
void Div(int n, int m, int *a, int *b, int *ans1, int *ans2)
{
    for(int i = 0; i < m; i++) c[i] = b[i];
    reverse(c, c + m); Inv(n, c, d);

    int l = 0, limit = 1;
    for(; limit <= (n - 1) * 2; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));

    for(int i = 0; i < n; i++) c[i] = a[i];
    for(int i = n; i < limit; i++) c[i] = 0;
    reverse(c, c + n);
    
    NTT(c, limit, 1); NTT(d, limit, 1);
    for(int i = 0; i < limit; i++) ans1[i] = c[i] * d[i] % P;
    NTT(ans1, limit, -1);

    reverse(ans1, ans1 + n - m + 1);
    for(int i = 0; i < n - m + 1; i++) c[i] = ans1[i];
    for(int i = n - m + 1; i < limit; i++) c[i] = 0;

    for(int i = 0; i < m; i++) d[i] = b[i];
    for(int i = m; i < limit; i++) d[i] = 0;

    NTT(c, limit, 1); NTT(d, limit, 1);
    for(int i = 0; i < limit; i++) c[i] = c[i] * d[i] % P;
    NTT(c, limit, -1);
    for(int i = 0; i < m - 1; i++) ans2[i] = (a[i] + P - c[i]) % P;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; ++n; ++m; // m < n
    for(int i = 0, x; i < n; i++) cin >> x, a[i] = (x + P) % P;
    for(int i = 0, x; i < m; i++) cin >> x, b[i] = (x + P) % P;
    Div(n, m, a, b, ans1, ans2);
    for(int i = 0; i < n - m + 1; i++) cout << ans1[i] << " \n"[i == n - m];
    for(int i = 0; i < m - 1; i++) cout << ans2[i] << " \n"[i == m - 2];
    return 0;
}