[学习笔记]转置原理 (Draft)

在分治FFT求 \( \Pi_{j} (1 - a_jy) \) 的时候，由于递归到底的时候要为 \( 1 - a_jy \) 留两个位置，所以最终会导致求出来的数组是 tot 级别的，而实际上 \( \Pi_{j} (1 - a_jy) \) 是 \( \frac{tot}{2} \) 级别的，造成了浪费，而且感觉不太优美

答：看了一份题解的代码，貌似也没有对这方面的处理，那也就只能这样写了。

鸡贼课件里说所谓 “转置原理” 就是 \( f(x) \times g(x) \cdot h(x) \Leftrightarrow g(x) \cdot h(x) \times f(\frac{1}{x}) \) ，但这个下标问题有点迷，还得推一下

关于鸡贼写的那个\( f(x) \times g(x) \cdot h(x) \Leftrightarrow g(x) \cdot h(x) \times f(\frac{1}{x}) \)，如果直接按这种形式写的话貌似会扯到循环卷积，就比较烦。 目前我只知道如果把 \( f(\frac{1}{x}) \) 直接看做 \(f_r(x)\) （对前 \( 0 \sim n - 1 \) 项翻转）的话，可以把点积转化为卷积的 \( x^{n-1} \) 项系数，不知道其他用法会不会对这个翻转的要求不一样。

upd: 推了一波式子，并实验了一波，得到结论其实是 \( A(x)B(x) \cdot C(x) = Ar(x) \cdot B(x)Cr(x) = Br(x) \cdot A(x)Cr(x) = A(x) \cdot (B(x)Cr(x))r \) 注意 ： 不是 \(Ar(x) \cdot Br(x)C(x)\)，究其原因在于进行减法卷积时，若将两个多项式互换，最终得到的结果会不一样。

但对于 \(A(x)B(x) \cdot C(x)D(x)\) 这种形式除了先把 \(C,D\) 卷起来之外暂时没想到什么更好的方法，因为要扯到减法卷积。

突然感觉鸡贼写的有点nb，居然能把转置抽象成一个纯多项式的东西？ 如果能把多项式操作和矩阵变换联系起来，估计就比较好理解了。 点积好像还行，但卷积怎么转化为矩阵？

一个 \( n \times n \) 常数矩阵 \(A\) 左乘一个 \( n \times 1 \) 的变量向量 \( a\)，得到 \( b \) 的算法

对于线性算法 \( b = Aa \)，称 \( b' = A^Ta \) 为它的转置算法。（ \(A^T\) 表示矩阵 \(A\) 的转置，就是沿主对角线翻转）

其实我感觉把向量换成矩阵也成立

定理： 设 \( A = E_1 E_2 E_3 \cdots E_k \) 则 \( A^T = E_k^T E_{k-1}^T E_{k-2}^T \cdots E_1^T \) 其中 \(E\) 为初等矩阵

然后如果你把矩乘换回普通操作（就是普通 C++ 语句），就相当于把所有操作反着做一遍，什么参数传入改为返回，函数调用顺序反过来…… 有种看 信条 的感觉

5-2 复合 简单函数 4 没看懂

一元函数的复合可以用复合的结合律简化运算 但二元函数怎么办？

二元函数 \( F(x,y) \) 左乘一个向量 \( b(y) \)，\( y^i \) 没有什么实际意义，只是相当于建立了一个对应关系，从而得到每一个 \( x^i \) 的系数。而复合函数 \( q'(sp(y)) \) 也是建立了一个对应关系，如果我们把复合函数的对应关系一层层扒下来，那么就可以简化运算。

设我们现在要求 \( f(p(x)q(y)) \cdot b(y) \)，然后 \( q(y) \) 能写成 \(q'(sp(y))\) 的形式，其中 \( sp(y) \) 是一个简单函数。 我们考虑把 \(b(y)\) 换个基，变成 \(b'(sp(y))\)，然后就相当于把 \(sp(y)\) 扒出来了。 考虑如何求 \(b'\)。 设 \(sp^{-1}(y)\) 为 \(sp(y)\) 的复合逆，设 \(t = sp(y)\)， 则 \(y = sp^{-1}(sp(y)) = sp^{-1}(t) \)， 那么把 \(y = sp^{-1}(t)\) 带入 \(b(y)\) 就可以得到 \(b(y) = b(sp^{-1}(t))\)，所以 \(b'(sp(y)) = b'(t) = b(sp^{-1}(t)) \)，也即 \(b' = b \circ sp^{-1}\)。

所以原式就可以变为 \(f(p(x)q'(t)) \cdot b'(t) \)，然后再把 \(q'(t)\) 一层一层按照上面的过程拆下去，直到得到一个 \(q'_{final}(z) = z\)， 那么原式为 \(f(p(x)q'_{final}(z)) \cdot b''(z) \)， 展开后就是

\( \begin{aligned} f(p(x)q'_{final}(z)) \cdot b''(z) &= (\sum_{i} f_i p(x)^i z^i) \cdot (\sum_{i}b''_{i} z^i) \\ &= \sum_{i} f_i b''_{i}p(x)^i z^i \\ \end{aligned} \) 所以可以先把 \(f\) 和 \(b''\) 点积起来，设 \(f'(t) = f(t) \cdot b(t) \)，之后的操作就是 \( f' \circ p \)，然后由于 \(p\) 又是由若干个简单函数复合而成，所以可以根据复合的结合律来一层层复合。

回到更普通的形式，即 \(u(x)v(y)f(p(x)q(y)) \cdot b(y) \)， 对于 \(v(y)\)，我们使用 \(A(x)B(x) \cdot C(x) = A(x) \cdot (B(x)Cr(x))r\) 的技巧，先把 \(v(y)\) 挪到右边，然后就变为了 \(u(x)v(y)f(p(x)q(y)) \cdot b'(y) \)， 接着再按照上面的步骤，最后得到 \(u(x)(\sum_{i} f_i b''_{i}p(x)^i z^i)\)，那么就先把后面那项求出来，然后再卷一次就OK了

尝试用转置方法写了发DFT，为啥转置后跑得飞快啊？？？ UOJ上普通写法总时间2000ms左右，转置写法只要不到700ms。。。 感觉运算量没差吧？？？？？

但为啥洛谷上又没啥差别。。。。

结果只是刚刚UOJ抽风了。。。。

由于转置方法是分治算完后二进制翻转，而原方法是分治算之前二进制翻转，所以如果你DFT用转置方法，IDFT用原方法，就可以少两个二进制翻转的过程，稍微能快那么一丢丢。