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

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

## 只保存需要的三个系数

沿用主题解的 $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 份正式输入上的输出一致；五轮交替计时及输入、源码、程序哈希见[完整记录](../../../docs/benchmark-R14-supplements.json)，环境见[参考评测环境](../../../docs/评测环境与性能.md)。标程最慢中位耗时为 0.499386 秒，补充方案为 0.584175 秒；峰值工作集分别为 125.83 与 41.74 MiB，包含进程与运行库开销。
补充程序在全部已测正式输入上均低于 1.0 秒参考时限。该结论仅针对随附实现、这些输入与参考环境；有限测试不代替正确性证明，也不保证每一种同阶实现通过。