杭電1715大斐波数

転送ゲート:http://acm.hdu.edu.cn/showproblem.php?pid=1715
大斐波数
Time Limit：1000/1000 MS(Java/Others)Memory Limit：32768/32768 K(Java/Others)Total Submission(s)：25234 Accepted Submission(s)：9041 Proble m Description
Fibonacci数列は、f（1）＝f（2）＝1 f（n）＝f（n−1）＋f（n−2）n＞＝3と定義されている。n番目のFibonacci値を計算します。
Input
第一の行為の整数Nを入力して、次にN行の整数Pi（1<=Pi<=1000）を行います。
Output
出力はN行で、各動作に対応するf（Pi）です。
Sample Input

5
1
2
3
4
5

Sample Output

1
1
2
3
5

分析
フィボナッチの数列を簡単に解くことですが、大きな数の演算が必要です。戻り値を持つ関数を書いて、大きな数の演算を解きます。戻り値は大きな数の文字列を保存して、結果を求めるまで繰り返します。注意したいのは本題はメーターを押す必要があります。でないと時間がオーバーします。
答えを参考にする

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
int n;
string bigaad(string s,string c)//     
{
	int i,j,a,b;
	int p[1000],q[1000];
	string str,t;            
    a=s.size();
	b=c.size();
	memset(p,0,sizeof(p));           //        ，   0；
	memset(q,0,sizeof(q));           //        ，   0;
	for(i=0,j=a-1;i<a;i++,j--)
	{
		p[i]=s[j]-'0';
	}
	for(i=0,j=b-1;i<b;i++,j--)
	{
		q[i]=c[j]-'0';
	}
	n=a>b?a:b;
	for(i=0;i<n;i++)
	{
		p[i]=p[i]+q[i];
		if(p[i]>9)
		{
			if(i==n-1)
				n++;            //    (     )
			p[i]=p[i]-10;
			p[i+1]+=1;
		}
	}
	for(i=n-1,j=0;i>=0;i--,j++)        //    
	{
	    t=p[i]+'0';
	   	str.append(t);                 //       
	}
    return str;
}
int main()
{
	string str_1,str_2,str;
	int N,i,k;
	vector<string> v; 
	v.push_back("1");
	v.push_back("1");
	scanf("%d",&N);
	while(N--)
	{
		scanf("%d",&k);
		if(k<=v.size())
		{
			cout<<v[k-1]<<endl;
			continue;
		}
		k=k-v.size();
		while(k--)
		{
	    	str=bigaad(v[v.size()-1],v[v.size()-2]);
			v.push_back(str);                           //  v     
	    	str_1=str_2; 
	    	str_2=str;
	    }
		for(i=0;i<n;i++)
		    printf("%c",str[i]);
	    printf("
");
	}
	return 0;
}