转置原理
analysis
·
·
算法·理论
不会写正经的伪代码，所以可能有点鬼畜。
概述
转置原理是给出通过问题 b=Aa 的算法解决问题 b'=A^{T}a' 的一种方法。
具体来说，我们先将 A 分解为若干容易翻译（即容易得到转置操作）的操作，即 A=A_{m}A_{m-1} \cdots A_{1}。
根据矩阵转置的相关信息，我们可以得到 A^T=A_{1}^{T} \cdots A_{m-1}^{T}A_{m}^{T}。
也即，我们只要把原来问题（b=Aa）的算法倒过来，执行转置操作，就可以解决新的问题（b'=A^{T}a'）。
常见操作的转置操作
无特殊说明，以下内容 a、b 为变量，c 为常量。
将这个操作翻译为矩阵形式，即：
\begin{bmatrix}1 & 0 \\ c & 1\end{bmatrix}\begin{bmatrix}a \\ b\end{bmatrix}=\begin{bmatrix}a \\ ac+b\end{bmatrix}
于是其转置操作即为：
\begin{bmatrix}1 & c \\ 0 & 1\end{bmatrix}\begin{bmatrix}a \\ b\end{bmatrix}=\begin{bmatrix}a+bc \\ b\end{bmatrix}
即 a \leftarrow a+cb
这个变换是一个 1 \times 1 的矩阵，转置后不变。
与 $a \leftarrow ca$ 不同的是，它是一段内存整体的操作，所以不能直接套用以上的操作。
可以先将三个多项式的大小统一一下。记 $n$ 为次数。
然后仍然考虑写为矩阵形式，我们可以对 $B$ 构造一个矩阵 $M$ 使得 $C=MA$。可以得出：
$$
M=\begin{bmatrix}
B_0 & 0 & 0 & \cdots \\
B_1 & B_0 & 0 & \cdots\\
B_2 & B_1 & B_0 & \cdots\\
\vdots & \vdots & \vdots & \ddots
\end{bmatrix}
$$
我们去考虑他的转置，即：
$$
M=\begin{bmatrix}
B_0 & B_1 & B_2 & \cdots \\
0 & B_0 & B_1 & \cdots\\
0 & 0 & B_0 & \cdots\\
\vdots & \vdots & \vdots & \ddots
\end{bmatrix}
$$
那么：$C_k=\sum_{i=0}^{n}B_{i-k}A_i$。
考虑记 $E_i=B_{n-i}$，则 $C_k=\sum_{i=0}^{n}E_{n+k-i}A_i=\sum_{i=0}^{n+k}E_{n+k-i}A_i$。
也就是，我们将 $B$ 反转再与 $A$ 做乘法，最后左移 $n$ 位，截取即可。
参考实现：
```cpp
poly mulT(poly f,poly h){
int n=(int)f.size();
f.resize(n),h.resize(n);reverse(h.begin(),h.end());h=mul(f,h);
for(int i=0;i<n;i++)f[i]=h[i+(n-1)];
return f;
}
```
ps：为了方便，此后多项式乘法的转置记为 $\times^{T}$。
upd：事实上，我们可以从 DFT 的角度考虑多项式乘法。我们知道 IDFT 可以拆成一次 DFT、一次数乘以及一次逆序。所以多项式乘法就是 DFT、点乘、DFT、数乘、逆序。
我们知道 DFT 转置后不变，逆序是副对角线，转置后不变，点乘和数乘都是主对角线也不变，所以转置算法就是 逆序、数乘、DFT、点乘、DFT。
### 应用
#### 多项式多点求值
[题目](https://www.luogu.com.cn/problem/P5050)
假设给出的多项式为 $\sum_{i=0}^{n} a_ix^{i}$，需要求得点值为 $\{x_i|0 \leq i \leq n\}$。
设矩阵 $M$ 有 $M_{ij}=x_i^j$，向量 $A$ 有 $A_i=a_i$，问题即为：
$$
\begin{bmatrix}1 & 0 \\ M & 1\end{bmatrix}
\begin{bmatrix}A \\ D\end{bmatrix}
=\begin{bmatrix}A \\ D+MA\end{bmatrix}
$$
考虑其转置问题：
$$
\begin{bmatrix}1 & M^{T} \\ 0 & 1\end{bmatrix}
\begin{bmatrix}A \\ D\end{bmatrix}
=\begin{bmatrix}A+M^{T}D \\ D\end{bmatrix}
$$
于是我们要考虑的就是 $A=M^{T}D$ 了，用人话说就是 $A_k=\sum_{i=0}^{n}M^{T}_{k,i}D_i=\sum_{i=0}^{n}M_{i,k}D_i=\sum_{i=0}^{n}D_ix_{i}^{k}$。
挂在 GF 上，令 $Q=\sum_{k \geq 0}A_kt^k=\sum_{k \geq 0}\sum_{i=0}^{n}D_i(x_{i}t)^{k}=\sum_{i=0}^{n}\frac{D_i}{1-x_{i}t}$，可以分治乘解决。
于是，我们解决了原问题的转置问题，可以写出其伪代码（注意，常量的计算可以无需体现在算法中）。
以下 $Q_{l,r}=\prod_{i=l}^{r}(1-x_it)$。
```
sol(l,r):
if(l=r):
f[0]=f[0]+D[l]
return f
mid=(l+r)/2
L=sol(l,mid)
R=sol(mid+1,r)
f=f+L*Q[mid+1][r]
f=f+R*Q[l][mid]
A=A+sol(0,n)*inv(Q[0][n])
```
将执行顺序反转，执行转置操作，于是我们可以解决原问题。
```
sol(l,r,f):
if(l=r):
D[l]=D[l]+f[0]
mid=(l+r)/2
sol(l,mid,f (*T) Q[mid+1][r])
sol(mid+1,r,f (*T) Q[l][mid])
sol(0,n,A (*T) inv(Q[0][n]))
```
参考实现：
```cpp
poly Q[N<<2|1];
void init(poly& X,int x,int l,int r){
if(l==r){
Q[x].clear();Q[x].push_back(1);Q[x].push_back((mod-X[l])%mod);
return;
}
int mid=(l+r)>>1;
init(X,x<<1,l,mid);init(X,x<<1|1,mid+1,r);
Q[x]=mul(Q[x<<1],Q[x<<1|1]);
return;
}
void sol(poly F,poly &a,int x,int l,int r){
F.resize(r-l+1);
if(l==r)return void(a[l]=F[0]);
int mid=(l+r)>>1;
sol(mulT(F,Q[x<<1|1]),a,x<<1,l,mid);
sol(mulT(F,Q[x<<1]),a,x<<1|1,mid+1,r);
}
void multipoint(poly A,poly X,poly &v,int n){
A.resize(n);X.resize(n);v.resize(n);
init(X,1,0,n-1);
sol(mulT(A,inv(Q[1],n)),v,1,0,n-1);
}
```
#### 特殊的 XOR FWT
[是这题](https://atcoder.jp/contests/arc133/tasks/arc133_f)
转化一下问题：$N$ 枚硬币,初始时 $i$ 个正面的概率为 $p_i$，每次随机翻一枚，求最后正面朝上硬币个数为 $x$ 的概率。
我们显式的表达这个序列，假设硬币序列的状态为 $S$，其出现概率为 $P_S$。
每一次操作取反一位，可以转化为 XOR 卷积。
如果只是这样的话时间复杂度只能做到 $O(n2^n)$。
但是这题有性质：若 $|i|=|j|$ 则 $P_i=P_j$（$|S|=\operatorname{popcount}(S)$）。
所以记 $g_{|s|}=FWT(P)_s$、$f_{|s|}=P_s$，有：
$$
FWT(P)_s = \sum_{t}(-1)^{|s \cap t|}P_t\\
g_{|s|} = \sum_{t}(-1)^{|s \cap t|}f_{|t|}\\
g_{k}=\sum_{i=1}^{n}f_i[x^i](1-x)^{k}(1+x)^{n-k}
$$
对于这个问题，转置一下即得：
$$
f_k=\sum_{i=1}^{n}g_i[x^k](1-x)^{i}(1+x)^{n-i}
$$
这是容易分治乘解决的，时间复杂度 $O(n\log^{2}{n})$。
于是我们可以直接用 FWT，然后乘起来就好了。
[参考实现](https://www.luogu.com.cn/paste/g3lc7ir8)
ps：刚学完转置原理就随机跳题跳到了，令人忍俊不禁。然鹅看题解发现其实不需要转置。