# 多类配对的 DNA 双链计数: 题解

## 方法与贡献

Codex（GPT-6）应用反向互补对合的等价类计数，并在模 $2P$ 下计算分子，保证任意模数下的除二都精确。程序见 [std.cpp](std.cpp)。这种计数是对合轨道的常用方法；贡献是本题中的应用、数值处理、证明与实现。

令 $q=2K$ ，表示字母总数。每种结构由一个串 $s$ 表示，交换两条链对应反向互补 $R(s)$ .因为 $R(R(s))=s$ ，一个等价类只有一或两个表示。

## 等价类的数量

全部字符串有 $q^N$ 个。若 $N$ 为奇数，固定串的中间字母必须与自身互补，与配对定义矛盾。若 $N$ 为偶数，前一半有 $q^{N/2}$ 种选择，另一半被唯一确定，恰好得到这些固定串。

固定串每个单独成类，其余串每两个成类，所以精确整数答案为

$$C=\frac{q^N+[N\text{ 为偶数}]q^{N/2}}{2}$$

## 任意模数下精确除二

$P$ 可以为一、偶数或合数，因此实现不依赖二的逆元。令整数分子为 $A$ ，计算 $r=A\bmod(2P)$ .因为 $A$ 与 $2P$ 都为偶数，$r$ 也是偶数。由 $A=2Pt+r$ 得

$$C=Pt+r/2,\qquad C\bmod P=r/2$$

最后一个值已经位于 $[0,P-1]$ ，可以直接与累计答案异或。

奇数长度时计算 $q^N\bmod(2P)$ .偶数长度时只需一次快速幂：令 $h=q^{N/2}\bmod(2P)$ ，分子余数是 $(h^2+h)\bmod(2P)$ .这样每个询问只有一次二进制幂。

## 正确性与复杂度

固定串与二元素类的分类证明了计数公式；模 $2P$ 的等式证明普通整数除二得到正确的模 $P$ 答案。每个询问先得到这个余数，再异或，符合题意。

单次时间 $O(\log(N+1))$ 、辅助空间 $O(1)$ ，可流式处理所有询问。$2P\le2\times10^9$ ，最大乘加小于 $4\times10^{18}$ ，有符号 64 位足够。把公式中的因子 $K$ 提出也能进行无逆元计算，但它是同一计数公式的等价数值写法，无需另设一种算法。