50分玄关

lizishi @ 2024-07-30 15:20:44

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n + 10] = {0};
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2];
    }
    cout << a[n];
    return 0;
}

by wzt2012 @ 2024-07-30 15:21:45

要高精度

by syex_luoyukai @ 2024-07-30 15:22:33

对于 100% 的数据，1≤N≤5000 1≤N≤5000。

by 枫原万叶 @ 2024-07-30 15:23:47

@lizishi 高精代码，数据太大，long long都不行

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
int a[6000][3001];
void P(int a[],int b[],int temp[])
{
    int len1=2000,len2=2000,i;
    while(!a[len1]) len1--; 
    while(!b[len2]) len2--;
    int len=max(len1,len2);
    for(i=1;i<=len;i++) temp[i]=a[i]+b[i];
    for(i=1;i<=len+1;i++)
    {
        temp[i+1]+=temp[i]/10;
        temp[i]%=10;
    }
    return;
}
int main()
{
    cin>>n;
    n++;
    if(n==0)
    {
        cout<<0<<endl;
        return 0;
    }
    a[1][1]=1;
    n++;
    for(int i=2;i<=n+1;i++)
    {
        P(a[i-1],a[i-2],a[i]);
    }
    int len=2000;
    while(!a[n][len]) len--;
    while(len) {cout<<a[n][len];len--;}
    return 0;
}