快速数列变换这个词怎么造出来的

· · 算法·理论

在观察到 数列幂级数，快速数列变换(Fast Array Transform)及其特化 - 洛谷专栏 从 cnblogs 到 luogu 之后，作者迫不及待的准备了这份合订本（意味着这篇会出现一些链接）以对这份看起来不是很牛的文章进行评价。此前 u 群的部分聊天记录可能是这篇出现的伏笔。

感兴趣的还可以尝试拓展阅读 Convolution, In the Perspective of 3-Dimensional Tensors - Codeforces 和 2025 年集训队论文《浅谈张量及其在 OI 的运用》。

对于一些细节层面的内容等到有空的时候会继续补充。

前言：时间线

我所知道的关于最早的 FWT 的构造探索可能是 command_block 等（位运算卷积(FWT) & 集合幂级数 - 洛谷专栏）的。

总之，之后是出现了一大堆同类文章，但是都毫无意外的出现 c_t(i,j)c_t(i,k)=c_t(i,j\oplus k)。

而这种构造方式难以解释 GYM102129A Tritwise Mex 这一道题，甚至很难用来解题，因为不直观，适用范围很有限。即使如此，甚至还是被沿用下来。

在该题的题解引入了张量分析，虽然是扩展了适用范围，但是介绍不太全面。

直到在今年的 12 月 31 日所发出的 CF blog（见上）和 12 月 23 日提交，不知道什么时候传出来的的集训队论文共同抛弃了 command_block 系列的 c_t(i,j)c_t(i,k)=c_t(i,j\oplus k)，转而使用更一般、也更加普遍的张量分析。

虽然性质还是比较奇怪，但是对限制做一些人性化能够比上文更容易地解题。

但是仍然存在大量题解使用 c_t(i,j)c_t(i,k)=c_t(i,j\oplus k) 的形式。

在 u 群出现数列幂级数后，已经有对于这个限制的讨论。

但数列幂级数出现在了算法·理论里。

所以是时候来一篇对于目前我已知的、使用另一种方法的文章的合订本，来和其“对冲”了。

FMT 和高维前缀和

这部分可以不阅读，如果理解两者的关系的话。

对于求 b_S=\sum_{T\subseteq S}a_S，我们可以使用高维前缀和解决。正确性这里不说明。

对于 c_U=\sum_{S\cup T=U}a_Sb_T，我们有 S\cup T\subset eq UU\Leftrightarrow S,T\subseteq U。所以：

\sum_{S\subseteq U}c_U=\sum_{S\cup T\subseteq U}a_Sb_T=(\sum_{S\subseteq U} a_S)(\sum_{T\subseteq U} b_T)

可以使用高维前缀和，按位相乘，高维差分得出 c。

事实上，\operatorname{FMT}(a)_S=\sum_{T\subseteq S}a_S 就是高维前缀和。

FWT 以及一个不是很牛的扩展

参考：位运算卷积(FWT) & 集合幂级数 - 洛谷专栏，或者大量同类型的文章。

我们拿出高维前缀和的代码：

for(int i=0;i<n;++i)
    for(int j=0;j<(1<<n);++j)
        if(!(j>>i&1))A[j|(1<<i)]+=A[j];

考虑拓展到 i\oplus j，其中 \oplus 是位运算。

可以发现，每次是对 A[j|(1<<i)] 和 A[j] 做一个线性变换。而如果只考虑一维的情况，这个线性变换明显是前缀和。

由于过程中全是线性操作，所以设结果为 B，则 B_i=\sum_j c(i,j)A_j。而且能够发现，第 i 次循环，如果 x 能够贡献到 y，那么两者只有第 i 位可能不同。

于是我们可以让 c(i,j) 变得位运算起来，具体来说，c(i,j)=\prod_t c_t((i)_t,(j)_t)，其中 (i)_t 表示 i 的 B 进制（这里 B=2）第 t 位。

模拟 A_i\to B_j 的过程中可以注意到 c_t([0,B-1],[0,B-1]) 实际上可以代表最内层的线性变换，例如在上述的高维前缀和中，我们有和前缀和转移矩阵高度相似的：

c_t=\begin{pmatrix}1&1\\0&1\end{pmatrix}

