UVa12333 Revenge of Fibonacci

高精度 trie

暴力预处理出前100000个fibonacci数，将每个数的前40位数字串插入到trie中，记录每个结点最早可以由哪个数字串到达。

然后依次回答询问即可。

存fibonacci数的数组当然要滚动起来。

时限是10秒。本机试着卡了常数后跑了18秒（这个高精度写法好像本来就很慢），干脆交一波，UVA上7s AC

　　　　　　　　↑for循环i+=4 和直接一个register跑出来一样快，果然WC2017那道题只能在特定机子上做吗233

　　　　　　　　↑本机CPU是Intel I5-4590

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #include<cstdlib>

 #include<time.h>

 using namespace std;

 const int mxn=;

 struct Num{

     int x[];

     int len;

     friend Num operator + (Num a,Num b){

         a.len=max(a.len,b.len);

 //        printf("len:%d\n",a.len);

         int ed=a.len/*;

         for(int i=;i<=ed;i+=){

             a.x[i]+=b.x[i];

             a.x[i+]+=b.x[i+];

             a.x[i+]+=b.x[i+];

             a.x[i+]+=b.x[i+];

         }

         for(int i=ed+;i<=a.len;i++)

             a.x[i]+=b.x[i];

 //        for(register int i=1;i<=a.len;i++) a.x[i]+=b.x[i];

         for(int i=;i<=a.len;i++){

             if(a.x[i]>=){

                 a.x[i+]+=a.x[i]/;

                 a.x[i]%=;

             }

         }

         if(a.x[a.len+]) ++a.len;

         return a;

     }

 }a[];

 struct Trie{

     int t[][];

     int end[];

     int cnt,rt;

     void init(){

         memset(end,0x3f,sizeof end);

         cnt=rt=;

     }

     void insert(int id,Num a){

         int ed=a.len;

         int st=max(,a.len-+);//取高位40位

         int now=rt;

         for(int i=ed;i>=st;i--){

             if(!t[now][a.x[i]])t[now][a.x[i]]=++cnt;

             now=t[now][a.x[i]];

             end[now]=min(end[now],id);

         }

     }

     int query(char *s){

         int now=rt,len=strlen(s),tmp;

         for(int i=;i<len;i++){

             tmp=s[i]-'';

             if(!t[now][tmp])return -;

             now=t[now][tmp];

             if(end[now]>)return -;

         }

         return end[now];

     }

 }tr;

 void init(){

     a[].len=;a[].x[]=;

     a[].len=;a[].x[]=;

     tr.insert(,a[]);

     tr.insert(,a[]);

     for(int i=;i<;i++){

 //        printf("init:%d \n",i);

         int tmp=i&;

         a[tmp]=a[tmp]+a[tmp^];

 //        for(int j=1;j<=a[tmp].len;j++)printf("%d ",a[tmp].x[j]);

 //        printf("%d cnt:%d\n",i,tr.cnt);

         tr.insert(i,a[tmp]);

     }

     return;

 }

 char s[mxn];

 int n;

 int main(){

     int i,j;

 //    clock_t a=clock();

 //    printf("%d\n",a);

     tr.init();

     init();

 //    clock_t b=clock();

 //    printf("%d\n",b);

 //    printf("fin: %d \n",b-a);

     scanf("%d",&n);

     for(i=;i<=n;i++){

         scanf("%s",s);

         printf("Case #%d: %d\n",i,tr.query(s));

     }

     return ;

 }