# 老yd与并查集：题解

出题人解法：按终止路径的两种步数枚举，用组合数计算路径数量。Codex（GPT-6）的贡献是精确有理数界、模数表空间整理、证明与标准 C++17 实现。组合计数、阶乘逆元与相邻分数分母引理均为经典方法。

## 展开到第一次越过阈值

固定查询，令 $t=n-B\ge0$ .一条递归路径使用 $a$ 次减一和 $b$ 次减 $e$ ，叶子贡献为 $A C^aD^b$ .路径终止当且仅当

$$a+eb>t,$$

且去掉最后一步后的总减量不超过 $t$ .每步减量为正，故只要这个倒数第二位置合法，更早位置也全部合法。

![查询三时递归展开到两个叶子](assets/explanation.svg)

图对应第一个样例的 $n=3$ ：两个叶子值均为一，权重分别为七、四。

当 $b=0$ 时只有 $a=t+1$ ，贡献为 $C^{t+1}$ ，最后统一乘 $A$ .

对 $b\ge1$ ，记

$$L_b=\max(0,t-\lfloor eb\rfloor),\qquad R_b=\begin{cases}t,&b=1,\\t-\lfloor e(b-1)\rfloor-1,&b>1.\end{cases}$$

条件 $a+eb>t$ 给出 $a\ge L_b$ .若最后一步是减 $e$ ，倒数第二位置要求 $a+e(b-1)\le t$ ，给出 $a\le R_b$ ；$b=1$ 需要单独保留整数边界。若 $R_b<0$ ，更大的 $b$ 也不可能，停止枚举。

当 $a=L_b>0$ 时，最后一步既可以减一，也可以减 $e$ ，两种数量相加为

$$\binom{a+b-1}{a-1}+\binom{a+b-1}{a}=\binom{a+b}{a}.$$

当 $L_b=0$ 时只能最后减 $e$ ，但数量仍是 $\binom b0=1$ .当 $a>L_b$ 时只能最后减 $e$ ，数量为 $\binom{a+b-1}{a}$ .因此答案为

$$A\left(C^{t+1}+\sum_{b\ge1:R_b\ge0}D^b\left[\binom{L_b+b}{L_b}C^{L_b}+\sum_{a=L_b+1}^{R_b}\binom{a+b-1}{a}C^a\right]\right)\pmod{10^9+7}.$$

相邻的 $\lfloor eb\rfloor$ 相差二或三，所以每个 $b$ 至多枚举三个 $a$ .

## 用整数精确求取整

浮点误差不应决定叶子是否已经越过阈值。使用以下严格界：

$$\frac{410105312}{150869313}<e<\frac{28245729}{10391023}.$$

这两个分数可用纯整数核实。令 $S=\sum_{j=0}^{30}1/j!$ ，级数余项满足

$$S<e<S+\frac1{30\cdot30!}.$$

因为从第三十一项起，每个后续因子至少为三十一，余项小于相应的等比级数。通分比较即可验证左端分数小于 $S$ ，右端分数大于上述上界。此外

$$28245729\cdot150869313-410105312\cdot10391023=1.$$

若约分后的 $a/b$ 严格位于 $p/q<P/Q$ 之间，且 $Pq-pQ=1$ ，则正整数 $aq-bp$ 与 $bP-aQ$ 至少为一，从

$$b=(aq-bp)Q+(bP-aQ)q$$

得到 $b\ge q+Q$ .因此上述两个分数之间没有分母不超过 $10^7$ 的有理数，端点分数的分母也都大于 $10^7$ .对 $0\le b\le10^7$ ，整数边界不可能落在两个乘积之间，故

$$\lfloor eb\rfloor=\left\lfloor\frac{410105312\,b}{150869313}\right\rfloor.$$

最大乘积 $410105312\times10^7$ 小于六十四位有符号上界。程序只做整数乘除。

## 组合数与复杂度

令 $T=\max(n-B+1)$ .预计算阶乘、逆阶乘、$C$ 的幂和 $D$ 的幂，共四个三十二位数组，长度为 $T+1$ .模数 $p=10^9+7$ 是质数，且全部阶乘下标小于 $p$ ，因此阶乘可逆。一次快速幂求最大阶乘的逆元，再反向递推逆阶乘，组合数每次常数时间。模乘前提升为六十四位。

预处理 $O(T+\log p)$ ，全部询问 $O(\sum(n-B+1))$ ，空间 $O(T)$ ，最大数组主体约一亿六千万字节。所有组合数下标均不超过 $t+1\le T$ .

## 正确性与方案选择

每条递归分支由两种步数与最后一步唯一归类。上述不等式恰好刻画第一次终止，排列计数覆盖所有且仅有这些路径；不同路径对应递归展开的不同项，因此加权求和等于函数值。精确取整与模运算保持这一结果。

首选 [std.cpp](std.cpp) 保留出题人的终止路径计数与阶乘表组织。[单逆元表递推方案](solution-alternative.zh.md)及其 [alternative.cpp](alternative.cpp) 同样支持完整范围，额外模乘较多，但只保留一张线性数组，具有明确空间优势，作为并列方案。小输入用独立二维递归展开核验，全部正式输入对照两份发布程序与出题人程序；最大规模不宣称做了二次复杂度的递归核验。

数据：[plan.json](tests/plan.json)、[generate.py](tests/generate.py)。性能：[测量记录](../../../docs/benchmark-R26.json)。