BZOJ-1002: Rotavirus [FJOI2007]

Problem Description: There are many variety to the rotavirus. Some of them follow the structure in the image below(graph 1.1), where there are connections between every node on the circumference with the center and with its neighbour. Specifically, we define the N-sided virus as a virus that for every pairs of nodes on the virus there is only one path to go through. For example, if  = 3, then there are 16 different kinds of N-sides viruses(graph 1.2). For any given N (N ≤ 100), print the number of different ways to form a N-sides virus.

Graph 1.1                            Graph1.2

Input Format: One line with integer N
Output Format: The number of ways to form a N-sides virus
Sample Input:
3
Sample Output:
16

Solution: First of all, we see that the requirement for the formed graph is to have only one path between any pairs of nodes. Therefore, it has be a tree. Then, this problem is transformed into a problem that needs us to count the number of spanning trees. There is a theorem called Kirchhoff’s Matrix-Tree Theorem that can help us do this. In Kirchhoff’s Matrix-Tree Theorem, we know that the number of spanning trees for a given graph G with N nodes is the value of the determinant of the matrix Q, where Q is the cofactor matrix of R and R equals to the degree matrix of graph G minus the adjacency matrix.(Don’t know why…) Let’s write out the degree matrix and the adjacency matrix of a N-sides virus.

$$\textbf{D}_n = \begin{vmatrix}{N}&{\cdots}&{0}&{\cdots}&{0}&{0}\\ {0}&{3}&{\cdots}&{\cdots}&{0}&{0}\\ {0}&{\cdots}&{3}&{\cdots}&{0}&{0}\\ {0}&{\vdots}&{\vdots}&{3}&{0}&{0}\\ {\vdots}&{\vdots}&{\vdots}&{\vdots}&{\vdots}&{\vdots}\\ {0}&{0}&{0}&{0}&{\cdots}&{3}\\\end{vmatrix} \quad\quad\quad\quad\textbf{E}_n = \begin{vmatrix}{0}&{1}&{\cdots}&{1}&{\cdots}&{1}\\ {1}&{0}&{1}&{0}&{\cdots}&{1}\\ {1}&{1}&{0}&{1}&{0}&{\cdots}\\ {1}&{0}&{1}&{0}&{1}&{\cdots}\\ {\vdots}&{\vdots}&{\vdots}&{\vdots}&{\vdots}&{\vdots}\\ {1}&{1}&{0}&{\cdots}&{1}&{0}\\\end{vmatrix}$$