DNA 双链序列计数: 题解¶

方法与贡献¶

出题人解法按对称性计数，得到按长度奇偶区分的公式，再用二进制快速幂求值。Codex（GPT-6）补充自包含的反向互补模型和对合证明，并整理标准 C++17 程序 std.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 位。幂表方案在大量询问中更快，但有初始化和存储开销；二进制幂保留为空间更省的首选。