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

这里找规律等等可以通过此题的方法不在介绍，仅介绍 std 做法。

Matrix-Tree 定理。

列出 $n+1$ 个点 $k$ 阶轮的 Laplace 矩阵，再删掉中心点所在行列，最终答案即为该矩阵的行列式。

答案只需计算如下矩阵的行列式，其中主对角线上的值 $a_{i,i}$ 在 $i$ 是 $k$ 的倍数时为 $3$，否则为 $2$。

该行列式可以拆成四部分：

其中前两项的答案均为 $-1$，后两项行列式满足如下形式：

记 $\Delta_n$ 表示 $n \times n$ 的矩阵的行列式，有性质 $\Delta_n=a_{n,n}\Delta_{n-1} - \Delta_{n-2}$，可以用矩阵快速幂优化，复杂度 $O(\log n)$。