概述

首先给定一个 $n - 1$ 次多项式 $A(x)$ 和一个 $m - 1$ 次多项式 $B(x)$，你需要求出一个 $n - m$ 次多项式 $Q(x)$ 和一个小于 $m - 1$ 次多项式 $R(x)$，满足 $A(x) = Q(x)B(x) +R(x)$。

思路

我们定义 $\text{rev}(A)$ 表示将 $n$ 次多项式 $A(x)$ 的系数翻转后的多项式。则有：

$$ \text{rev}(A) = x ^ n A\left(\frac{1}{x}\right) $$

接下来推一波式子：

$$ A(x) = Q(x)B(x) + R(x) $$

显然有：

$$ A\left(\frac{1}{x}\right) = Q\left(\frac{1}{x}\right) B\left(\frac{1}{x}\right) + R\left(\frac{1}{x}\right) $$

我们将等式两边同时乘上 $x ^ {n - 1}​$ 得到：

$$ x ^ {n - 1} A\left(\frac{1}{x}\right) = x ^ {n - m}Q\left(\frac{1}{x}\right)x ^ {m - 1}B\left(\frac{1}{x}\right) + x ^ {n - m + 1} x ^ {m - 2}R\left(\frac{1}{x}\right) $$

接下来把式子的一部分换成 $\text{rev}​$ 的形式：

$$ \text{rev}(A) = \text{rev}(Q)\times \text{rev}(B) + x ^ {n - m + 1}\text{rev}(R) $$

由于 $Q(x)​$ 在系数翻转后肯定不超过 $n - m​$ 次，那么我们可以把这个式子放到模 $x ^ {n - m + 1}​$ 的意义下，得到：

$$ \text{rev}(A)\equiv \text{rev}(Q)\times\text{rev}(B)\pmod{x ^ {n - m + 1}} $$

发现我们把 $R(x)$ 消去了！这样我们移项可以求出 $\text{rev}(Q)$ 的值：

$$ \text{rev}(Q) \equiv \text{rev}(A)\times\text{rev}(B)^{-1}\pmod{x ^ {n - m + 1}} $$

再把系数翻转回来就可以得到 $Q(x)$ 了。

对于 $R(x)$，我们直接代入 $R(x) = A(x) - Q(x)B(x)$ 就可以了。

时间复杂度：$\mathcal O(n \log n)$。

代码

Vec operator / (Vec A, Vec B) {
    int n = A.size() - B.size() + 1;
    if (n <= 0) return Vec(1, 0);
    std::reverse(A.begin(), A.end());
    std::reverse(B.begin(), B.end());
    A.resize(n), B.resize(n);
    A = fix(A * ~B, n);
    std::reverse(A.begin(), A.end());
    return A;
}
Vec operator % (Vec A, Vec B) {
    int n = B.size() - 1;
    return fix(A - A / B * B, n);
}