老yd与并查集：单逆元表方案¶

贡献：出题人的终止路径枚举模型；Codex（GPT-6）补充加权组合数滚动递推、精确取整、证明与实现。模逆元和组合数相邻项关系是经典公式。本方案与阶乘表方案并列，减少空间，增加常数时间开销。

公共计数与新组织¶

沿用主解完整证明的 \(t=n-B\) 、\(L_b,R_b\) 及精确 \(\lfloor eb\rfloor\) .无 \(e\) 步的项为 \(C^{t+1}\) ；每个 \(b\ge1\) 的最低项为

\[ W(a,b)=\binom{a+b}{a}C^aD^b,\qquad a=L_b. \]

更高的 \(j\in[L_b+1,R_b]\) 使用 \(\binom{j+b-1}{j}C^jD^b\) .这些终止条件与计数不变，只调整系数计算方式。

预计算 \(\operatorname{inv}[i]=i^{-1}\bmod p\) ，其中 \(p=10^9+7\) ，\(1\le i\le T=\max(n-B+1)\) ：

\[ \operatorname{inv}[1]=1,\qquad\operatorname{inv}[i]=p-\lfloor p/i\rfloor\operatorname{inv}[p\bmod i]\bmod p. \]

由于 \(i<p\) ，递推中不会对零求逆。另用快速幂求 \(C^{-1}\) ；输入保证 \(1\le C<p\) .

初始化 \((a,b)=(t+1,0)\) ，\(W=C^{t+1}\) .准备处理下一层 \(b\) 时，先保持旧的 \(b-1\) ，将 \(a\) 降到 \(L_b\) ，每次利用

\[ W(a-1,b-1)=W(a,b-1)\frac{a}{a+b-1}C^{-1}. \]

然后把第二个坐标从 \(b-1\) 增至 \(b\) ：

\[ W(a,b)=W(a,b-1)\frac{a+b}{b}D. \]

所有除法替换为模逆元。这样得到最低项，加入答案。第一项更高的系数为

\[ V_{a+1}=W(a,b)\frac{b}{a+1}C, \]

其后用

\[ V_j=V_{j-1}\frac{j+b-1}{j}C. \]

每个 \(b\) 的额外项至多两个。不要用计算这些额外项的变量覆盖最低项 \(W\) ，下一层需要从最低项继续。

两种坐标移动及额外项递推都直接来自阶乘形式的组合数比值，且所有分母为 \(1,\ldots,T\) 的非零模数。归纳可知，每次更新后的 \(W\) 精确等于定义的加权组合数；枚举项与主解的全部终止路径项完全一致，故答案相同。

每个查询中 \(a\) 只减少，从 \(t+1\) 到零；\(b\) 只增加，共 \(O(t+1)\) 次移动。总时间 \(O(T+\sum(n-B+1)+M\log p)\) ，空间 \(O(T)\) ，最大逆元数组约四千万字节。程序仍使用主解的整数有理数取整证书，六十四位模乘与原范围均不变。

本方案能通过完整数据。它适合优先节省内存的环境；阶乘表方案的查询常数更小。两者的具体五轮运行时间和峰值工作集见测量记录。

程序：alternative.cpp。验证包括独立递归展开、与阶乘表方案逐项比较及完整原程序对照。