问题标题: 酷町堂：2744   斐波那契数列2

题目链接： 酷町堂：2744

2744   斐波那契数列2

经验值：1200 时间限制：1000毫秒 内存限制：128MB

题目描述 De**ion

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。 给出一个正整数n，要求菲波那契数列中第n个数是多少。n不超过1000

输入描述 Input De**ion

一行：一个正整数n，n不超过1000

输出描述 Output De**ion

个正整数，表示菲波那契数列中第n个数是多少

样例输入 Sample Input

5

样例输出 Sample Output

5

#include <bits/stdc++.h>
using namespace std;
char x[1200];
int s,n,sum,a[1200],b[1200];
string s1,s2;
int main(){
    cin>>n;
    s1="1";
    s2="1";
    for(int j=2;j<n;j++){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        a[0]=s1.size();
        b[0]=s2.size();
        for(int i=1;i<=a[0];i++){
            a[i]=s1[a[0]-i]-'0';
        }
        for(int i=1;i<=b[0];i++){
            b[i]=s2[b[0]-i]-'0';
        }
        sum=max(a[0],b[0]);
        for(int i=1;i<=sum;i++){
            a[i]+=b[i];
            a[i+1]=a[i]/10;
            a[i]%=10;
        }
        sum++;
        while((a[sum]==0)&&(sum>1)){
            sum--;
        }
        s=0;
        for(int i=sum;i>=1;i--){
            x[s]=a[i]+'0';
            s++;
        }
        s1=s2;
        s2=x;
    }
    cout<<s2<<endl;
    return 0;
}