Description:


  轮状病毒有很多变种,所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子
和圆心处一个核原子构成的,2个原子之间的边表示这2个原子之间的信息通道。如下图所示

N轮状病毒的产生规律是在一个N轮状基中删去若干条边,使得各原子之间有唯一的信息通道,例如共有16个不
同的3轮状病毒,如下图所示

现给定n(N<=100),编程计算有多少个不同的n轮状病毒

Input:


  第一行有1个正整数n

Output:


  计算出的不同的n轮状病毒数输出

Sample Input:


Sample Output:


题解:


这个题目初一看不是一道矩阵树的模板题吗~

然后打完了暴力高斯消元后交上去发现WA了QAQ。

天真的以为开个long long就可以了,然后还是WA~

最后搞黑科技__int128发现最后一个点还是炸了。(用double精度也炸了QAQ)

于是悲催的我开始了找规律,然后发现这个东西是可以用矩阵树定理证明的。

如果你不知道矩阵树定理是什么的话可以戳这里~

矩阵树定理中的这一个矩阵正式名字叫做基尔霍夫矩阵,因为题目中的图有一定特点,它的基尔霍夫矩阵长成这样:

\(\begin{bmatrix} n & -1 & -1 & -1 & \cdots & -1 & -1 \\ -1 & 3 & -1 & 0 & \cdots & 0 & -1 \\ -1 & -1 & 3 & -1 & \cdots & 0 & 0 \\ -1 & -1 & -1 & 3 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ -1 & 0 & 0 & 0 & \cdots & 3 & -1 \\ -1 & -1 & 0 & 0 & \cdots & -1 & 3 \end{bmatrix}\)

那么它的生成树个数就是这个行列式的值:(去掉第一行第一列)

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

我们接下来使用拉普拉斯展开第一行(拉普拉斯展开(百度百科) )

\(\begin{vmatrix} 3 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 & -1 \\ -1 & 3 & -1 & 0 & \cdots & 0 & 0 & 0 & 0 \\ 0 & -1 & 3 & -1 & \cdots & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 3 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & -1 & 3 & -1 \\ -1 & 0 & 0 & 0 & \cdots & 0 & 0 & -1 & 3 \end{vmatrix} = \)

\( 3 \times \begin{vmatrix} 3 & -1 & 0 & \cdots & 0 & 0 & 0 & 0 \\ -1 & 3 & -1 & \cdots & 0 & 0 & 0 & 0 \\ 0 & -1 & 3 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & -1 & 3 & -1 \\ 0 & 0 & 0 & \cdots & 0 & 0 & -1 & 3 \end{vmatrix} + \begin{vmatrix} -1 & -1 & 0 & \cdots & 0 & 0 & 0 & 0 \\ 0 & 3 & -1 & \cdots & 0 & 0 & 0 & 0 \\ 0 & -1 & 3 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & -1 & 3 & -1 \\ -1 & 0 & 0 & \cdots & 0 & 0 & -1 & 3 \end{vmatrix} +\begin{vmatrix}-1 & 3 & -1 & 0 & \cdots & 0 & 0 & 0 \\ 0 & -1 & 3 & -1 & \cdots & 0 & 0 & 0 \\ 0 & 0 & -1 & 3 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & -1 & 3 \\ -1 & 0 & 0 & 0 & \cdots & 0 & 0 & -1 \end{vmatrix}\)

(因为该行列式第一行中间全部为0)

后面的两个行列式不太好看,我们继续将它们按照第一列展开。

\(\begin{vmatrix} 3 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 & -1 \\ -1 & 3 & -1 & 0 & \cdots & 0 & 0 & 0 & 0 \\ 0 & -1 & 3 & -1 & \cdots & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 3 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & -1 & 3 & -1 \\ -1 & 0 & 0 & 0 & \cdots & 0 & 0 & -1 & 3 \end{vmatrix} = \)

\(3 \times \begin{vmatrix} 3 & -1 & 0 & \cdots & 0 & 0 & 0 & 0 \\ -1 & 3 & -1 & \cdots & 0 & 0 & 0 & 0 \\ 0 & -1 & 3 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & -1 & 3 & -1 \\ 0 & 0 & 0 & \cdots & 0 & 0 & -1 & 3 \end{vmatrix} - \begin{vmatrix} 3 & -1 & \cdots & 0 & 0 & 0 & 0 \\ -1 & 3 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & -1 & 3 & -1 \\ 0 & 0 & \cdots & 0 & 0 & -1 & 3 \end{vmatrix} - \begin{vmatrix}-1 & 0 & \cdots & 0 & 0 & 0 & 0 \\ 3 & -1 & \cdots & 0 & 0 & 0 & 0 \\ -1 & 3 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & -1 & 3 & -1 \end{vmatrix} - \begin{vmatrix}-1 & 3 & -1 & \cdots & 0 & 0 & 0 \\ 0 & -1 & 3 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\0 & 0 & 0 & \cdots & 0 & -1 & 3 \\ 0 & 0 & 0 & \cdots & 0 & 0 & -1 \end{vmatrix} - \begin{vmatrix}3 & -1 & 0 & \cdots & 0 & 0 & 0 \\-1 & 3 & -1 & \cdots & 0 & 0 & 0 \\0 & -1 & 3 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & -1 & 3\end{vmatrix}\)

然后我们发现等式右边第三个和第五个行列式等于-1。我们令对角线为3周围两条-1的n阶行列式为 \(f(n)\) ,题目中 \(n\) 对应的答案为 \(g(n)\) 。上面的式子即为:

\(g(n) = 3\times f(n-1) - 2 \times f(n-2) - 2\)

我们可以用相似的方法推导出 \(f(n) = 3\times f(n-1) - f(n-2)\)

然后解一下方程组可以把 \(f\) 消掉。

得到递推式: \(g(n) = 3 \times g(n-1) - g(n-1) - g(n-2) + 2\)

然后我们就可以开心的来写高精度了QAQ(以上步骤可以不用写高精度除法)

代码如下: