# DNA 双链长度区间计数

**Codex（GPT-6）解法贡献：** 对反向互补的固定表示计数，推导长度前缀和，并实现无除法的等比块合并。计数使用经典的对合轨道划分，不将该方法归为模型原创。

## 固定长度

令 $q=2K$ .反向互补执行两次回到原串，因此每个等价类有一个或两个表示。奇数长度的中心字母不可能等于自身互补，没有固定表示。偶数长度 $t=2h$ 时，前一半任选，后一半被唯一确定，共 $q^h$ 个固定表示。

固定表示单独成类，其余两两成类，所以

$$F(t,K)=\frac{q^t+[2\mid t]q^{t/2}}{2}$$

这里方括号表示条件成立为一，否则为零。模数 $P=1000000007$ 为奇素数，除二可乘 $500000004$ .

## 长度前缀

定义 $G(h)=\sum_{i=1}^{h}q^i$ ，$G(0)=0$ .从固定长度公式得

$$H(n)=\sum_{t=1}^{n}F(t,K)=\frac{G(n)+G(\lfloor n/2\rfloor)}{2}$$

设 $h=\lfloor n/2\rfloor$ 、$p=q^h$ 、$s=G(h)$ .有 $G(2h)=s(1+p)$ ；奇数时再加 $q^{2h+1}=p^2q$ .因此

$$H(n)=\frac{s(p+2)+[2\nmid n]p^2q}{2}$$

区间答案为 $H(R)-H(L-1)$ ，对模数正规化即可。$H(0)=0$ 自然成立。

## 无除法的等比块

一个长度块保存 $(p,s)=(q^h,G(h))$ .在长度为 $a$ 的块后接长度为 $b$ 的块，得到

$$p_{a+b}=p_ap_b,\qquad s_{a+b}=s_a+p_as_b$$

从空块 $(1,0)$ 和单位块 $(q,q)$ 出发，按长度的二进制位合并与倍增，求出任意 $(q^h,G(h))$ .所有等式均在模 $P$ 下成立，即使 $q\equiv1\pmod P$ 也无需特殊处理。

固定表示计数证明了单长度公式；等比块不变量证明每次合并正确，前缀相减故得到准确的区间计数。单次询问时间 $O(\log(R+1))$ 、辅助空间 $O(1)$ ；流式处理全部询问，总时间 $O(\sum\log(R+1))$ .模乘中间量用 64 位，两个模内数的乘积小于约 $10^{18}$ .

[闭式等比求和](solution-alternative.zh.md)是另一种同阶方案，见[程序](alternative.cpp)。它减少块状态，但每个询问需要一个模逆元或处理特殊公比；两份程序均通过完整数据。

## 实现与验证

[标准程序](std.cpp)、[生成器](tests/generate.py)、[测试配方](tests/plan.json)。

参考环境中标准程序最慢中位数 0.076774 秒，峰值 5.32 MiB，校准时限 0.5 秒。每例独立运行五次。

[评测环境](../../../docs/评测环境与性能.md)与[逐次时间和哈希](../../../docs/benchmark-R31.json)。数值只适用于所记录环境，迁移评测机需重新校准。