# DNA 双链序列计数: 题解

## 方法与贡献

出题人解法按对称性计数，得到按长度奇偶区分的公式，再用二进制快速幂求值。Codex（GPT-6）补充自包含的反向互补模型和对合证明，并整理标准 C++17 程序 [std.cpp](std.cpp)。大批量询问还可以使用[两级幂表](solution-alternative.zh.md)及 [alternative.cpp](alternative.cpp)，以少量预计算空间换取每次询问常数时间。

设 $R(s)$ 是串 $s$ 的反向互补串。互补两次、反转两次都会还原，所以 $R(R(s))=s$ .每种分子对应一个或两个字符串。

## 出题人的第一处不对称计数

先令长度为 $2h$ .从 $s$ 与 $R(s)$ 的开头同时比较，也就是逐对确定两端字母。

- 如果始终相同，前 $h$ 个字母各有四种选择，后半部分被唯一确定，共 $4^h$ 种。
- 如果第一次不同发生在第 $i$ 对，之前有 $4^{i-1}$ 种选择；本对两种不同字母无序选择，有 $\binom42=6$ 种。用它们的顺序固定两条链的代表方向后，中间 $2h-2i$ 个字母可任意选择。

因此偶数长度的数量为

$$4^h+6\sum_{i=1}^{h}4^{i-1}4^{2h-2i}=2^{2h-1}(1+2^{2h})$$

长度为 $2h+1$ 时，若外侧完全对称，中间互补对只有两种；若外侧已有不同，代表方向已确定，中间字母有四种。于是

$$2\cdot4^h+4\left(6\sum_{i=1}^{h}4^{i-1}4^{2h-2i}\right)=2^{4h+1}$$

## 对合解释与实现

也可以直接统计固定串。奇数长度的中间字母需要等于自己的互补字母，不可能成立。偶数长度时，前半串任意选择即可，固定串有 $4^{n/2}$ 个。其余串两两配对，因此总数为

$$\frac{4^n+[n\text{ 为偶数}]4^{n/2}}{2}$$

这与上面的公式一致。程序在奇数长度时计算 $2^{2n-1}$ ；偶数长度时先算 $z=2^{n-1}\bmod p$ ，再算 $z(2z+1)\bmod p$ ，其中 $p=10^9+7$ .每个询问先取模，再将结果异或到累计答案，重复询问会按异或规则相消。

## 正确性与复杂度

第一处不同的分类互斥且覆盖全部字符串表示；完全对称和已确定代表方向的情况分别消除了链交换造成的重复。对合计数也表明每个非固定表示恰好有一个不同伙伴。因此公式恰好计数题目定义的等价类。快速幂精确计算模幂，逐次异或得到要求的汇总。

单个询问 $O(\log(n+1))$ 时间、$O(1)$ 辅助空间；总时间为各询问代价之和。最大指数不超过 $1999999999$ ，乘法使用有符号 64 位。幂表方案在大量询问中更快，但有初始化和存储开销；二进制幂保留为空间更省的首选。