正如 EI 所言啊，转置原理不是无中生有创造算法，而是建立了一些问题之间的转化机制。
问题形式：
考虑一个 \(n\times m\) 的矩阵 \(A\)，我们有一个算法：输入长度为 \(m\) 的向量 \(b\)，可以利用这个算法得到 \(A\times b\) 的结果：一个长度为 \(n\) 的向量 \(a\)。
如果在这个算法过程中，对输入的修改都是线性修改，那么转置原理断言：存在一个复杂度相同的算法，使得，输入长度为 \(n\) 的向量 \(a\)，可以得到 \(A^{T}\times a\) 的结果：一个长度为 \(m\) 的向量 \(b\)。
需要注意是，这个东西，并不是反解方程的结果。意思是，你用原算法得到了一个 \(a\)，然后将这个 \(a\) 作为输入放进转置问题的算法里，那么你得到的 \(b\) 并不是原来你输入的 \(b\) 啊。
解决方案
考虑所有和输入有关的项，其它项就都应该成为常数项：换言之它们在输入之前就应该预先处理完毕。
此时原问题的每一步骤，都应该是对输入的线性修改。
因为是线性修改，所以可以看成，将输入数据左乘上了一个矩阵。
换言之 \(A\times b\) 应该可以分解成 \(A_k\times ... \times A_1 b\)，每一个 \(A_i\) 都对应了算法流程中的一个操作。
我们知道 \(A^T=A_1^T\times ... \times A_k^T\)，而每一个 \(A_i\) 本质上，是对输入数据的一些操作。
那么你倒着做原算法的操作，并且每一步操作，都“做原操作的转置”，就可以得到答案。
什么叫做原操作的转置？我们举一些例子（事实上转置原理这部分，你都可以把操作写成矩阵形式，然后把矩阵转置一下就行）。
- 例如：\(a_i\leftarrow a_i + c\times a_j\)。
写成矩阵的形式：
\[\left[ \begin{array}{ll} 1 & c \\ 0 & 1 \end{array} \right] \times \left[ \begin{array}{ll} a_i \\ a_j \end{array} \right] = \left[ \begin{array}{ll} a_i+c\times a_j \\ a_j \end{array} \right] \]然后把最左边的 \(2\times 2\) 矩阵转置，重新做乘法，就得到：\(a_j\leftarrow c\times a_i+a_j\)。
那你就得到了 \(a_i\leftarrow a_i+c\times a_j\) 这个操作对应的转置。
卷积不是线性的，但是如果两个相乘的数组，一个是确定的，那么就可以认为是线性的。从线性代数的角度来看，无非就是：
\[\left[ \begin{array}{ll} c_0 & 0 & 0 & 0 \\ c_1 & c_0 & 0 & 0 \\ c_2 & c_1 & c_0 & 0 \\ c_3 & c_2 & c_1 & c_0 \end{array} \right] \times \left[ \begin{array}{ll} b_0 \\ b_1 \\ b_2 \\ b_3 \end{array} \right] = \left[ \begin{array}{ll} a_0 \\ a_1 \\ a_2 \\ a_3 \end{array} \right] \]这个乘法等价于卷积：\(a_i=\sum_{j\le i}b_j\times c_{i-j}\)。
\[\left[ \begin{array}{ll} c_0 & c_1 & c_2 & c_3 \\ 0 & c_0 & c_1 & c_2 \\ 0 & 0 & c_0 & c_1 \\ 0 & 0 & 0 & c_0 \end{array} \right] \times \left[ \begin{array}{ll} a_0 \\ a_1 \\ a_2 \\ a_3 \end{array} \right] = \left[ \begin{array}{ll} b_0 \\ b_1 \\ b_2 \\ b_3 \end{array} \right] \]这个运算就等价于 \(b_i=\sum_{j\ge i}c_{j-i}\times a_j\)。
我们发现和卷积的转置就是我们也很熟悉的差卷积的形式。
我们一般把这里的矩阵记作 \(mul(c)\)，其转置就是 \(mulT(c)\)
经典应用：多项式多点求值
咕咕。
标签：right,end,转置,ll,笔记,times,原理,array From： https://www.cnblogs.com/Cry-For-theMoon/p/16771931.html