Eva

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 7798  Solved: 4233
Description

　　轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子
和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示

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

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

Input

　　第一行有1个正整数n

Output 

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

Sample Input

3

Sample Output

16

f[n]=3∗f[n−1]−f[n−2]+2

  

/**************************************************************

    Problem: 1002

    User: ictsing

    Language: C++

    Result: Accepted

    Time:0 ms

    Memory:1292 kb

****************************************************************/

 

//求轮状病毒，类似于生成树一样的东西

/*

首先暴搜，然后打表发现规律

命令行编辑的时候手抽代码都不见了，重新写一遍吧QAQ

1

5

16

45

121

320

841

2205

5776

15125

39601

103680

271441

 

1*1

          5*1*1   

4*4     

          5*3*3    

11*11    

          5*8*8     

29*29     

          5*21*21     

76*76     

          5*55*55     

199*199     

          5*144*144     

521*521

 

1 (1) 2 (3) 5 (8) 13 (21) 34 (55) 89 (144)

(1) 3 (4) 7 (11) 18 (29) 47 (76) 123 (199) 322 (521)

大概就是类似于斐波那契数一样的加就可以了

高精度搞一搞233333

*/

/*

#include <iostream>

#include <cstdio>

using namespace std;

const int mt = 100+5;

struct edge{

  int l,r;

}e[mt];

int n;

int f[mt],tmp[mt];

int getfa(int x)

{

  if(f[x]==x) return x;

  return f[x]=getfa(f[x]);

}

int ans;

bool flag[mt];

void dfs(int x,int ed)

{

  if(x==n+1) {ans++;return ;}

  int tmp[mt];

  for(int i=ed+1;i<=n*2;i++)

    if(!flag[i])

  {

    int a=getfa(e[i].l);

    int b=getfa(e[i].r);

        if(a==b) continue;

        for(int j=0;j<=n;j++) tmp[j]=f[j];

        f[a]=b,flag[i]=true,dfs(x+1,i);

        for(int j=0;j<=n;j++) f[j]=tmp[j];

        flag[i]=false;

  }

}

int main()

{

  for(n=1;n<=15;n++)

  {

      ans=0;

      for(int i=1;i<n;i++)

       e[i].l=i,e[i].r=i+1;

       e[n].l=n,e[n].r=1;

      for(int i=n+1;i<=n+n;i++)

       e[i].l=0,e[i].r=i-n;

     for(int i=0;i<=n;i++) f[i]=i;

      dfs(1,0);

      printf("%d\n",ans);

  }

  return 0;

}

*/

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int mt =50+1;

struct arr{

  int num,p[mt];

}a,b,c;

arr add(arr a,arr b)

{

  arr c;memset(c.p,0,sizeof(c.p));

  c.num=max(a.num,b.num);

  for(int i=1;i<=c.num;i++)

    c.p[i]=a.p[i]+b.p[i];

  for(int i=1;i<=c.num;i++)

    c.p[i+1]+=c.p[i]/10,c.p[i]%=10;

  if(c.p[c.num+1]) c.num++;

  return c;

}

arr multi(arr a,arr b)

{

  arr c;memset(c.p,0,sizeof(c.p));

  for(int i=1;i<=a.num;i++)

    for(int j=1;j<=b.num;j++)

      c.p[i+j-1]+=a.p[i]*b.p[j];

    c.num=a.num+b.num-1;

    for(int i=1;i<=c.num;i++)

      c.p[i+1]+=c.p[i]/10,c.p[i]%=10;

    while(c.p[c.num+1])

      c.num++,c.p[c.num+1]+=c.p[c.num]/10,c.p[c.num]%=10;

    return c;

}

inline int read()

{

  int num=0,flag=1;

  char ch;

  do{

    ch=getchar();

    if(ch=='-') flag=-1;

  }while(ch<'0'||ch>'9');

  do{

    num=num*10+ch-'0';

    ch=getchar();

  }while(ch>='0'&&ch<='9');

  return num*flag;

}

int main()

{

  int n=read();

  if(n==0) puts("0");

  else if(n==1) puts("1");

  else if(n==2) puts("5");

  else if(n&1)

  {

    a.p[1]=1;b.p[1]=3;a.num=1;b.num=1;  

    for (int i=3;i<=n;i++)  

    {  

      c=add(a,b);  

      a.num=b.num;for (int j=1;j<=a.num;j++) a.p[j]=b.p[j];  

      b.num=c.num;for (int j=1;j<=b.num;j++) b.p[j]=c.p[j];  

    }  

    c=multi(c,c);  

    for (int i=c.num;i>0;i--)  

      printf("%d",c.p[i]);  

  }

  else

  {

    a.p[1]=1,b.p[1]=2,a.num=1,b.num=1;

    for(int i=4;i<=n;i++)

    {

      c=add(a,b);

      a.num=b.num;for(int j=1;j<=a.num;j++) a.p[j]=b.p[j];

      b.num=c.num;for(int j=1;j<=b.num;j++) b.p[j]=c.p[j];

    }

    c=multi(c,c);

    memset(a.p,0,sizeof(a.p));a.p[1]=5,a.num=1;c=multi(c,a);

    for(int i=c.num;i>0;i--)

      printf("%d",c.p[i]);

  }

  return 0;

}