思路：用字典树将前40个数字记录下来，模拟大数加法即可。
AC代码
#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000")#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int>typedef long long LL;const int maxn = 10;struct Node{int num;Node *next[maxn];Node(){num = -1;for(int i = 0; i < maxn; i++) {next[i] = NULL;}}}*root;void init() {root = new Node();}void insert(int *a, int n, int num) {n = min(n, 40);Node *p = root, *q;for(int i = 0; i < n; ++i) {int x = a[i];if(p->next[x] == NULL) {q = new Node();q->num = num;p->next[x] = q;}p = p->next[x];}}int find(char *a) {Node *p = root;int n = strlen(a);for(int i = 0; i < n; ++i) {int x = a[i] - '0';if(p->next[x] == NULL) return -1;p = p->next[x];}return p->num;} //高精度加法const int Base = 100000000;int a[2][20000+5], val[100];int f = 0, h = 1;stack<int>sta;void Deal() {memset(a, 0, sizeof(a));a[0][0] = 1, a[1][0] = 1;val[0] = 1;int len[2] = {1,1};insert(val, 1, 0);for(int i = 2; i < 100000; ++i) {int g = 0;for(int j = 0; j < len[f] || j < len[h] || g > 0; ++j) {int x = a[f][j] + a[h][j] + g;a[f][j] = x % Base;g = x / Base;len[f] = max(len[f], j+1);}int cur = 0;for(int j = len[f]-1; j >= 0; --j) {if(cur >= 40) break;int x = a[f][j];if(j == len[f] - 1) {while(x) {sta.push(x % 10);x /= 10;}}else {int u = 0, t = x;while(t) {++u;t /= 10;}while(x) {sta.push(x % 10);x /= 10;}for(int k = 0; k < 8 - u; ++k) {sta.push(0);}}while(!sta.empty()) {val[cur++] = sta.top();sta.pop();}}//insertinsert(val, cur, i);f = 1 - f;h = 1 - h;}}int main() {init();Deal();int T, kase = 1;scanf("%d", &T);char s[50];while(T--) {scanf("%s", s);printf("Case #%d: %d\n", kase++, find(s));}return 0;}
如有不当之处欢迎指出！
