# Grox的序列四：逐块 FWT

**出题人解法：逐块变换的空间优先方案。** Codex（GPT-6）整理边界、模运算与 C++17 实现。此方案与[分阶段 FWT](solution.zh.md)并列：空间更低，时间阶更高。

令 $L$ 为不小于 $n+1$ 的最小二次幂，$B=\log_2L$ .将合法区域 $i+j\le n$ 分成互不重叠的对齐方块；分解规则与主方案相同。

每个接受方块的边长为 $s=2^d$ ，起始下标 $a,b$ 的低 $d$ 位均为零，因此

$$(a+u)\circ(b+v)=(a\circ b)+(u\circ v)$$

对两段长度为 $s$ 的数组独立执行完整的正 FWT，逐项相乘，再逆变换。按照高位偏移 $a\circ b$ 将结果直接累加到三个余数类别，不保留跨层结果数组。对 XOR、OR、AND 分别处理。

方块互不重叠并覆盖全部合法数对；高低位分离保证局部卷积的偏移正确；完整正逆变换得到每块的全部贡献，所以结果与分阶段方案相同。蝶形规则与按位卷积证明见主题解。

边长为 $s$ 的一层有 $O(L/s)$ 个方块，每块完整变换为 $O(s(1+\log s))$ ；各层累加得到 $O(L(1+B)^2)$ 时间。输入与当前方块数组共占 $O(L)$ 空间。递归深度为 $O(1+B)$ ，方块处理完即释放临时数组。

## 同输入测量

测量结果见[参考环境与性能](../../../docs/评测环境与性能.md)及 [R14 原始记录](../../../docs/benchmark-R14.json)。逐块方案在10份相同正式输入上均与标程输出一致，五轮交替计时的最慢中位时间为 0.892257 秒，峰值工作集为 17.16 MiB。分阶段方案在同轮比较中的最慢中位时间为 0.466883 秒；参考标程峰值为 125.83 MiB。逐块方案在全部已测正式输入上均低于 1.0 秒参考时限。该结论限于这些输入和参考环境，不保证所有同阶实现均通过。空间优先时可选此方案；标准程序以完整数据的时间余量为依据选择分阶段方案。