题解：P12046 [USTCPC 2025] 生成树！
Rosaya
·
·
题解
这里找规律等等可以通过此题的方法不在介绍，仅介绍 std 做法。
前置芝士
Matrix-Tree 定理。
列出 n+1 个点 k 阶轮的 Laplace 矩阵，再删掉中心点所在行列，最终答案即为该矩阵的行列式。
常规做法
答案只需计算如下矩阵的行列式，其中主对角线上的值 a_{i,i} 在 i 是 k 的倍数时为 3，否则为 2。
\begin{vmatrix}
2 & -1 & \cdots & -1 \\
-1 & 2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
-1 & 0 & \cdots & 3
\end{vmatrix}
该行列式可以拆成四部分：
\begin{vmatrix}
0 & -1 & \cdots & 0 \\
0 & 2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
-1 & 0 & \cdots & 0
\end{vmatrix}
+
\begin{vmatrix}
0 & 0 & \cdots & -1 \\
-1 & 2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 0
\end{vmatrix}
\\
+
\begin{vmatrix}
2 & -1 & \cdots & 0 \\
-1 & 2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 3
\end{vmatrix}
+
\begin{vmatrix}
0 & 0 & \cdots & -1 \\
0 & 2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
-1 & 0 & \cdots & 0
\end{vmatrix}
其中前两项的答案均为 -1，后两项行列式满足如下形式：
\begin{vmatrix}
a_{1,1} & -1 & \cdots & 0 \\
-1 & a_{2,2} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{n,n}
\end{vmatrix}
记 \Delta_n 表示 n \times n 的矩阵的行列式，有性质 \Delta_n=a_{n,n}\Delta_{n-1} - \Delta_{n-2}，可以用矩阵快速幂优化，复杂度 O(\log n)。