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

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

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

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

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

$1\le n\le 10^9$ 而 $1\le d\le 10^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$，则有

我们利用枚举一个 $O(d)$ 的变量的代价使得上指标的 $2i$ 变成了 $i$！回到原式，答案为

此时关于 $i$ 的和式便明朗了起来：$i$ 个里选 $d-b$ 个，$n-1-i$ 个里面随便选，那么在中间插入一个元素的话，其实就是问 $n$ 个元素选至少 $d'-b+1=d-b$ 个的方案数——对于每个 $d-b\le d$，这都可以递推求出：用总共的 $2^n$ 再递推地逐一减去少于 $d-b$ 个的组合数即可。

本问题解决，时间复杂度 $O(d)$。