Description
给定n(N<=100)，编程计算有多少个不同的n轮状病毒。
Input
第一行有1个正整数n。
Output
将编程计算出的不同的n轮状病毒数输出
Sample Input
3
Sample Output
16
HINT
Source
Solution
基尔霍夫矩阵，左转生成树的计数及其应用
推出本题的递推式：f[n] = f[n - 1] * 3 - f[n - 2] + 2
如果你能看懂，拜托给我讲讲，本人不懂。
注意要使用高精度
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct bigint
{
int a[]; bigint()
{
memset(a, , sizeof(a));
} bigint operator + (int rhs)
{
bigint ans;
for(int i = ; i <= a[]; i++)
ans.a[i] = a[i];
ans.a[]++, ans.a[] += rhs;
for(int i = ; i < ans.a[]; i++)
{
ans.a[i + ] += ans.a[i] / ;
ans.a[i] %= ;
}
while(!ans.a[ans.a[]])
ans.a[]--;
return ans;
} bigint operator - (bigint rhs)
{
bigint ans;
ans.a[] = a[];
for(int i = ; i <= ans.a[]; i++)
ans.a[i] = a[i] - rhs.a[i];
for(int i = ; i < ans.a[]; i++)
if(ans.a[i] < )
{
ans.a[i] += ;
ans.a[i + ] -= ;
}
while(!ans.a[ans.a[]])
ans.a[]--;
return ans;
} bigint operator * (int rhs)
{
bigint ans;
ans.a[] = a[] + ;
for(int i = ; i <= ans.a[]; i++)
ans.a[i] = a[i] * rhs;
for(int i = ; i < ans.a[]; i++)
{
ans.a[i + ] += ans.a[i] / ;
ans.a[i] %= ;
}
while(!ans.a[ans.a[]])
ans.a[]--;
return ans;
} }f[]; int main()
{
int n;
cin >> n;
f[].a[] = , f[].a[] = ;
f[].a[] = f[].a[] = ;
for(int i = ; i <= n; i++)
f[i] = f[i - ] * - f[i - ] + ;
for(int i = f[n].a[]; i; i--)
cout << f[n].a[i];
cout << endl;
return ;
}