GitHub 源文件 Markdown English

Grox的序列四：余数值张量变换¶

Codex（GPT-6）：将出题人的对齐方块分解与余数值张量变换结合，直接计算三个分类和。 张量积与多项式商环为通用方法；这里说明它们在本题中的应用。计算程序与分阶段 FWT、逐块 FWT并列，保留全部方案。

只保存需要的三个系数¶

沿用主题解的 \(L,B\) 及对齐方块分解。令

\[ \mathcal R=\mathbb F_P[z]/(z^3-1) \]

环元素只需三个模数余数，分别代表常数项、一次项、二次项。乘以 \(z^w\) 就把三个位置循环移动 \(w\bmod3\) ，不需要寻找三次单位根。

对一种按位运算 \(\circ\) ，所求的三项正是下式在这个环中的系数：

\[ \sum_{i+j\le n}a_i b_j z^{i\circ j} \]

不必先求每个下标的卷积值再分类。

一位的矩阵¶

考虑权值为 \(w=2^h\) 的一位，令 \(q=z^w\) .以左下标的位为行、右下标的位为列，三种运算的权值矩阵为

\[ K_h^{\mathrm{XOR}}=\begin{pmatrix}1&q\\q&1\end{pmatrix},\qquad K_h^{\mathrm{OR}}=\begin{pmatrix}1&q\\q&q\end{pmatrix},\qquad K_h^{\mathrm{AND}}=\begin{pmatrix}1&1\\1&q\end{pmatrix} \]

例如 OR 的两个位只有同时为零时贡献 \(1\) ，另外三种配对均贡献 \(q\) .多个位互相独立，完整矩阵是这些矩阵的张量积。

边长为 \(s=2^d\) 、起点为 \((a,b)\) 的接受方块中，定义

\[ H_d(u)=\sum_{v=0}^{s-1}b_{b+v}z^{u\circ v} \]

从 \(H_0(0)=b_b\) 开始，每加一位，用对应的二元矩阵推进。把全局数组的每个对齐区间一起推进，便能在第 \(d\) 层得到所有长度 \(2^d\) 区间的 \(H_d\) .各分量的计算只有模加法与循环移位。

此时方块贡献为

\[ z^{a\circ b}\sum_{u=0}^{s-1}a_{a+u}H_d(u) \]

算完即累加到三个答案中；不保存跨层结果，也不执行逆变换。三种运算依次进行，只保留一份工作数组。

正确性¶

一位矩阵的每个元素恰为该配对产生的指数权值。张量积把各位权值相乘，得到 \(z^{u\circ v}\) ，所以推进过程准确求出 \(H_d\) .对齐起点的低位为零，高低位独立，乘以 \(z^{a\circ b}\) 即补上高位。接受方块不交且覆盖全部合法数对，累加恰为目标环元素。关系 \(z^3=1\) 将指数归入对应的三个余数类别，因此输出正确。零下标与单点方块直接由初始层处理。

复杂度与取舍¶

每层全局推进花费 \(O(L)\) 时间；接受方块的点积总长同样为 \(O(L)\) .总时间 \(O(L(1+B))\) ，输入、三分量工作数组与方块清单占 \(O(L)\) 空间，递归栈为 \(O(1+B)\) .

它保持分阶段 FWT 的时间阶，并将其 \(O(L(1+B))\) 空间降为 \(O(L)\) ；相较逐块 FWT，则省去完整变换的一个对数因子。代价是每个工作值有三个分量，模乘与分类操作的常数不同。分阶段 FWT 仍作标程，三者提供不同的时间与空间取舍，实际性能以同输入测量为准。

同输入测量¶

与标程在全部 10 份正式输入上的输出一致；五轮交替计时及输入、源码、程序哈希见完整记录，环境见参考评测环境。标程最慢中位耗时为 0.499386 秒，补充方案为 0.584175 秒；峰值工作集分别为 125.83 与 41.74 MiB，包含进程与运行库开销。补充程序在全部已测正式输入上均低于 1.0 秒参考时限。该结论仅针对随附实现、这些输入与参考环境；有限测试不代替正确性证明，也不保证每一种同阶实现通过。