远古记忆里的一道模拟赛题

· · 个人记录

远古记忆里的一道模拟赛题，没记错应该是 djq 老师的场/bx/bx/bx

不知道有没有原，有道题面类似的题 Since A Light 来着。

之前经常想起来经常想不起来怎么做，遂记录。

定义 T_0 为一个结点的有根树，T_n 为 T_{n-1} 的根节点下面再挂一个 T_{n-1} 作为子树的树，问 T_n 中距离为 d 的点对数，对 10^9+7 取模。

--- 设 $f(n,d)$ 为答案，则跨过两个 $T_{n-1}$ 间连的边的点对数为 $\sum\limits_{i=0}^{d-1}\binom{n-1}{i}\binom{n-1}{d-1-i}$，因为显然 $T_n$ 中有 $\binom{n}{i}$ 个深度为 $i$ 的点。Vandermonde 卷积可得为 $\binom{2n-2}{d-1}$，故而 $f(n,d)=2f(n-1,d)+\binom{2n-2}{d-1}$，即答案为 $\sum\limits_{i=0}^{n-1}2^{n-1-i}\binom{2i}{d-1}$。 ……额这个 $\binom{2i}{d-1}$ 看起来挺难处理的？有没有什么高妙的事情，让复杂度转移到 $d$ 上？ --- 回到上一步 Vandermonde 卷积之前，我们要找两个 $\{1,2,\cdots,i\}$ 的子集大小和为 $d'=d-1$。**枚举其交的大小**。设交的大小为 $b$，则对称差的大小为 $d-1-2b$，则有 $$ \dbinom{2i}{d'}=\sum_{b=0}^{\lfloor d'/2\rfloor}2^{d'-2b}\dbinom{i}{b,d'-2b,i-d'+b}=\sum_{b=0}^{\lfloor d'/2\rfloor}2^{d'-2b}\dbinom{d'-b}{b}\dbinom{i}{d'-b} $$ --- 我们利用枚举一个 $O(d)$ 的变量的代价使得上指标的 $2i$ 变成了 $i$！回到原式，答案为 $$ \sum_{b=0}^{\lfloor d'/2\rfloor}2^{d'-2b}\dbinom{d'-b}{b}\sum_{i=0}^{n-1}2^{n-1-i}\dbinom{i}{d'-b} $$ 此时关于 $i$ 的和式便明朗了起来：$i$ 个里选 $d-b$ 个，$n-1-i$ 个里面随便选，那么在中间插入一个元素的话，其实就是问 $n$ 个元素选至少 $d'-b+1=d-b$ 个的方案数——对于每个 $d-b\le d$，这都可以递推求出：用总共的 $2^n$ 再递推地逐一减去少于 $d-b$ 个的组合数即可。 本问题解决，时间复杂度 $O(d)$。