0x01 前言

答应我，下辈子不要再碰高投入低回报的多项式科技了，这个还真的不如 dp、字符串或者和图论有关的题目效益更高的。

以转置方法实现的多点求值，需要对多项式、FFT 有着极其深刻的理解，对矩阵与高维向量能纯熟运用以及内心拥有着高强度悟道的勇气。

老样子，如果发现有什么问题，尽可能不要吝啬，还多请指教。能改则抽时间出来改。

0x02 介绍

考察两多项式的乘积，记其长度分别为 $n,n’$，此时有

$$\begin{aligned} p(x)q(x)&=(a_0+a_1x+\cdots+a_{n-1}x^{n-1})(b_0+b_1x+\cdots+b_{n’-1}x^{n’-1})\\ &=a_0b_0+(a_0b_1+a_1b_0)x+\cdots+a_{n-1}b_{n’-1}x^{n+n’-2}\\ &=\sum\limits_{i=0}^{n+n’-2}c_ix^i\\ &=\sum\limits_{i=0}^{n+n’-2}\left(\sum\limits_{\substack{j=0 \\ 0 \leq j \leq n-1 \\ 0\leq i-j\leq n’-1 }}^{i}a_jb_{i-j}\right)x^i \end{aligned}$$

显然，这就是个能用两次 FFT + 点值相乘 + 一次 IFFT 实现的加法卷积。

而所谓加法卷积，是指所有满足下标特点为 $a_j,b_{i-j}$ 形式的系数相乘后，按照下标和为 $i$ 的性质贡献到 $x^i$ 系数的运算。本质上就是多次相乘然后累加的过程。

具体而言，我们将相乘后的结果摊到向量上并尝试用矩阵与向量相乘的形式表出。

以施行傅里叶变换后，确定两多项式长度为 $m=4$ 时的情况为例，加法卷积的两种形式如下。(注：留白表示留白处置 $0$，标蓝处表示并未计算到)。

最直观的展开。
$$\begin{aligned} p(x)q(x)&=(a_0+a_1x+a_2x^2+a_3x^3)(b_0+b_1x+b_2x^2+b_3x^3)\\ &=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+(a_0b_3+a_1b_2+a_2b_1+a_3b_0)x^3 \\ &+(a_1b_3+a_2b_2+a_3b_1)x^4+(a_2b_3+a_3b_2)x^5 + a_3b_3x^6 +\color{blue}{0 \cdot x^7}+\color{blue}{0 \cdot x^8}. \end{aligned}$$
列出系数列表有

