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 N = 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} $$
Then, we do a Laplace expansion on the determinant matrix R = D – E, we can find that 
Too lazy to write the complete proof… Then, we can just write a recursion to calculate the answer. If N = 1, we can see there is only 1 kind of virus. If N = 2, we can see that there is only 5 kinds of virus. Therefore, we have the following recursion formula.
$$\det{R}_n = \begin{cases}
1, &\textbf{N} = 1\\
5, &\textbf{N} = 2\\
3\det{R}_{n-1} – 2\det{R}_{n-2} + 2, &\textbf{N} > 2\\
\end{cases}$$
One thing to notice is that even long long cannot store the answer, so we need to write a BigNum class to store the answer.
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;
class BigNum{
public:
string str;
BigNum(){}
BigNum(string s):str(s){}
BigNum operator +(BigNum b){
string re = "";
string num_a = str;
string num_b = b.str;
int add = 0;
for(int i = num_a.size() - 1, j = num_b.size() - 1; j >= 0; i--,j--){
int a = num_a[i] - '0';
int b = num_b[j] - '0';
re.push_back((char)((a + b + add) % 10 + '0'));
if(a + b + add >= 10) add = 1;
else add = 0;
}
for(int i = num_a.size() - num_b.size() - 1; i >= 0; i--){
int a = num_a[i] - '0';
re.push_back((char)((a + add) % 10 + '0'));
if(a + add >= 10) add = 1;
else add = 0;
}
if(add) re.push_back(add + '0');
reverse(re.begin(),re.end());
return BigNum(re);
}
BigNum operator -(BigNum b){
string re = "";
string num_a = str;
string num_b = b.str;
bool flag = 1;
if(num_a.size() < num_b.size() || (num_a.size() == num_b.size() && num_a < num_b)) {swap(num_a,num_b); flag = 0;}
int minus = 0;
for(int i = num_a.size() - 1, j = num_b.size() - 1; j >= 0; i--,j--){
int a = num_a[i] - '0';
int b = num_b[j] - '0';
if(a - b - minus < 0){
re.push_back((char)((10 + a - b - minus) % 10 + '0'));
minus = 1;
}
else{
re.push_back((char)((a - b - minus) % 10 + '0'));
minus = 0;
}
}
for(int i = num_a.size() - num_b.size() - 1; i >= 0; i--){
int a = num_a[i] - '0';
if(a - minus < 0){
re.push_back((char) ((10 + a - minus) % 10 + '0'));
minus = 1;
}
else{
re.push_back((char)((a - minus) % 10 + '0'));
minus = 0;
}
}
while(re[re.size() - 1] == '0') re.erase(re.end() - 1);
reverse(re.begin(),re.end());
if(re.empty()) return BigNum(0);
return BigNum(re);
}
BigNum operator *(int mul){
string re = "";
string num_a = str;
int add = 0;
for(int i = str.size() - 1; i >= 0; i--){
int a = str[i] - '0';
re.push_back((char)((a * mul + add) % 10 + '0'));
if((a * mul + add) >= 10) add = (a * mul + add) / 10;
else add = 0;
}
if(add) re.push_back(add + '0');
reverse(re.begin(),re.end());
return BigNum(re);
}
void output(){
cout<<str<<endl;
}
};
BigNum ans[105];
int N;
int main(){
FAST_IO
cin>>N;
ans[1] = BigNum("1");
ans[2] = BigNum("5");
for(int i = 3; i <= N; i++) ans[i] = ans[i - 1] * 3 - ans[i - 2] + BigNum("2");
ans[N].output();
return 0;
}