题解 P4430 【小猴打架】

prufer编码是啥?Cayley定理是啥?主不了解? 没事 让我们用矩阵树定理推一波 首先这个小猴打架最后会打成一棵树，这棵树是N个点的完全图的生成树 所以用矩阵树定理 构建矩阵(N个点的完全图) 这是我们的邻接矩阵 $\begin{vmatrix}0&1&1&\cdots&1\\1&0&1&\cdots&1\\1&1&0&\cdots&1\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&1&1&\cdots&0\end{vmatrix}$ 然后是我们的度数矩阵 $\begin{vmatrix}N-1&0&0&\cdots&0\\0&N-1&0&\cdots&0\\0&0&N-1&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&N-1\end{vmatrix}$ 所以说我们的基尔霍夫矩阵是N*N的下面矩阵： $\begin{vmatrix}N-1&-1&-1&\cdots&-1\\-1&N-1&-1&\cdots&-1\\-1&-1&N-1&\cdots&-1\\\vdots&\vdots&\vdots&\ddots&\vdots\\-1&-1&-1&\cdots&N-1\end{vmatrix}$ 然后我们开始大力跑代数余子式 划掉第N行第N列的元素得到一个(N-1)*(N-1)的矩阵： $\begin{vmatrix}N-1&-1&-1&\cdots&-1\\-1&N-1&-1&\cdots&-1\\-1&-1&N-1&\cdots&-1\\\vdots&\vdots&\vdots&\ddots&\vdots\\-1&-1&-1&\cdots&N-1\end{vmatrix}$ 注意这个矩阵是(N-1)*(N-1)的 然后对这个矩阵进行各种初等变换~~(初等乱搞)~~(以下方法参考《线性代数》) 我们先让第一行成为所有(N-1)行的和(初等变换第三条) $\begin{vmatrix}1&1&1&\cdots&1\\-1&N-1&-1&\cdots&-1\\-1&-1&N-1&\cdots&-1\\\vdots&\vdots&\vdots&\ddots&\vdots\\-1&-1&-1&\cdots&N-1\end{vmatrix}$ 然后让第2~(N-1)行都加上第一行(初等变换第三条) $\begin{vmatrix}1&1&1&\cdots&1\\0&N&0&\cdots&0\\0&0&N&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&N\end{vmatrix}$ 消成了上三角矩阵（美滋滋） 所以行列式就是对角线元素相乘，有1个1，(N-2)个N 所以生成树个数为$N^{N-2}$ 然后 考虑生成树的每一条边 小猴打架可以按照任意的顺序 所以每一种生成树的产生顺序就是他的边的排列个数， 有$(N-1)$条边所以排列为$(N-1)!$ 所以最后答案是$N^{N-2}(N-1)!$ ``` #include <bits/stdc++.h> using namespace std; #define p 9999991 long long n, ans = 1; int main() { scanf("%lld", &n); for (int i = 1; i <= n - 2; i++) ans = ans * n % p * (i + 1) % p; printf("%lld\n", ans); return 0; } ``` 让我们一起膜拜大佬林瑞堂@[olinr](https://www.luogu.org/space/show?uid=88460)