从而保证矩阵与向量相乘的形式。那么此时有
$$\begin{aligned} \boldsymbol{A}\boldsymbol{v}= \left(\begin{array}{cccc} a_0 \\ a_1 &a_0 \\ a_2 &a_1 &a_0 \\ \hdashline a_3 &a_2 &a_1 &a_0\\ % 都能算到的 &a_3 &a_2 &a_1\\ & &a_3 &a_2\\ & & &a_3\\ \end{array}\right) \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{pmatrix}= \begin{pmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \\ c_4 \\ c_5 \\ c_6 \end{pmatrix} \end{aligned}$$
我们再来看矩阵转置与向量相乘的情况（这里舍弃掉矩阵中竖实线右侧的部分，不然不能乘）。
$$\boldsymbol{A}^T\boldsymbol{v}=\left( \begin{array}{cccc|ccc} a_0 &a_1 &a_2 &a_3\\ &a_0 &a_1 &a_2 &a_3 \\ & &a_0 &a_1 &a_2 &a_3 \\ && &a_0 &a_1 &a_2 &a_3 \end{array}\right) \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{pmatrix}= \begin{pmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{pmatrix}$$

然后就能注意到，结果下标 $i$ 是通过系数 $b$ 的下标减去系数 $a$ 的下标得到。因此叫减法卷积。

同时转置矩阵中，实线左侧的部分与 原矩阵 中画了虚线的下侧部分在结构上是一致的。

尝试将转置矩阵补全成原矩阵的形式以重新定义转置矩阵，这样我们就能够套用 FFT 参与计算了。此时便可以有
$$\boldsymbol{A}^T\boldsymbol{v}=\left( \begin{array}{cccc} a_3 \\ a_2 &a_3 \\ a_1 &a_2 &a_3 \\ a_0 &a_1 &a_2 &a_3\\ &a_0 &a_1 &a_2 \\ & &a_0 &a_1\\ && &a_0 \end{array}\right) \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{pmatrix}= \begin{pmatrix} \color{red}{c_{-3}} \\ \color{red}{c_{-2}} \\ \color{red}{c_{-1}} \\ c_0 \\ c_1\\ c_2 \\ c_3 \end{pmatrix}$$

标红处旨在示意需要去除（后同）。因为它们是 $a$ 的下标值减去 $b$ 的下标值而不是我们的目的“ $b-a$ ”。但总的来讲，要算的值出现在了答案的后半部分。

而解决的方式很简单。到按顺序最后覆盖写入即可。这时就可拿 FFT 做了。

以上两点：

• 两多项式相乘可视为矩阵作用于某个向量；
• 计算矩阵转置后与向量相乘的结果，只需使充当矩阵的数组/向量反转，正常执行加法卷积，便可得到后移了几个位置之后的结果。

个人认为是整套算法最巧妙，也是最难理解的地方。由于在实现上会遇到很多障碍，这里统一逐项击破。

首先考察 修改了定义 的转置矩阵。本来，拿转置后的矩阵左乘向量是要要求向量长度与之匹配的。即
$$\boldsymbol{A}^T\boldsymbol{v}=\left( \begin{array}{ccccccc} a_0 &a_1 &a_2 &a_3\\ &a_0 &a_1 &a_2 &a_3 \\ & &a_0 &a_1 &a_2 &a_3 \\ && &a_0 &a_1 &a_2 &a_3 \end{array}\right) \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ \end{pmatrix}= \begin{pmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{pmatrix}= \begin{pmatrix} a_0b_0+a_1b_1+a_2b_2+a_3b_3 \\ a_0b_1+a_1b_2+a_2b_3+a_3b_4 \\ a_0b_2+a_1b_3+a_2b_4+a_3b_5 \\ a_0b_3+a_1b_4+a_2b_5+a_3b_6 \end{pmatrix}$$
这样才能保证向量分量没有少算。所以在转置前，需要保证向量长度是矩阵的两倍（多出来的部分可以不用考虑）。

但是这个时候我们发现，在保证作用效果不改变的前提下，为使矩阵与向量 $\boldsymbol{b}$ 的长度相适，我们需要在施行傅里叶变换前，先反转；而后用数字 $0$ 扩充设定为矩阵的多项式的长度，从而使得反转的做法可行。

$$\boldsymbol{A}^T\boldsymbol{v}=\left( \begin{array}{} a_3 \\ a_2 &a_3 \\ a_1 &a_2 &a_3 \\ a_0 &a_1 &a_2 &a_3\\ 0 &a_0 &a_1 &a_2 &a_3\\ 0 &0 &a_0 &a_1 &a_2 &a_3\\ 0 &0&0& a_0 &a_1 &a_2 &a_3\\ \end{array}\right) \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ \end{pmatrix}= \begin{pmatrix} \color{red}{c_{-3}} \\ \color{red}{c_{-2}} \\ \color{red}{c_{-1}} \\ c_{0} \\ c_1 \\ c_2 \\ c_3 \end{pmatrix}= \begin{pmatrix} \color{red}{a_3b_0} \\ \color{red}{a_3b_1+a_3b_2} \\ \color{red}{a_3b_2+a_2b_1+a_1b_0} \\ a_3b_3+a_2b_2+a_1b_1+a_0b_0 \\ a_3b_4+a_2b_3+a_1b_2+a_0b_1 \\ a_3b_5+a_2b_4+a_1b_3+a_0b_2 \\ a_3b_6+a_2b_5+a_1b_4+a_0b_3 \\ \end{pmatrix}$$
注意到 FFT 在预处理时总是将序列的长度分配为 $2$ 的非负整数次幂。如此一来，转置 / 减法卷积 的算法依然可表示为下面这样（本质上，还是相当于 $4$ 位数乘以 强制长度 是 $8$ 的数）。

$$\boldsymbol{A}^T\boldsymbol{v} = \left( \begin{array}{} a_3 \\ a_2 &a_3 \\ a_1 &a_2 &a_3 \\ a_0 &a_1 &a_2 &a_3\\ &a_0 &a_1 &a_2 &a_3\\ &&a_0 &a_1 &a_2 &a_3\\ &&&a_0 &a_1 &a_2 &a_3\\ &&&&a_0 &a_1 &a_2 &a_3\\ %第8行 &&&&&a_0 &a_1 &a_2 &a_3\\ &&&&&&a_0 &a_1 &a_2 &a_3\\ &&&&&&&a_0 &a_1 &a_2 &a_3\\ &&&&&&&&a_0 &a_1 &a_2 &a_3\\ &&&&&&&&&a_0 &a_1 &a_2 &a_3\\ &&&&&&&&&&a_0 &a_1 &a_2 &a_3\\ &&&&&&&&&&&a_0 &a_1 &a_2 &a_3\\ &&&&&&&&&&&&a_0 &a_1 &a_2 &a_3\\ \end{array}\right) \begin{pmatrix}b_0\\ b_1 \\b_2\\b_3\\ b_4 \\b_5\\b_6\\ \color{red}{b_7}\\ \color{red}{b_8} \\ \color{red}{b_9} \\ \color{red}{b_{10}}\\ \color{red}{b_{11}} \\ \color{red}{b_{12}} \\ \color{red}{b_{13}} \\ \color{red}{b_{14}} \\ \color{red}{b_{15}}\end{pmatrix}= \begin{pmatrix} \color{red}{a_3b_0} \\ \color{red}{a_3b_1+a_3b_2} \\ \color{red}{a_3b_2+a_2b_1+a_1b_0} \\ a_3b_3+a_2b_2+a_1b_1+a_0b_0 \\ a_3b_4+a_2b_3+a_1b_2+a_0b_1 \\ a_3b_5+a_2b_4+a_1b_3+a_0b_2 \\ a_3b_6+a_2b_5+a_1b_4+a_0b_3 \\ \color{red}{\sum ab}\\ \color{red}{\sum ab}\\ \color{red}{\sum ab}\\ %第10行 \color{red}{\sum ab}\\ \color{red}{\sum ab} \\ \color{red}{\sum ab}\\ \color{red}{\sum ab}\\ \color{red}{\sum ab}\\ \color{red}{\sum ab}\\ \end{pmatrix}$$

所以流程是：

1. 实现内带长度调整、并可返回调整后长度的 FFT 与 IFFT。
2. 定义转置乘法（减法卷积）函数，形参列表有：向量 $\boldsymbol{b}$,矩阵 $\boldsymbol{A}$（本质上是数组/向量）；可以返回转置乘法后的多项式。
3. 取出向量与矩阵的长度，分别记为 $n,n_1$。
4. 如果向量的长度小于矩阵的长度，直接返回空的多项式（调用构造函数即可）。
5. 反转矩阵。
6. 重新分配两者的长度为 $n+n_1-1$。
7. 对两者施行傅里叶变换，并记录此时的长度 $m$。
8. 从 $0\to m-1$，相乘向量与矩阵的每一项，结果记录到向量或者矩阵上。
9. 对结果施行傅里叶逆变换。
10. 从 $0 \to n_1-1$，以 res[i] = res[i + n1 - 1] 的形式覆盖。
11. 重新分配答案的长度为 $n_1$。
12. 返回答案。

这里还是很直观的，代码也比较好敲，后面再统一给出。

然后我们转过头来看，给定 $x_0,x_1,\ldots,x_{m-1}$ 与 $f(x)$ 的系数 $a_0,a_1,\ldots,a_{m-1}$，求 所有 $\forall i \in [1,m-1],f(a_i)$。

将所有条件变到矩阵上，并将 $x,a,f(a_i)$ 换为 $a,f,g_i$。
$$\begin{aligned} \begin{pmatrix} 1 &a_0 &a_0^2 & \ldots &a_0^{m-1} \\ 1 &a_1 &a_1^2 & \ldots &a_1^{m-1} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 1 &a_{m-1} &a_{m-1}^2 &\ldots &a_{m-1}^{m-1} \end{pmatrix} \begin{pmatrix} f_0 \\f_1 \\ \vdots \\f_{m-1} \end{pmatrix} =\begin{pmatrix} g_0\\ g_1\\ \vdots \\ g_{m-1} \end{pmatrix}=\begin{pmatrix} f_0+f_1a_0+\cdots+f_{m-1}a_0^{m-1}\\ f_0+f_1a_1+\cdots+f_{m-1}a_1^{m-1}\\ \vdots \\ f_0+f_1a_{m-1}+\cdots+f_{m-1}a_{m-1}^{m-1} \end{pmatrix} \end{aligned}$$

其中等式最右侧的向量待求。

而这里有一个问题：到底是系数的数量多还是点的数量多？如果不能很好解决，这到后面将会是一个编写障碍。

注意到我们还是可以通过为向量或者矩阵补 $0$ 的方式使得讨论不会那么繁琐。具体来说：

1. 若向量长度小于矩阵长度，即系数比待计算的点值少；则只需以点值的数量重新作为向量的长度。
2. 若向量长度等于矩阵长度，则此时可忽略。
3. 若向量长度大于矩阵长度，即系数数量比点值的多，则只需将点值补成与矩阵长度相适的长度。

所以这个问题结束了。

回到求向量的正道上，如果最终还是硬套上范德蒙矩阵逆的形式，做法显然无法接受。查看转置后的结果。

$$\begin{aligned} \begin{pmatrix} 1 &1 &1 & \ldots &1 \\ a_0 &a_1 &a_2 & \ldots &a_{m-1} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ a_0^{m-1} &a_1^{m-1} &a_2^{m-1} &\ldots &a_{m-1}^{m-1} \end{pmatrix} \begin{pmatrix} f_0 \\ f_1 \\ \vdots \\ f_{m-1} \end{pmatrix} =\begin{pmatrix} f_0+f_1+\cdots+f_{m-1} \\ f_0a_0+f_1a_1+\cdots+f_{m-1}a_{m-1} \\ \vdots \\ f_0a_0^{m-1}+f_1a_1^{m-1}+\cdots+f_{m-1}a_{m-1}^{m-1} \end{pmatrix} \end{aligned}$$

然后回代到表示结果多项式的函数之中。（为了区别，以 $g$ 代表待求的多项式，$g_t$ 为转置了矩阵后所得到的结果）。

$$\begin{aligned} g_t(x)&= (f_0+f_1+\cdots+f_{m-1})+\left(f_0a_0+f_1a_1+\cdots+f_{m-1}a_{m-1}\right)x+\cdots+\left(f_0a_0^{m-1}+f_1a_1^{m-1}+\cdots+f_{m-1}a_{m-1}^{m-1}\right)x^{m-1}\\ &=f_0(1+a_0x+a_0^2x^2+\cdots+a_0^{m-1}x^{m-1})+\cdots+f_{m-1}(1+a_{m-1}x+a_{m-1}^2x^2+\cdots+a_{m-1}^{m-1}x^{m-1})\\ &=f_0[x^m]\dfrac{1}{1-a_0x}+\cdots+f_{m-1}[x^m]\dfrac{1}{1-a_{m-1}x}\\ &=\sum_{i=0}^{m-1}[x^m]\dfrac{f_i}{1-a_ix}\\ &= [x^m]\dfrac{\sum\limits_{i=0}^{m-1} f_{i} \prod\limits_{j=0 \atop j\ne i}^{m-1}(1-a_ix)}{\prod\limits_{i=0}^{m-1}(1-a_ix)}. \end{aligned}$$
这个式子可以使用分治求出。具体做法是，将分母视为多项式 $Q_{[0,m-1]}(x)=\prod\limits_{i=0}^{m-1}(1-a_ix)$，分子为 $P_{[0,m-1]}(x)$。
那么，有
$$\begin{align}& Q_{[l,r]}=Q_{[l,mid]}\cdot Q_{[mid+1,r]} \\&P_{[l,r]}=P_{[l,mid]}\cdot Q_{[mid+1,r]}+P_{[mid+1,r]}\cdot Q_{[l,mid]}\end{align}$$

显然，线段树就能完成 $Q(x)$ 的维护了。其次，分子项再套个分治也能解决问题。但关键的关键在于，求得转置矩阵与向量的乘积之后，怎么样才能让结果回到正确的道路？

矩阵的转置满足$(\boldsymbol{A}_1 \boldsymbol{A}_2 \cdots\boldsymbol{A}_n)^T=\boldsymbol{A}_n^T\cdots\boldsymbol{A}_2^T\boldsymbol{A}_1^T$ 以及 $(\boldsymbol{A}^T)^T=\boldsymbol{A}$。

同时，任意矩阵都能经由很多个初等矩阵相乘得出。即 $\boldsymbol{A}$可被分解为 $\boldsymbol{B}_1\boldsymbol{B}_2\cdots \boldsymbol{B}_n$。那么，相应地有 $\boldsymbol{A}^T=\boldsymbol{B}_n^T\cdots\boldsymbol{B}_2^T\boldsymbol{B}_1^T$。

既然我们得到了 $g_t(x)=\dfrac{P_{[0,m-1]}(x)}{Q_{[0,m-1]}(x)}$，就可以靠 $\boldsymbol{A}^T\boldsymbol{v}=\boldsymbol{B}_n^T\cdots\boldsymbol{B}_2^T\boldsymbol{B}_1^T\boldsymbol{v}$推回去。

具体来讲，结合要求的结果来看，只有分子才有答案才有的 $f_i$。

又由于 $P_{[l,r]}=P_{[l,mid]}\cdot Q_{[mid+1,r]}+P_{[mid+1,r]}\cdot Q_{[l,mid]},\boldsymbol{A}^T\boldsymbol{v}=\dfrac{P_{[l,r]}}{Q_{[l,r]}}$ 的存在，分治算相乘后相加到最后合并回来，整体乘上 $Q_{[l,r]}$ 的逆的过程均可视为前文所提到的矩阵左乘向量。这个时候显然 $Q(x)$ 作为矩阵，而 $P(x)$ 作为向量。

所以，我们只需要自顶向下，把原来顺过来求 $\boldsymbol{A}^T\boldsymbol{v}$ 的所有语句，倒过来拿去算减法卷积后，在最底层叶子节点的常数项上就可以拿到我们要的答案了。

至此，我们实现了一个花上雕花的算法。

0x03 cpp代码实现

基于描述上的难度以及算法的巧妙性，我想，代码是必须要给出的。虽然跑得不如人家用数组实现的快，反而还显得慢了。

// 大学牲不如第一个找出这些关系并写出代码的OI爷orz
using ll = long long;
using namespace std;
using arr = vector<int>;

const int N = 3e5 + 10;
const int mod = 998244353, gi = 332748118;

ll n, m;
ll rev[N << 2], tot;
inline ll read()
{
    ll res = 0;
    int c, f = 1;
    while (!isdigit(c = getchar())) f = c ^ '-' ? f : -1; 
    while (isdigit(c))
        res = res * 10 + c - 48, c = getchar();
    return res * f;
}
inline ll qpow(ll a, ll k)
{
    ll res = 1;
    for (; k; k >>= 1, a = a * a % mod)
        res = k & 1 ? (res * a) % mod : res;
    return res;
}
int fft(arr &a, int sig = 1)
{ // 快速数论变换，FFT 换了层皮，也可以略过（数论改天再补补）。
    int n = a.size();
    int bits = -1, tot = 1;
    while (tot < n)
        tot <<= 1, bits++;
    if ((int)a.size() < tot)
        a.resize(tot);
    for (int i = 0; i < tot; ++i)
    {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bits);
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    }

    for (int mid = 1; mid < tot; mid <<= 1)
    {
        ll w = qpow(sig ^ 1 ? gi : 3, (mod - 1) / (mid << 1));
        for (int i = 0; i < tot; i += mid << 1)
        {
            ll w0 = 1;
            for (int j = 0; j < mid; ++j, w0 = w0 * w % mod)
            {
                ll x = a[i + j], y = (ll)a[i + j + mid] * w0 % mod;
                a[i + j] = (x + y) % mod, 
                a[i + j + mid] = (x - y + mod) % mod;
            }
        }
    }

    if (sig ^ 1)
    {
        ll invlen = qpow(tot, mod - 2);
        for (int i = 0; i < tot; ++i)
            a[i] = (ll)a[i] * invlen % mod;
    }
    return tot;
}

void inv(arr &a)  // 实参。
// 不会多项式求逆都没学就来看多点求值吧？！
{
    arr f, g;
    int n = a.size(), tot = 1, Nn = 0;
    g.push_back(qpow(a[0], mod - 2));
    while (tot < n)                          // 改递归为循环，通过倍增的方式求逆。
    {
        tot <<= 1;
        f = a, f.resize(tot);
        f.resize(tot << 1), g.resize(tot << 1);
        Nn = fft(f);
        fft(g);
        for (int i = 0; i < Nn; ++i)         // 牛顿迭代算出来的。
            g[i] = (ll)g[i] * (2LL - (ll)f[i] * g[i] % mod + mod) % mod;
        fft(g, -1), g.resize(tot);           // 重新分配大小。
    }
    a = g, a.resize(n);                      // 这里需要分配长度。
}

arr mul(arr a, arr b)
{ // 加法卷积不多说。
    int n = a.size(), n1 = b.size();
    a.resize(n + n1 - 1), b.resize(n + n1 - 1);

    int Nn = fft(a);
    fft(b);

    for (int i = 0; i < Nn; ++i)
        a[i] = (ll)a[i] * b[i] % mod;
    fft(a, -1), a.resize(n + n1 - 1);

    return a;
}

arr mulT(arr b, arr a) 
{ // 向量 矩阵。
    int n = b.size(), n1 = a.size();

    if (n < n1)
        return arr();                        // 特判，防止出错。

    reverse(a.begin(), a.end());
    a.resize(n + n1 - 1),
    b.resize(n + n1 - 1);


    int m = fft(a);                          // 这里正常算就行。
    fft(b);
    for (int i = 0; i < m; ++i)
        a[i] = (ll)a[i] * b[i] % mod;
    fft(a, -1);

    for (int i = 0; i < n1; i++)             // 按说明更改即可。
        a[i] = a[i + n1 - 1];
    a.resize(n1);                            // 防止后面出错。
    return a;
} 
/*\ 其实，画出来把玩也能写出自己想要的形式，不一定需要用别人的模板（划掉） 
 *  能照着打出来个人认为也是在锻炼代码阅读能力，过后不看答案再打出来对加深理解还是有很大的帮助的。
\*/
arr tr[N << 2];
ll res[N];

int cnt = 0;
void build(int x, int l, int r, const arr &a)
{
    if (l == r)                             // 1 - a_i * x，所以要放两项。
    {
        tr[x].clear();                      // 以防万一。
        tr[x].push_back(1);
        tr[x].push_back((mod - a[l]) % mod);
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid, a);
    build(x << 1 | 1, mid + 1, r, a);
    tr[x] = mul(tr[x << 1], tr[x << 1 | 1]);// 算完记得乘起来。
}

void down(int x, int l, int r, arr F) 
{
    if (l == r)
        return (void)(res[l] = F[0]);       // 叶子层就拿常数项。
    int mid = (l + r) >> 1;
                                            // 注意这里和下面的写法。
    down(x << 1, l, mid, mulT(F, tr[x << 1 | 1])); 
    down(x << 1 | 1, mid + 1, r, mulT(F, tr[x << 1]));
}

void solve(arr &a, arr &b)
{
    int n = max(a.size(), b.size());        // 比一下，是要求的式子多还是系数多。

    a.resize((1 + n) << 1), b.resize(n);    // 然后重新分配，向量必须是矩阵长度的两倍。
    build(1, 0, n - 1, b);                  // 先建树，以得到连乘项。
    inv(tr[1]);                             // 使整个连乘式变成分母，而保持其它不变。
    down(1, 0, n - 1, mulT(a, tr[1LL]));    // 第一次转置乘。
}

arr aa, ff;

#define Ored
int main()
{
#ifndef Ored
    freopen("mid.in", "r", stdin);
    freopen("mid.out", "w", stdout);
#endif

    n = read() + 1, m = read();
    for (ll i = 0; i < n; ++i)
        ff.emplace_back(read());            // 系数。

    for (ll j = 0; j < m; ++j)
        aa.emplace_back(read());            // 要代入的点值。

    solve(ff, aa);
    for (int i = 0; i < m; ++i)
        printf("%lld\n", res[i]);

#ifndef Ored
    fclose(stdin);
    fclose(stdout);
#endif
    system("pause");
    return 0;
}

时间复杂度 $O(n \log^2 n)$。

0x04 参考资料

• gezelligheid1.github.io/2022/06/09/转置原理和多项式多点求值
• compilationfail.github.io/58244.html
• jkloverdcoi.github.io/2020/08/04/转置原理及其应用/slide.pdf
• 洛谷P5050 【模板】多项式多点求值题解区
• 浅谈基于转置原理的多项式多点求值新方法（附上简洁但大常数的代码）
• 如何用latex编写矩阵（包括各类复杂、大型矩阵）
• LaTeX-数学符号（二）矩阵与大括号