# 3076. 斐波那契数列

#include <stdio.h>
int main(void)
{
int T;
scanf("%d",&T);
int i, j, fib[121][27], n;
for(i=0; i<121; i++) for(j=0; j<27; j++) fib[i][j]=0;
fib[1][0]=1;
for(i=2; i<121; i++)
for(j=0; j<26; j++)
{
fib[i][j]+=(fib[i-1][j]+fib[i-2][j]);
fib[i][j+1]=fib[i][j]/10;
fib[i][j]%=10;
}
for(i=0; i<T; i++)
{
scanf("%d",&n);
printf("case #%d:\n",i);
for(j=26; j+1; j--)
if(fib[n][j]) break;
for(;j+1; j--)
printf("%d",fib[n][j]);
if(n==0) printf("0");
printf("\n");
}
return 0;
}


dp = [-1 for i in range(125)]
def F(n):
if(n == 0): return 0
if(n == 1 or n == 2): return 1
if(dp[n] != -1):
return dp[n]
else:
dp[n] = F(n-1) + F(n-2)
return dp[n]

T = int(input())
for i in range(T):
n = int(input())
print("case #%d:"%i)
print(F(n))


### include

using namespace std;
typedef vector BIG;
vector V;
int T;

BIG create(int aa)
{
BIG ret;
ret.push_back(aa);
while(ret[ret.size()-1]>=10)
{
int top=ret.size()-1;
ret.push_back(ret[top]/10);
ret[top]%=10;
}
return ret;
}
BIG operator+(const BIG& aa,const BIG& bb)
{
BIG ret;
for(int i=0;ibb.size())
for(int i=bb.size();i<aa.size();i++) ret.push_back(aa[i]);
else if(aa.size()<bb.size())
for(int i=aa.size();i=10) { int top=ret.size()-1; ret.push_back(ret[top]/10); ret[top]%=10; } return ret; } void print(const BIG& aa) { for(int i=aa.size()-1;i>=0;i–) cout<<aa[i];
cout<<endl;
return;
}
void init()
{
V.push_back(create(0));
V.push_back(create(1));
for(int i=2;i<=120;i++) V.push_back(V[V.size()-1]+V[V.size()-2]);
return;
}
void solve()
{
int n;
cin>>n;
print(V[n]);
return;
}
int main()
{
scanf(“%d”,&T);
init();
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

### include

using namespace std;
int plu(char s1[],char s2[],char s3[],int l1,int l2)
{
int cnt=0;
int jin=0;

while(l1>=0&&l2>=0)
{
int num=s1[l1]-'0'+s2[l2]-'0'+jin;
jin=num/10;
num=num%10;
s3[cnt]=num+'0';
cnt++;
l1--,l2--;
}
while(l1>=0)
{
int num=s1[l1]-'0'+jin;
jin=num/10;
num=num%10;
s3[cnt]=num+'0';
cnt++;
l1--;
}
while(l2>=0)
{
int num=s2[l2]-'0'+jin;
jin=num/10;
num=num%10;
s3[cnt]=num+'0';
cnt++;
l2--;
}
if(jin!=0) s3[cnt++]=jin+'0';

return cnt-1;


}
void solve()
{
char s1[50],s2[50],s3[50];
strcpy(s1,”0”);
strcpy(s2,”1”);
int l1=strlen(s1)-1,l2=strlen(s2)-1;
int l3;
int n;
cin>>n;
if(n==0) cout<<s1<<endl;
else if(n==1) cout<<s2<<endl;
else{
for(int i=2;i<=n;i++)
{l3=plu(s1,s2,s3,l1,l2);
for(int i1=0;i1<=l2;i1++) s1[i1]=s2[i1];
for(int i1=0;i1<=l3;i1++) s2[i1]=s3[l3-i1];
l1=l2;
l2=l3;
}
for(l3;l3>=0;l3–) cout<<s3[l3];
cout<>T;
for(int i=0;i<T;i++)
{
printf(“case #%d:\n”,i);
solve();
}
}