Revenge of Fibonacci
题意:给定fibonacci数列的前100000项的前n位(n<=40);问你这是fibonacci数列第几项的前缀？如若不在前100000项范围内，输出-1；
思路:直接使用数组模拟加法，再用Trie树插入查找即可；但是一般使用new Trie()的代码都是MLE的。反而我之前写的，直接得到数组大小的maxnode版本的内存可以接受；并且还有一点就是前40位的精度问题；由于是自己计算出来的finboncci数列，并不是系统给的，所以1的进位不会形成很长序列的递推，但是也不能只计算到40+位..代码中是计算到了前60位，然后只往Trie中传了40位，还有一点就是要维护前60位的值，即当位数增加时，逐渐地将末位舍去；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include<stack>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
typedef pair<int,int> PII;
#define A first
#define B second
#define MK make_pair
typedef __int64 ll;
template<typename T>
void read1(T &m)
{
T x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>) out(a/);
putchar(a%+'');
}
const int maxl = 1e5* + ;
const int sigma_size = ;
struct Trie{
int val[maxl],sz;
int ch[maxl][];
Trie(){sz = ;MS0(ch[]);}
void Insert(char *s,int v)
{
int u = ,len = strlen(s);
rep0(i,,len){
int c = s[i]-'';
if(ch[u][c] == ){
MS0(ch[sz]);
val[sz] = v;
ch[u][c] = sz++;
}
u = ch[u][c];
}
if(val[u] == ) val[u] = v;//不能直接覆盖;
}
int Find(char *s)
{
int u = ,len = strlen(s);
rep0(i,,len){
int c = s[i]-'';
if(ch[u][c] == ) return ;
u = ch[u][c];
}
return val[u];
}
}trie;
int a[],b[],c[];
void init()
{
char s[] = {''};
a[] = ;b[] = ;
trie.Insert(s,);
rep0(i,,){
int r = ,cnt = ;
rep1(j,,){
c[j] = a[j]+b[j]+r;
r = c[j]/;
c[j] = c[j]%;
}
int id = -;
rep_1(j,,){
if(id < && c[j]) id = j;
if(~id){
s[cnt++] = c[j]+'';
}
if(cnt >= ) break;
}
s[cnt] = '\0';
trie.Insert(s,i+);
if(id >= ){ //防止进位误差，舍去后面一位;
rep1(j,,)
c[j-] = c[j],b[j-] = b[j];
c[] = b[] = ;
}
rep1(j,,){
a[j] = b[j];
b[j] = c[j];
}
}
}
int main()
{
init();
int kase = ,T;
read1(T);
char str[];
while(T--){
scanf("%s",str);
printf("Case #%d: %d\n",kase++,trie.Find(str)-);
}
return ;
}