DNA 双链序列计数: 补充解法¶

固定底数的两级幂表¶

计数公式来自出题人，Codex（GPT-6）补充两级表求模幂的实现 alternative.cpp。公式和计数证明见主题解。

所有需要计算的幂都是 \(2^e\bmod p\) ，且 \(0\le e\le E=1999999999\) .取块长 \(B=32768\) ，写成 \(e=tB+r\) ，其中 \(0\le r<B\) .预先保存

\[ Low_r=2^r\bmod p,\qquad High_t=(2^B)^t\bmod p \]

低位表逐次乘二，高位表逐次乘以 \(2^B\) .查询时返回 \(High_tLow_r\bmod p\) ，由指数加法恒等式立即得到正确值。将这个值代入相同的奇偶计数公式，再按顺序异或。

预处理时间和空间都是 \(O(B+E/B)\) ，单个询问 \(O(1)\) ，总时间 \(O(B+E/B+m)\) .两张32位整数表约占 \(375\) KB。固定的上界使它无需保存所有询问。

此方案减少大量询问中的乘法次数，代价是预处理和表空间；原二进制幂只需常数辅助空间、适合更少询问。两者并列适用，不把表方案宣称为所有输入下都更好。