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

## 固定底数的两级幂表

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

所有需要计算的幂都是 $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。固定的上界使它无需保存所有询问。

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