GitHub 源文件 Markdown English

老yd与并查集：题解

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

展开到第一次越过阈值

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

\[ a+eb>t, \]

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

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

数据：plan.json、generate.py。性能：测量记录。