Old yd and Disjoint Sets: Single Inverse Table¶
Contribution: the problem setter supplied terminal-path enumeration. Codex (GPT-6) added rolling weighted binomial coefficients, exact floors, proofs and implementation. Modular inverses and adjacent binomial ratios are classical formulas. This is a parallel option to the factorial-table solution, trading additional constant-time work for less space.
The same count with different coefficient storage¶
Use \(t=n-B\) , \(L_b,R_b\) and the exact floors proved in the main solution. The term without any \(e\) step is \(C^{t+1}\) . For \(b\ge1\) , its lowest term is
Higher \(j\in[L_b+1,R_b]\) contribute \(\binom{j+b-1}{j}C^jD^b\) . The terminal conditions and counts are unchanged; only the coefficient computation changes.
Precompute \(\operatorname{inv}[i]=i^{-1}\bmod p\) for \(p=10^9+7\) and \(1\le i\le T=\max(n-B+1)\) :
Because \(i<p\) , no inverse of zero is required. Obtain \(C^{-1}\) by exponentiation; the input guarantees \(1\le C<p\) .
Two adjacent moves¶
Start at \((a,b)=(t+1,0)\) with \(W=C^{t+1}\) . Before processing the next level \(b\) , keep the old second coordinate \(b-1\) and decrease \(a\) to \(L_b\) , repeatedly using
Then increase the second coordinate from \(b-1\) to \(b\) :
Replace division by multiplication with modular inverses. Add this lowest term. The first higher coefficient is
and subsequent coefficients satisfy
There are at most two higher terms per level. Keep their temporary variable separate from \(W\) , since the next level continues from the lowest term.
Correctness, range and complexity¶
Both coordinate moves and the higher-term recurrence follow directly from factorial ratios of binomial coefficients. Every denominator is a nonzero residue from \(1,\ldots,T\) . Inductively, the maintained \(W\) equals its defined weighted binomial coefficient. The enumerated terms are exactly the terminal-path terms in the main solution, so the answer is identical.
Within a query, \(a\) only decreases from \(t+1\) to zero, and \(b\) only increases, giving \(O(t+1)\) moves. Total time is \(O(T+\sum(n-B+1)+M\log p)\) and space is \(O(T)\) . The largest inverse array uses about forty million bytes. The exact rational floor certificate, sixty-four-bit modular multiplication and original input range all remain applicable.
This program supports the full data range. It is useful when saving memory is the priority; factorial tables have smaller query constants. See the five-run measurements for observed times and peak working sets.
Program: alternative.cpp. Checks include independent recursive expansion, complete comparison with factorial tables and comparison with the setter's program.