[BZOJ 1002][FJOI2007]轮状病毒（高精+矩阵树定理？）

Description

---

　　轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子 和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示 　　N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不 同的3轮状病毒，如下图所示 　　现给定n(N<=100)，编程计算有多少个不同的n轮状病毒

Input

---

　　第一行有1个正整数n

Output

---

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

Sample Input

---

3

Sample Output

---

16

Solution

---

一开始觉得这题非常不可捉…不会矩阵树定理 然后去学了一下矩阵树定理（不学这个我好像连表都打不出来…弱 据说可以状压dp？） 嗯 打表找规律 你可以发现f[i]=f[i-1]*3-f[i-2]+2 然后加一个高精 证明= =不是很会啊 VFK这里有一个证明

#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #define MAXN 5000 #define Max(a,b) (a>b?a:b) using namespace std; struct Bign { int len,s[MAXN]; Bign() { memset(s,0,sizeof(s)); len=1; } Bign(int num){*this=num;} Bign(const char *num){*this=num;} void clean() {while(len>1&&!s[len-1])len--;} Bign operator = (const int num) { char s[MAXN]; sprintf(s,"%d",num); *this=s; return *this; } Bign operator = (const char *num){ len=strlen(num); for(int i=0;i<len;i++)s[i]=num[len-i-1]-'0'; } Bign operator - (const Bign& b) { Bign c;c.len=0; for(int i=0,g=0;i<len;i++) { int x=s[i]-g; if(i<b.len)x-=b.s[i]; if(x>=0)g=0; else g=1,x+=10; c.s[c.len++]=x; } c.clean(); return c; } Bign operator + (const int b) { s[0]+=b; int i=0,g=0; for(;i<len||g;i++) { s[i]+=g; g=s[i]/10; s[i]%=10; } len=i; return *this; } Bign operator * (const int b) { Bign c;c.len=0; for(int i=0,g=0;i<len||g;i++) { int x=g; if(i<len)x+=s[i]*b; g=x/10; c.s[c.len++]=x%10; } return c; } string str() const { string res; for(int i=0;i<len;i++) res=char(s[i]+'0')+res; return res; } }; ostream& operator << (ostream&out,Bign x) { out <<x.str(); return out; } Bign f[105]; int n; int main() { scanf("%d",&n); f[1]=1;f[2]=5; for(int i=3;i<=n;i++) { f[i]=f[i-1]*3-f[i-2]+2; } cout<<f[n]<<endl; return 0; }