算法基础（一）：转置原理
Satella
·
·
算法·理论
转置原理的定义
我们知道一个 n\times m 的矩阵 M 的转置，为其沿主对角线翻转的 m\times n 的矩阵 M^T。
假设你现在有一个 n 阶向量 X 和一个 n\times m 的矩阵 M。
你现在知道 X，希望求出 XM，且求出 M 相对困难或时间复杂度较高。
此时如果你能快速求出 M^T，则将其转置回来后就能得到 M，从而求出 XM。
这样求解原问题的方法就叫做转置原理。
如何转置
为了解决原问题 XM，我们思考一个新问题：YM^T，假设你已经知道 Y 并希望求 YM^T。
如果对于这个问题，你能相对容易地得到 M^T，则将其转置即可得到 M。
例如：
你现在有 n 个变量 X_1,X_2,\dots,X_n 和 n 个集合 S_1,S_2,\dots,S_n\subseteq \{1,2,\dots,m\}。
你需要对每个 i=1,2,\dots,m 求
\sum_{i\in S_j}X_j
直接做要对于 i=1,2,\dots,n，枚举 j\in[1,n]，遍历 S_j 判断 i 是否属于 S _ j，时间复杂度 \text O(n^3)。
这道题存在时间复杂度较低的做法（主动转移），但我们转置之后其实和那本质相同：
你现在有 m 个变量 Y_1,Y_2,\dots,Y_m 和 n 个集合 S_1,S_2,\dots,S_n\subseteq \{1,2,\dots,m\}。
你需要对于每个 i=1,2,\dots,n 求
\sum_{j\in S_i}Y_j
这简直就是把做法写脸上了。直接对于 i=1,2,\dots,n，遍历 S_i 中的每个元素 j，对 Y_j 求和即可。
写成矩阵形式，就是 j 对 i 有贡献当且仅当 j\in S_i，故
M^T_{j,i}=[j\in S_i]
转置后即得到 M，便可求出 XM。时间复杂度 \text O(n^2)。
加速矩阵的构造与转置
为方便，下文中常量统一用花体字母 \mathcal{ABC} 表示。
我们发现上述算法还是没什么用，当然是因为不够快速。
矩阵的转置有这么一个公式：
(M_1 M_2\cdots M_k)^T=M^T_k M^T_{k-1}\cdots M^T_1
其实这很好理解，就是贡献路径从 i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_k 转置后变成 i_k\rightarrow i_{k-1}\rightarrow\cdots\rightarrow i_1。
也就是说，我们在转置矩阵的时候，不一定要把 M^T 整个求出来。如果我们知道
M^T=M^T_k M^T_{k-1}\cdots M^T_1
那么根据结合律，
XM=XM_1 M_2\cdots M_k
此外，我们有这么两种方便转置的 M_i 矩阵：
-
\mathcal{A}X\rightarrow Y 转置为 \mathcal{A}Y\rightarrow X：
令 M^T_i 表示变换 \mathcal{A}X\rightarrow Y。
转置前 M^T_i 相当于一个 (X,Y) 位置为 \mathcal{A}、其他位置为 0 的矩阵；
转置后 M_i 变为一个 (Y,X) 位置为 \mathcal{A}，其他位置为 0 的矩阵。
故 M_i 表示变换 \mathcal{A}Y\rightarrow X。
-
B\otimes\mathcal{A}\rightarrow C 转置为 C\ominus\mathcal{A}\rightarrow B，其中 \mathcal{A},B,C 为多项式，\otimes 为加卷积，\ominus 为减卷积：
令 M^T_i 表示变换 B\otimes\mathcal{A}\rightarrow C。
转置前 M^T_i 相当于 \forall u,v，(B_u,C_{u+v}) 位置为 \mathcal{A}_{v}、其他位置为 0 的矩阵；
转置后 M_i 相当于 \forall u,v，(C_u,B_{u-v}) 位置为 \mathcal{A}_v、其他位置为 0 的矩阵。
故 M_i 表示变换 C\ominus\mathcal{A}\rightarrow B。
可能还有更多，但如果你理解了以上两种，其他的理应也不难变换。
回到上文可以发现，如果我们思考转置问题时，对 Y 分别进行了若干次可以归结为矩阵乘的操作，那么原问题就是倒序对 X 进行若干次对应转置矩阵乘的操作。
注意，在多次矩阵乘法之间是允许有中间变量的。
例题 1
我们令 X=(1,2,\dots,n)，X_i 表示“最大值为 i”的权重。
另设矩阵 M，M_{i,j} 表示“最大值为 i”对“包含 j”的贡献次数，答案即为 XM。
考虑到 M 不方便求解，我们转而去求 M^T。
试想一个问题：若虚拟一组权值 Y，Y_i 表示“包含 i”的权重，现要求 YM^T。由于一个独立集中每个点的 Y_i 都会贡献一遍，故 (YM^T)_i 的含义是“最大值为 i 的独立集中每个点的权值和之和”。
把“最大值为 i”转成“最大值 \le i”，然后可以用动态 dp 更新出每个 i 的答案。
注意到动态 dp 实质上只有矩阵乘操作，我们封装这些操作的转置矩阵。
然后代入原问题的权值 X，倒序对 X 进行乘法即可求出答案。
例题 2
令多项式
F_k(x)=\prod_{j=1}^k(x+B_j)
对于 k=1,2,\dots,N 通过变形容易得到
\sum_{j=0}^k[x^j]F_k(x)\sum_{i=1}^NC_iA_i^j
记 G_{j}=\sum_{i=1}^NC_iA_i^j，我们这么一个多项式
\begin{align*}G(x)&=\sum_{n=0}x^n\sum_{i=1}^NC_iA_i^n\\&=\sum_{i=1}^N{C_i\over 1-A_ix}\end{align*}
可以分治时维护分数形式求解，最后再求逆得到 G(x)\bmod x^{N+1}，然后提取各项系数即得到 G_j。
现在目标变成了
\sum_{j=0}^kG_j[x^j]F_k(x)
为了方便提取系数，我们考虑其转置问题：
假设给你一组 H，你要对于 j=0,1,\dots,n 求
[x^j]\sum_{k=1}^NH_kF_k(x)
同样提取系数，直接把 F_k(x) 展开后提取公因式 \prod_{l\le i\le mid}(x+B_i) 然后分治。
推一下用了哪些卷积，并处理出每个区间的 \prod_{l\le i\le r}(x+B_i)，原问题倒序进行转置操作即可求解。
每个部分的时间复杂度都是 O(n\log^2n)。
变种：非线性变换
我们考虑 \{X\}_n 通过某种变换得到 \{Y\}_m，其中
Y_i=\sum_{S\in\mathfrak{T_i}}\mathcal{C}(i,S)\prod_{j\in S}X_j
其中 \mathfrak{T}_i 为集族，\mathcal{C} 为关于 (i,S) 的函数。
我们已知 X，对于每个 X_j，想要知道其对 Y 贡献次数，即
\sum_i\sum_{S\in\mathfrak{T}_i,j\in S}\mathcal{C}(i,S)\prod_{j\in S\setminus\{i\}}X_j
由于这不是线性变换，故无法用矩阵来表示。不过转置原理依然适用，主要有两种方法：
法一：计算贡献次数
不妨设 n,m 同阶。
对于正过程，我们先求出 Y 和所有中间变量，假设这部分时间复杂度为 \text O(T(n))；
根据定义，不妨假设 Y_i 之间没有转移，则现在我们知道每个 Y_i 的贡献次数为 1。
对于逆过程，我们倒着跑一遍正过程，如果发生以下转移：
-
-
这里，我们 $\mathcal{X}_j$ 为我们在正过程已经算过的部分。
根据定义，上述过程其实比较好理解：因为 $X_i$ 的贡献次数在正过程中这个转移“扩大”了 $\mathcal{A}\prod_{1\le j\le k,j\neq i}\mathcal{X}_j\rightarrow X_i$ 倍，所以在逆过程时，它的贡献次数就是 $Y$ 乘上这么多倍。
最后求出的每个 X_i 就是其贡献次数，不难发现这部分时间复杂度也为 \text O(T(n))。
注意：正过程和逆过程是不同的变量（数组）！
法二：代数原理
首先跑一遍正过程，我们考虑对每个 X_j 单独处理答案。
我们可以把 X 中除了 X_j 以外的变量都视为 \mathcal{X}，此时正过程变成了线性变换，可以倒着跑转置操作。
上述算法的时间复杂度是 \text O(nT(n)) 的，但我们发现有些部分其实很浪费。
比如一个状态 G 的贡献非零的所有 X_j 的 j 构成集合 S_G，则由于这个状态后面不会和 S_G\cap S_H\neq\empty 的状态 H 合并（否则就会有 X_j 次数大于 1）。
于是这时候我们可以只把 S_G 的补集中的元素 j' 视为常数 \mathcal{X_{j'}}，这样它对于所有 j\in S_G 的 j 跑转置都是对的，对于 j\not\in S_G 的 j 无关紧要。
所以可以像法一全体跑一遍，详见法一。时间复杂度 \text O(T(n))。
例题 3
有点忘了，但从一个节点推到其子节点时就差不多可以转化成这个。
由于是特殊情形，也可以使用多项式除法。两者复杂度相同。
例题 4
主旋律加上这个就可以。