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

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

## 公共计数与新组织

沿用主解完整证明的 $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)$ ，最大逆元数组约四千万字节。程序仍使用主解的整数有理数取整证书，六十四位模乘与原范围均不变。

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

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