依据原文的分析，我们需要有 c_t(i,j)c_t(i,k)=c_t(i,j\oplus k)。可以通过真值表求出满足要求的 c_t([0,B-1],[0,B-1])。

对于 \operatorname{FWT}，我们可以构造适当的 c_t 使得满足上述条件，那么我们就有（* 是异或卷积）

\operatorname{FWT}(A)\operatorname{FWT}(B)=\operatorname{FWT}(A*B)

我们只需要对 c_t 取个逆元就可以获得 \operatorname{IFWT} 了。

上述的分析过程和代码都可以选择一篇讲解 FWT 的文章来查看。

注意到先前所给出的约束：c_t(i,j)c_t(i,k)=c_t(i,j\oplus k)，在绝大部分（可能是除了作者以外任意一人发表的题解）如果探究 FWT 的构造，几乎全部出现此约束。

作者尚未弄清楚这种情况的出现，因为已经存在此方法无法解决的题目。

CF GYM102129A Tritwise Mex

求 C_k=\sum_{\operatorname{mex}_3(i,j)=k}A_iB_j。

如果上面的构造方法成立，我们应该给出 O(3^nn) 的做法，但是这题基本不可能。

当然存在一些题解使用硬凑的方式，把输入输出改造成 4^n 大小。但是这样的复杂度是 O(4^nn) 的，也不优秀。

事实上我们可以使用分治乘法。这种做法的具体定义和一些技巧见 巨大多我们 - 洛谷专栏。

这里再次给出定义：

按照最高位划分出 A_0,A_1,A_2 和 B_0,B_1,B_2。

所以 $a_ib_j\to c_k$ 的贡献可以被拆成每一位。同时这里题目定义的“卷积” $$W(A,B)=\sum_{i\mathop{\mathrm{op}}j=x}A_iB_j$$ $W$ 对于 $A$ 或者 $B$ 是线性的（双线性）。因此有乘法分配律 $W(kA+B,C)=k W(A,C)+W(B,C)$，$W(A,kB+C)=k W(A,B)+W(A,C)$。 因为调用乘法，我们需要构造若干个 $D_i=W(\sum x_{i,j}A_j, \sum y_{i,j}B_j)$。这里有 $r$ 个。 最后我们要求 $C_k=\sum_{\text{op}_{i,j}=k}W(A_i,B_j)$，需要可以用 $D_i$ 加减表示。 在接下来的题目中，我们默认 $A_i,B_j$ 是一个变量，这样 $W(A_i,B_j)=A_iB_j$。但不影响推广。 关于时间复杂度分析：$T(n)=rT(n-1)+O(3^n)=O(\max\{r^n,3^nn\})$，当 $r\ge 3$ 的时候。

之后可以类似这样的人类智慧的凑。【题解】GYM-102129A-Tritwise Mex | Zerol's Notes。

可以发现，这种构造天然支持任意位运算操作。但注意，这里的算法实现依赖于分治乘法，而不是传统的变换-逆变换形式。

但中间的转移矩阵其实本质相同，并且整个算法形式可以自然转换到 变换-逆变换 形式，可以参考 P4717 题解 - 洛谷专栏 中的内容。

说了这么多还没有考虑限制条件。

考虑 a_ib_j\to c_k，其贡献是 [\text{op}_{i,j}=k]。

设最后 C_k=\sum z_{i,k}D_i。

这个算法贡献是 \sum_t x_{t,i}y_{t,j}z_{t,k}，应该等于 [\text{op}_{i,j}=k]。

对于这个限制的人性化处理可以参考 巨大多我们 - 洛谷专栏 里提到的表示方式。

这个限制是几乎充要的，其看上去能够支持任何位运算卷积的构造（除了子集卷积以外都是显然的，后面会拓展让其进一步支持子集卷积）。

张量 CP 分解求张量秩上界的乱搞 巨大多我们 - 洛谷专栏 里提到一点，对于特定张量分解的乱搞存在一些研究者在整 (Kauers-Moosbauer) 等，当然最近的 AI 优化矩阵乘法本质也是在搞这坨。

熟悉张量的都知道，这东西是张量 CP 分解道理，而求张量秩（最小的 r）是一件非常困难的事情，所以这东西多半只能靠人类智慧或者乱搞。

