Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 7125  Solved: 3878

[][][]

Description

　　轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子

和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示

　　N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不

同的3轮状病毒，如下图所示

　　现给定n(N<=100)，编程计算有多少个不同的n轮状病毒

 

Input

　　第一行有1个正整数n

Output

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

Sample Input

3

Sample Output

16

HINT

题解：基尔霍夫矩阵（我也不知道是什么）推出f[i]=(f[i-1]*3-f[i-2]+2)；

代码：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define PAU putchar(' ') 8 #define ENT putchar('\n') 9 #define eps 1e-8 10 using namespace std; 11 const int maxn=105; 12 struct bign{ 13 int len,s[maxn]; 14 bign(){memset(s,0,sizeof(s));len=1;} 15 bign(int num){*this=num;} 16 bign(const char *num){*this=num;} 17 bign operator = (const int num){ 18 char s[maxn]; sprintf(s,"%d",num); 19 *this = s;return *this; 20 } 21 bign operator = (const char *num){ 22 for(int i=0;num[i]=='0';num++); 23 len=strlen(num); 24 for(int i=0;i
            
              1 && !s[len-1]) len--;return;} 38 bign operator * (const bign &b){ 39 bign c; 40 c.len=len+b.len; 41 for(int i=0;i
             
              =0) g=0; 52 else g=1,x+=10; 53 c.s[c.len++]=x; 54 } c.clean();return c; 55 } 56 bign operator / (const bign &b) { 57 bign c,f=0; 58 for(int i=len-1;i>=0;i--){ 59 f=f*10;f.s[0]=s[i]; 60 while(!(f
              
               =0;i--){ 71 if(s[i]!=b.s[i]) return s[i]
               
                 (const bign &b){ 75 if(len!=b.len) return len>b.len; 76 for(int i=len-1;i>=0;i--){ 77 if(s[i]!=b.s[i]) return s[i]>b.s[i]; 78 } return false; 79 } 80 bool operator == (const bign &b){ 81 return !(*this>b)&&!(*this
                
                 = (const bign &b){ 84 return (*this>b)||(*this==b); 85 } 86 void print(){ 87 for(int i=len-1;i>=0;i--) putchar(s[i]+'0');return; 88 } 89 }f[maxn]; 90 inline int read(){ 91 int x=0,sig=1;char ch=getchar(); 92 while(!isdigit(ch)){ if(ch=='-')sig=-1;ch=getchar();} 93 while(isdigit(ch))x=10*x+ch-'0',ch=getchar(); 94 return x*=sig; 95 } 96 inline void write(int x){ 97 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 98 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 99 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;100 }101 int n;102 void init(){103 n=read();f[1]=1;f[2]=5;104 return;105 }106 void work(){107 for(int i=3;i<=n;i++) f[i]=f[i-1]*3-f[i-2]+2;108 return;109 }110 void print(){111 f[n].print();112 return;113 }114 int main(){init();work();print();}