多类配对的 DNA 双链计数: 题解¶
方法与贡献¶
Codex（GPT-6）应用反向互补对合的等价类计数，并在模 \(2P\) 下计算分子，保证任意模数下的除二都精确。程序见 std.cpp。这种计数是对合轨道的常用方法；贡献是本题中的应用、数值处理、证明与实现。
令 \(q=2K\) ，表示字母总数。每种结构由一个串 \(s\) 表示，交换两条链对应反向互补 \(R(s)\) .因为 \(R(R(s))=s\) ，一个等价类只有一或两个表示。
等价类的数量¶
全部字符串有 \(q^N\) 个。若 \(N\) 为奇数，固定串的中间字母必须与自身互补，与配对定义矛盾。若 \(N\) 为偶数，前一半有 \(q^{N/2}\) 种选择，另一半被唯一确定，恰好得到这些固定串。
固定串每个单独成类，其余串每两个成类，所以精确整数答案为
任意模数下精确除二¶
\(P\) 可以为一、偶数或合数，因此实现不依赖二的逆元。令整数分子为 \(A\) ，计算 \(r=A\bmod(2P)\) .因为 \(A\) 与 \(2P\) 都为偶数，\(r\) 也是偶数。由 \(A=2Pt+r\) 得
最后一个值已经位于 \([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\) 提出也能进行无逆元计算，但它是同一计数公式的等价数值写法，无需另设一种算法。