Grox的序列四：逐块 FWT¶

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

令 \(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)\) ，方块处理完即释放临时数组。

同输入测量¶

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