张量的概念在任意一个分治乘法，复杂度和乘法次数有关的分治算法中几乎能够用上，例如矩阵乘法和多项式乘法（Karatsuba 及其引申）。

子 集 卷 积

在几乎所有的题解（这里应该能几乎完全断定除作者以外的所有题解），子集卷积使用 FMT 加上一个看似割裂的占位多项式来获得操作。

事实上，这部分和张量的边界秩有关。

一种详细介绍如何将占位多项式揉到 FMT 的结构内见 P6097 题解 - 洛谷专栏，这篇题解由于题解区满了暂时没法加入。

进一步？

注意到我们的分析中，最后的限制 \sum_t x_{t,i}y_{t,j}z_{t,k}=[\text{op}_{i,j}=k]，这个形式高度一致，但是 x,y 依赖输入，z 依赖输出。

这启发我们输入输出本质是一致的，可以交换。

实际上，根据 Convolution, In the Perspective of 3-Dimensional Tensors - Codeforces 中的 Baur-Strassen's Algorithm 可以解释。但是其实这是极其容易理解的，根本不需要感受。

这里可以干一些有趣的事情，比如 c_k=\sum_{j|k=i}a_ib_j 这个 USACO 的弱化版本，可以对输入输出进行“旋转”照样获得 O(2^nn) 的结果，可以将这个对应的张量仅通过交换坐标得到 OR 运算所代表的张量，进而还原出来 x,y,z。

具体使用场景：题解：P11458 [USACO24DEC] All Pairs Similarity P | 进行一个转 - 洛谷专栏

如何严格包含快速数列变换的运用场景

对于位运算 F_1\times F_2\times\cdots\times F_k，其中 F_i: (S_i,S_i)\to S_i，中间使用笛卡尔积。

我们递归调用 F_1\times F_2\times\cdots\times F_{k-1}，把最后一个拆开。则该层循环需要能够用尽可能少的乘法模拟出 F_k。这是张量分解道理。

注意到快速数列变换只能支持使用 |S_i| 次乘法，非常的屑。

对于子集卷积，我们有更好的方法能够规避额外加的“占位多项式”。或者说将占位多项式嵌入位运算卷积中更好。

对于快速 GCD/LCM 变换。只给你一维显然是会做的，直接将一维对应的 x,y,z 套到多维度即可。

这里提到的迪利克雷前缀和 / 差分主要目的是优化 \sum x_{i,j}A_j 这个特殊矩阵乘法（线性变换）的计算过程。

一个小东西

对于特征为 2 的域计算异或卷积（FWT）。这里特征为二指的是 x+x=0。

这种情况无法使用普通的 FWT 算法（因为有\frac 12）。

但是我们仍然可以尝试摸索边界秩，利用 (1+c)^2=1+c^2 和 c=-c 这两比较特殊的限制可以做到一些好玩的东西，比如我们可以只考虑系数 0,1。

具体来说可以假设这个是必须的：

d_0=W(a_0+a_1,b_0+b_1),d_1=W(a_0+ca_1,b_0+cb_1)

我们只有一个 d_1 的构造空间，因为 0,1 在异或下等价，可以尝试：

d'_1=W(a_0+a_1x,b_0+b_1x)=W(a_0,a_1)+(W(a_0,b_1)+W(a_1,b_0))x+W(a_1,b_1)x^2

但是这样应该是啥作用没有，需要修改 d_1 定义，我们呢感受那股劲下：

d_1=W(a_0x+(a_0+a_1),b_0x+(b_0+b_1))=d_0+(W(a_1,b_0)+W(a_0,b_1))x

中间用了 x+x=0 的消除。

c_1=\frac{d_1-d_0}{x},c_0=d_0-c_1

注意 \frac 1x 实际上没什么事，可以转化成 c_0x=d_1-d_0 然后形如子集卷积那样处理 / 搓出来 Xx^k+o(x^k)（如果你知道这个是什么意思的话）。

于是得到解决，时间复杂度 O(2^nn^2)。

我宣称这题用程序爆搜都能出来这个构造。原因前面说过了。

言简意赅的总结

综上所述，数列幂级数显然是张量分解的特化，别再 c_t(i,j)c_t(i,k)=c_t(i,j\oplus k) 了。

倒挺想知道那么多题解都写这东西究竟有多少人在用它，感觉一用一个不吱声。