DNA 双链长度区间计数¶
Codex（GPT-6）解法贡献： 对反向互补的固定表示计数，推导长度前缀和，并实现无除法的等比块合并。计数使用经典的对合轨道划分，不将该方法归为模型原创。
固定长度¶
令 \(q=2K\) .反向互补执行两次回到原串，因此每个等价类有一个或两个表示。奇数长度的中心字母不可能等于自身互补，没有固定表示。偶数长度 \(t=2h\) 时，前一半任选，后一半被唯一确定，共 \(q^h\) 个固定表示。
固定表示单独成类，其余两两成类，所以
这里方括号表示条件成立为一，否则为零。模数 \(P=1000000007\) 为奇素数，除二可乘 \(500000004\) .
长度前缀¶
定义 \(G(h)=\sum_{i=1}^{h}q^i\) ，\(G(0)=0\) .从固定长度公式得
设 \(h=\lfloor n/2\rfloor\) 、\(p=q^h\) 、\(s=G(h)\) .有 \(G(2h)=s(1+p)\) ；奇数时再加 \(q^{2h+1}=p^2q\) .因此
区间答案为 \(H(R)-H(L-1)\) ，对模数正规化即可。\(H(0)=0\) 自然成立。
无除法的等比块¶
一个长度块保存 \((p,s)=(q^h,G(h))\) .在长度为 \(a\) 的块后接长度为 \(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}\) .
闭式等比求和是另一种同阶方案，见程序。它减少块状态，但每个询问需要一个模逆元或处理特殊公比；两份程序均通过完整数据。
实现与验证¶
参考环境中标准程序最慢中位数 0.076774 秒，峰值 5.32 MiB，校准时限 0.5 秒。每例独立运行五次。