题解：P12046 [USTCPC 2025] 生成树！

lfy_syx_172 · 2026-06-23 19:45:30 · 题解

首先考虑向点 0 向连边的点之间的间隔，设为 p_1k\ldots p_{\ell}k。

显然需要满足 k\sum_{i=1}^{\ell} p_i=n，即 \sum_{i=1}^{\ell} p_i=\frac{n}{k}。

不难发现，对于一组间隔 p，将其生成树个数，对于每个间隔，需要任意断掉一条边，显然这一步有 \prod_{i=1}^{\ell}{ p_ik} 种方案，又因为有 p_1 中选择第一个与 0 连边的点的方案（因为可以将断完边的环依次品平移能形成新方案，但如果平移超过 p_1 步，就会与原有方案重复，因此只能平移 [0,,p_1-1] 步），所以答案是 \sum_{p} {p_1\prod_{i=1}^{\ell}{p_ik}}。

考虑设 f_n 为 \sum_{p}=n 时的答案。

那么显然有递推关系 f_n=n^2k+\sum_{j=1}^{n-1}(i-j)kf_j。

但是这样显然无法直接递推，考虑化简递推式吗，推导过程不复杂，经典套路，计算 f_{n+2}+f_{n}-2\times f_{n+1}，化简得到 f_{n+2}+f_{n}-2\times f_{n+1}=kf_{n+1}+2k。

于是得到了更简单的递推关系：f_{n+2}=(k+2)f_{n+1}-f_n+2k。

可以直接矩阵快速幂计算，时间复杂度 \mathcal O(\log n)。

代码并不难写，1KB以内，留给读者独立完成。