至尊大法师——奇异博士，在与灭霸的战斗中，奇异博士幻化出了许多的分身，而奇异博士的分身有很多，但是奇异博士每次分身变换需要时间，为了帮助奇异博士打败灭霸，让我们帮他计算一下这些分身有多少个吧。
奇异博士是个怪人，他可以每一秒进行一次变换，每次分身后分身个数满足这样的一个序列：1,1,2,3,5,8,13,21,34……。（即第一秒是1个，第二秒是1个，第三秒是2个。。。）
给你一个数n，接下来有n次查询，对于每次查询输出经过第m秒钟后分身的个数。由于输出的数会很大，所以请输出结果的后四位即可，对于不足四位需要前补0。
在第一行输入一个数n，表示查询次数 (1<=n<=10000)
接下来有n行，每行有一个数m，表示第m秒钟 (1<=m<=10^6)
输出m秒钟后分身的结果，输出结果的后四位即可，对于不足四位需要前补0，每个输出占一行。
4
1
3
4
5
0001
0002
0003
0005
1表示第1秒钟后分身结果0001（当然是自身咯）
3表示第3秒钟后分身结果0002
4表示第4秒钟后分身结果0003
5表示第5秒钟后分身结果0005
(根据序列的变换得出第m秒钟后分身结果)
#include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<‘=‘<<(x)<<endl) using namespace std; typedef unsigned long long ll; typedef pair<int,int> pr; inline int read() {int x=0,f=1;char c=getchar();while(c!=‘-‘&&(c<‘0‘||c>‘9‘))c=getchar();if(c==‘-‘)f=-1,c=getchar();while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();return f*x;} const int maxn = 1e6+7; const int inf = 0x3f3f3f3f; const int mod = 1e8+7; const int M = 10000; int fb[maxn]; int main() { int t; fb[1]=fb[2]=1; for(int i=3;i<=maxn;i++){ fb[i]=fb[i-1]%M+fb[i-2]%M;//斐波那契打表 } scanf("%d",&t); while(t--){ int n; scanf("%d",&n); printf("%04d\n",fb[n]%M); } return 0; }
原文：https://www.cnblogs.com/lipu123/p/12163404.html