转置原理和多项式多点求值

这篇博客背后是阅读十数篇博客和高强度悟道

矩阵的初等变换和初等矩阵:

三种矩阵初等变换

• 交换矩阵两行(列)
• 对一行(列)乘
• 将第行乘加给第行

对单位矩阵实施一次初等变换得到的矩阵称为初等矩阵。

一种初等变换对应一个初等矩阵

一个可逆矩阵可分为多个初等矩阵相乘

转置原理：

转置定理：如果，可得

线性算法的转置：

1. 已知矩阵，输入向量，向量为左乘的运算结果，求解的算法为线性算法
2. 称与互为转置
3. 若矩阵可逆，可分为若干个初等矩阵相乘 此时若算法较难求出，可先求解的优化方法即 的优化方法，求出的优化方法后以相反的运算顺序即可求出的优化方法，具体原理可以参考其他博客，笔者高强度悟道才理解此处

多项式乘法

对于一个多项式次多项式和次多项式,令，可知将看作向量，看作矩阵

以举例，考虑矩阵形式： 该线性算法转置为 即，可见加法卷积的转置为减法卷积，加法卷积的转置标记为

多项式多点求值

给定一个次多项式，现在请你对于，求出 。

不妨都将长度扩充到，长度不够的地方补充0，以下令

考虑该算法的矩阵形式 求点值的过程为线性变换，矩阵A为范德蒙德矩阵，可分为若干个初等矩阵扩充为n阶方阵后运算得到，并不影响推导(应该吧)。

考虑该算法的转置，易知 该式可用分治快速求出 令分子为，分母为，则

以上为转置算法的解

接下来考虑原算法，可知与多项式无关，可视为列向量，对应转置算法为

1. 线段树预处理数组
2. 由转置原理的第三条和多项式乘法的转置可知自顶向下求解，顶部求出
3. 由转置算法中分子的运算过程可得原算法的逆过程：
4. 叶子节点即为答案

该算法常数小且易于实现，难点在于高强度悟道

这篇博客中有很多东西并没有讲清楚，许多细节以笔者的水平难以表达出来，同时笔者对线代的理解非常浅显，暂时先写成这样

以下是笔者写的递归代码

const int N = 100005;
int n, m, k;
poly mulT(const poly &a)
{
    if (a.empty())return poly();
    return (T * a.rev()) >> (a.size() - 1);
}
poly a, F;
poly c[N << 2], h[N << 2];
int len;

void build(int l, int r, int k)
{
    if (l == r)c[k] = poly{1, mod - a[l]};
    else
    {
        int m = (l + r) >> 1;
        build(l, m, k << 1);
        build(m + 1, r, k << 1 | 1);
        c[k] = c[k << 1] * c[k << 1 | 1];
    }
}

void solve(int l, int r, int k)
{
    if (l == r)return;
    else
    {
        int m = (l + r) >> 1;
        h[k << 1] = h[k].mulT(c[k << 1 | 1]).modxk(m - l + 1);
        h[k << 1 | 1] = h[k].mulT(c[k << 1]).modxk(r - m);
        solve(l, m, k << 1);
        solve(m + 1, r, k << 1 | 1);
    }
}

void print(int l, int r, int k)
{
    if (l == r)
    {
        if (l < m)
            printf("%lld\n", h[k][0]);
    }
    else
    {
        int m = (l + r) >> 1;
        print(l, m, k << 1);
        print(m + 1, r, k << 1 | 1);
    }
}

int main()
{
    int p, q, u, v, x, y, z, T;
    cin >> n >> m;
    F.resize(n + 1);
    for (int i = 0; i <= n; i++)
        scanf("%lld", &F[i]);
    a.resize(m);
    for (int i = 0; i < m; i++)
        scanf("%d", &a[i]);
    len = max(n + 1, m);
    F.resize(len), a.resize(len);
    build(0, len - 1, 1);
    h[1] = F.mulT(c[1].inv(len));
    solve(0, len - 1, 1);
    print(0, len - 1, 1);
    return 0;
}