题目链接：

思想很容易想到

就是预处理出前10w个的fib数，然后建树查询

建树时只用前40位即可，所以在计算时只用截取前60位

但是我在截取时总是出错

后来看了别人的代码改了一下就对了

不过还是不知道为什么那样是对的

更改地方在代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define maxn 110  6 using namespace std;  7 char  s[60];  8 char c[100];  9 char s1[maxn],s2[maxn],s3[maxn]; 10 void add(char *s1,char *s2, char *s3)//大数加 11 { 12     int len1=strlen(s1)-1; 13     int len2=strlen(s2)-1; 14     int up=0; 15     int x=0,y=0; 16     int k=0; 17     int z=0; 18     while(len1>=0 || len2>=0) 19     { 20         if(len1<0) x=0; 21         else x=s1[len1]-'0'; 22         if(len2<0) y=0; 23         else y=s2[len2]-'0'; 24  25         z=x+y+up; 26  27         c[k++]=z%10+'0'; 28         up=z/10; 29         len1--; 30         len2--; 31     }  32  33     if(up>0) c[k++]=up+'0'; 34     for(int i=0;i
         
          next[s[i]-'0']==NULL) 53      { 54        node *temp=new node; 55        for(int j=0;j<10;j++) 56             temp->next[j]=NULL; 57             temp->ID=-1; 58        p->next[s[i]-'0']=temp; 59  60      } 61     p=p->next[s[i]-'0']; 62  63     if(p->ID<0) p->ID=num; 64   } 65 } 66 void init() 67 { 68    node *q=root; 69    for(int i=0;i<10;i++) 70       q->next[i]=NULL; 71       q->ID=-1; 72     73    s1[0]='1';s1[1]='\0'; 74    s2[0]='1';s2[1]='\0'; 75  76    insert_node(s1,0); 77    insert_node(s2,1); 78  79  80   for(int i=2;i<100000;i++) 81   { 82      int len1=strlen(s1); 83      int len2=strlen(s2); 84      if(len2>60) // 防止进位出错，但是不知道为什么这样就可以防止了。。。。。 85      { 86         s2[len2-1]='\0'; 87         s1[len1-1]='\0'; 88      } 89  90      //我自己曾经的方法 91      /* 92         if(len2>60) s2[len2-1]='\0'; 93         if(len1>60) s1[len1-1]='\0'; 94   95      */ 96  97      add(s1,s2,s3); 98      insert_node(s3,i); 99 100      strcpy(s1,s2);101      strcpy(s2,s3);102 103   }104 }105 int find(char *s)106 {107   node* q=root;108   int num;109   int len=strlen(s);110   for(int i=0;i
          
           next[d]==NULL) return -1;115 else116 {117 q=q->next[d];118 num=q->ID;119 }120 }121 return num;122 }123 void del_node(node *p)124 {125 for(int i=0;i<10;i++)126 {127 if(p->next[i]!=NULL)128 del_node(p->next[i]);129 130 }131 free(p);132 133 }134 int main()135 {136 int t;137 init();138 139 scanf("%d",&t);140 int iCase=0;141 while(t--)142 {143 144 scanf("%s",s);145 printf("Case #%d: %d\n",++iCase,find(s)); 146 }147 del_node(root);148 return 0;149 }