题目链接：
https://www.lydsy.com/JudgeOnline/problem.php?id=1002
题目大意：
给定n(N<=100)，编程计算有多少个不同的n轮状病毒
思路：
大部分题解都是直接一个递推公式，具体得来的方法由矩阵树定理可以求得。
只是求矩阵的行列式的时候比较复杂。
具体证明过程：http://vfleaking.blog.163.com/blog/static/17480763420119685112649/
需要高精度
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);//不可再使用scanf printf
#define Max(a, b) (a) > (b) ? (a) : (b)
#define Min(a, b) (a) < (b) ? (a) : (b)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std; typedef long long ll;
const int mod = 1e9 + ;
const int maxn = + ; #define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
//如果位数特别大，可以把数组a放大，也可以把MAXN多加几个9，同时DLEN = 9的个数 后者方法会更快
class BigNum {
private:
public:
ll a[]; //可以控制大数的位数
int len; //大数长度 BigNum() {len = ;memset(a,,sizeof(a));} //构造函数
BigNum(const ll); //int 构造函数
BigNum(const char*); //字符串 构造函数
BigNum(const string); //string 构造函数
BigNum(const BigNum &); //拷贝构造函数
BigNum &operator=(const BigNum &);//重载赋值运算符 friend istream& operator >> (istream&, BigNum&);//重载输入运算符
friend ostream& operator << (ostream&, BigNum&);//重载输出运算符 BigNum operator + (const BigNum &) const;//重载加法
BigNum operator - (const BigNum &) const;//重载减法
BigNum operator * (const BigNum &) const;//重载乘法
BigNum operator / (const ll &) const; //重载除法 int
BigNum operator ^ (const ll &) const; //n次方
ll operator % (const ll &) const; //对int 取模 bool operator > (const BigNum & T)const; //比较大小
bool operator > (const ll & t)const;
bool operator < (const BigNum & T)const;
bool operator < (const ll & t)const;
bool operator == (const BigNum & T)const;
bool operator == (const ll & t)const; void print(); //输出大数
};
BigNum::BigNum(const ll b) //int 构造函数
{
ll c, d = b;
len = ;
memset(a,,sizeof(a));
while(d > MAXN)
{
c = d - (d / (MAXN + )) * (MAXN + );
d = d / (MAXN + ); a[len++] = c;
}
a[len++] = d;
}
BigNum::BigNum(const char*s)//字符串 构造函数
{
ll t, k, index, l;
memset(a,,sizeof(a));
l = strlen(s);
len = l / DLEN;
if(l % DLEN)len++;
index=;
for(int i = l - ; i >= ;i -= DLEN)
{
t = ; k = i - DLEN + ;
if(k < )k = ;
for(int j = k; j <= i; j++)
t = t * + s[j] - '';
a[index++]=t;
}
}
BigNum::BigNum(const string s)//字符串 构造函数
{
ll t, k, index, l;
memset(a,,sizeof(a));
l = s.size();
len = l / DLEN;
if(l % DLEN)len++;
index=;
for(int i = l - ; i >= ;i -= DLEN)
{
t = ; k = i - DLEN + ;
if(k < )k = ;
for(int j = k; j <= i; j++)
t = t * + s[j] - '';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum & T) : len(T.len)//拷贝构造函数
{
memset(a,,sizeof(a));
for(int i = ; i < len ; i++)a[i] = T.a[i];
}
BigNum & BigNum::operator = (const BigNum & n)//重载赋值运算符
{
len = n.len;
memset(a,,sizeof(a));
for(int i = ; i < len ; i++)
a[i] = n.a[i];
return *this;
}
istream& operator >> (istream & in, BigNum & b)//重载输入运算符
{
char ch[MAXSIZE * ];
in >> ch;
int l = strlen(ch);
ll count = , sum = ;
for(int i = l - ; i >= ;)
{
sum = ;
ll t = ;
for(int j = ; j < DLEN && i >= ; j++, i--, t *= )
sum += (ch[i] - '') * t;
b.a[count] = sum;
count++;
}
b.len = count++;
return in;
}
ostream& operator << (ostream& out, BigNum& b)//重载输出运算符
{
cout<<b.a[b.len - ];
for(int i = b.len - ; i >= ; i--)
{
cout.width(DLEN);
cout.fill('');
cout<<b.a[i];
}
return out;
}
BigNum BigNum::operator + (const BigNum & T) const //重载加法
{
BigNum t(*this);
ll i,big;//位数
big = T.len > len ? T.len : len;
for(i = ; i < big ; i++)
{
t.a[i] +=T.a[i];
if(t.a[i] > MAXN)
{
t.a[i + ]++;
t.a[i] -= MAXN + ;
}
}
if(t.a[big] != ) t.len = big + ;
else t.len = big;
return t;
}
BigNum BigNum::operator - (const BigNum & T) const //重载减法
{
ll i,j,big;
bool flag;
BigNum t1,t2;
if(*this > T)
{
t1 = *this;
t2 = T;
flag = ;
}
else
{
t1 = T;
t2 = *this;
flag = ;
}
big = t1.len;
for(i = ; i < big ; i++)
{
if(t1.a[i] < t2.a[i])
{
j = i + ;
while(t1.a[j] == ) j++;
t1.a[j--]--;
while(j > i) t1.a[j--] += MAXN;
t1.a[i] += MAXN + - t2.a[i];
}
else t1.a[i] -= t2.a[i];
}
t1.len = big;
while(t1.a[t1.len - ] == && t1.len > )
{
t1.len--;
big--;
}
if(flag)t1.a[big - ] = - t1.a[big - ];
return t1;
}
BigNum BigNum::operator * (const BigNum & T) const //重载乘法
{
BigNum ret;
ll i,j,up;
ll temp,temp1;
for(i = ; i < len ; i++)
{
up = ;
for(j = ; j < T.len ; j++)
{
temp = a[i] * T.a[j] + ret.a[i + j] + up;
if(temp > MAXN)
{
temp1 = temp - temp / (MAXN + ) * (MAXN + );
up = temp / (MAXN + );
ret.a[i + j] = temp1;
}
else
{
up = ;
ret.a[i + j] = temp;
}
}
if(up != )
ret.a[i + j] = up;
}
ret.len = i + j;
while(ret.a[ret.len - ] == && ret.len > ) ret.len--;
return ret;
}
BigNum BigNum::operator / (const ll & b) const //重载除法
{
BigNum ret;
ll i,down = ;
for(i = len - ; i >= ; i--)
{
ret.a[i] = (a[i] + down * (MAXN + )) / b;
down = a[i] + down * (MAXN + ) - ret.a[i] * b;
}
ret.len = len;
while(ret.a[ret.len - ] == && ret.len > ) ret.len--;
return ret;
}
ll BigNum::operator % (const ll & b) const //重载取模
{
ll i,d=;
for (i = len-; i>=; i--)
{
d = ((d * (MAXN+))% b + a[i])% b;
}
return d;
}
BigNum BigNum::operator^(const ll & n) const //重载n次方
{
BigNum t,ret();
if(n < )exit(-);
if(n == )return ;
if(n == )return *this;
ll m = n;
while(m > )
{
t = *this;
ll i;
for(i = ; i << <= m; i <<= )
{
t = t * t;
}
m -= i;
ret = ret * t;
if(m == )ret = ret * (*this);
}
return ret;
}
bool BigNum::operator > (const BigNum & T) const //两大整数 大于号重载
{
ll ln;
if(len > T.len) return true;
else if(len == T.len)
{
ln = len - ;
while(a[ln] == T.a[ln] && ln >= ) ln--;
if(ln >= && a[ln] > T.a[ln]) return true;
else return false;
}
else return false;
}
bool BigNum::operator > (const ll & t) const
{
return *this > BigNum(t);
}
bool BigNum::operator < (const BigNum & T) const //两大整数 小于号重载
{
return T > *this;
}
bool BigNum::operator < (const ll & t) const
{
return BigNum(t) > *this;
}
bool BigNum::operator == (const BigNum & T) const //两大整数 等于号重载
{
return !(T > *this) && !(*this > T);
}
bool BigNum::operator == (const ll & t) const
{
return BigNum(t) == *this;
}
void BigNum::print()
{
int i;
cout << a[len - ];
for(i = len - ; i >= ; i--)
{
cout.width(DLEN);
cout.fill('');
cout << a[i];
}
} int main()
{
int n;
cin >> n;
if(n == )puts("");
else if(n == )puts("");
else
{
BigNum a(), b(), c;
for(int i = ; i <= n; i++)
{
c = BigNum(3LL) * b;
c = c - a;
c = c + BigNum(2LL);
a = b;
b = c;
}
cout<<c<<endl;
}
return ;
}