Counting Paired DNA Strands over a Length Range¶
Codex (GPT-6) contributions: count fixed reverse-complement representations, derive length-prefix sums, and implement division-free geometric block merging. The counting uses the classical orbit partition of an involution, not a newly invented method.
A fixed length¶
Let \(q=2K\) . Reverse complementation applied twice returns the original string, so each class has one or two representations. An odd-length string cannot be fixed, because its middle letter would have to complement itself. At even length \(t=2h\) , the first half is arbitrary and determines the second half, giving \(q^h\) fixed representations.
Each fixed representation forms one class; all others form pairs. Thus
Brackets denote one when the condition holds and zero otherwise. The modulus \(P=1000000007\) is an odd prime, so division by two is multiplication by \(500000004\) .
Prefixes of lengths¶
Define \(G(h)=\sum_{i=1}^{h}q^i\) and \(G(0)=0\) . Summing the fixed-length formula gives
Set \(h=\lfloor n/2\rfloor\) , \(p=q^h\) , and \(s=G(h)\) . We have \(G(2h)=s(1+p)\) ; for odd size, add \(q^{2h+1}=p^2q\) . Therefore
The interval answer is \(H(R)-H(L-1)\) , normalized modulo the modulus. This also gives \(H(0)=0\) .
Division-free geometric blocks¶
A block of length \(h\) stores \((p,s)=(q^h,G(h))\) . Appending a length-\(b\) block to a length-\(a\) block gives
Starting with empty block \((1,0)\) and unit block \((q,q)\) , merge and double according to the binary digits of the length. This computes any \((q^h,G(h))\) . Every identity holds modulo \(P\) , even when \(q\equiv1\pmod P\) , without a special case.
Fixed-representation counting proves the single-length formula. The block invariant proves each merge correct, and subtracting prefixes gives the required interval count. Each query takes \(O(\log(R+1))\) time and \(O(1)\) auxiliary space. Streaming all queries takes total time \(O(\sum\log(R+1))\) . Use 64-bit modular products; a product of two reduced values is below approximately \(10^{18}\) .
Closed-form geometric sums give another method of the same asymptotic order; see the program. It uses fewer block variables but needs a modular inverse per query or a special-ratio case. Both programs pass the complete data.
Implementation and validation¶
Standard program, generator, and test recipes.
The slowest standard-program median in the reference environment is 0.076774 seconds, with peak working set 5.32 MiB, and calibrated limit 0.5 seconds. Each case has five independent timing runs.
See the evaluation environment and individual timings and hashes. Measurements apply to that environment; recalibrate on another judge.