题解 P2144 【[FJOI2007]轮状病毒】

· · 题解

发现题目要求求出看起来很有规律的无向图生成树个数，显然可以找一些规律/打表/递推之类的，但不妨采用比较暴力的方法，矩阵树定理。

然后发现事情并没有那么简单，如果用矩阵树定理暴力去做的话，你可以选择一些乱搞/手写高精度小数类之类的方法

而之前又说，这个图比较特殊，所以，我们可以研究一下基尔霍夫矩阵的行列式有没有什么比较特殊的求法，n+1(n>2)阶的基尔霍夫矩阵大概长这个样子

\begin{bmatrix}n&-1&-1&-1&-1&\cdots&-1&-1&-1\\-1&3&-1&0&0&\cdots&0&0&-1\\-1&-1&3&-1&0&\dots&0&0&0\\-1&0&-1&3&-1&\cdots&0&0&0\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\-1&0&0&0&0&\cdots&-1&3&-1\\-1&-1&0&0&0&\cdots&0&-1&3\end{bmatrix} $$\begin{bmatrix}3&-1&0&0&\cdots&0&0&-1\\-1&3&-1&0&\dots&0&0&0\\0&-1&3&-1&\cdots&0&0&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\0&0&0&0&\cdots&-1&3&-1\\-1&0&0&0&\cdots&0&-1&3\end{bmatrix}$$ 设这个矩阵为$A_n$，那么$n$的答案就是$\det A_n$，然后我们考虑求出这个矩阵的行列式 由“行列式等于它的任一行（列）的各元素与其对应的代数余子式乘积之和” - 余子式：在$n$阶行列式中，把元素$a_{i,j}$所在第$i$行和第$j$行划去后，留下的$n-1$阶行列式叫元素$a_{i,j}$的余子式，记做$M_{i,j}$，定义代数余子式为$A_{i,j}=(-1)^{i+j}M_{i,j}

我们可以扔第一行，因为(1,n)和(n,1)两个位置的东西看起来巨难受。

拆开第一行第一列得到

3\begin{vmatrix}3&-1&0&\dots&0&0&0\\-1&3&-1&\cdots&0&0&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\0&0&0&\cdots&-1&3&-1\\0&0&0&\cdots&0&-1&3\end{vmatrix}

这个看起来就可以递推的东西，设n-1阶的它为B_{n-1}。为了方便，以下A_n,B_n也指代行列式的值。

然后剩下有贡献的第一行第二列和第一行第n-1列，因为余子式的正负与n有关，不妨先设n为奇数，偶数的情况是一样的。

\begin{vmatrix}-1&-1&0&\dots&0&0&0\\0&3&-1&\cdots&0&0&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\0&0&0&\cdots&-1&3&-1\\-1&0&0&\cdots&0&-1&3\end{vmatrix}

这是拆了第一行第二列，没思路再拆，发现扔第一行第一列后是-B_{n-2}，扔第n-1行第1列是主对角线全为-1的下三角，行列式的值为-1，再乘上(-1)^{n-1+1}(-1)还是-1

然后是第一行第n列

-\begin{vmatrix}-1&3&-1&0&\dots&0&0\\0&-1&3&-1&\cdots&0&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&0&\cdots&-1&3\\-1&0&0&0&\cdots&0&-1\end{vmatrix}

注意这里是负的，因为n是奇数。然后还是拆第一列，发现答案还是-B_{n-2}和-1

于是我们有A_n=3B_{n-1}-2B_{n-2}-2

以同样的方法对B做讨论，可以得到B_n=3B_{n-1}-B_{n-2}

然后联立一下得到A_{n}=3A_{n-1}-A_{n-2}+2，带入到n\le2发现式子仍然成立，然后直接递推+高精即可。