HDU 4099 Revenge of Fibonacci(高精度+字典树) - c++编程基础

题意：对给定前缀（长度不超过40），找到一个最小的n，使得Fibonacci（n）前缀与给定前缀相同，如果在[0,99999]内找不到解，输出-1。

思路：用高精度加法计算斐波那契数列，因为给定前缀长度不超过40，所以高精度计算时每次只需保留最高60位，每次将得到的值插入到字典树中，使得树上每个节点只保留最小的n值。查询输出字典树结点的值。

#include  
#include  
#include  
#define MAXNLEN 80  
#define LEN 60  
using namespace std;  
  
struct bign  
{  
    int d[MAXNLEN],len;  
};  
  
void add(bign & a,bign & b,bign & c)  
{  
    c.len=max(a.len,b.len);  
    int carry=0;  
    for(int i=0;iLEN)  
    {  
        for(int i=0;i




=max(s.len-41,0);--i)  
        {  
            int c=s.d[i];  
            if(!ch[u][c])  
            {  
                memset(ch[sz],0,sizeof(ch[sz]));  
                if(val[sz]==-1) val[sz]=v;  
                ch[u][c]=sz++;  
            }  
            u=ch[u][c];  
        }  
    }  
  
    int find(char *s)  
    {  
        int u=0;  
        for(int i=0;s[i];++i)  
        {  
            int c=s[i]-'0';  
            if(!ch[u][c]) return -1;  
            u=ch[u][c];  
        }  
        return val[u];  
    }  
}trie;  
  
void init()  
{  
    tmp[0].len=tmp[1].len=1,tmp[0].d[0]=tmp[1].d[0]=1;  
    trie.insert(tmp[1],0);  
    for(int i=2;i<100000;++i)  
    {  
        add(tmp[(i+2)%3],tmp[(i+1)%3],tmp[i%3]);  
        trie.insert(tmp[i%3],i);  
    }  
}  
int T,ca=0;  
char st[MAXNLEN];  
int main()  
{  
    init();  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%s",st);  
        printf("Case #%d: %d\n",++ca,trie.find(st));  
    }  
    return 0;  
}