3、数列求值

题目 数列求值

image-0862e1de

思路分析

简单dp（斐波那契）

注意溢出问题 开long long每轮模上10000

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e8+10;

LL f[N];

int main()

{

	f[1]=f[2]=f[3]=1;

	for(LL i=4;i<=20200000;i++){

		f[i]=(f[i-1]+f[i-2]+f[i-3])%10000;

		cout<<f[i]<<" ";

	}

	cout<<f[20190324]%10000;

	return 0;

 }

可以用变量滚动优化 但是怕出错

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()

{

    LL a=1, b=1, c=1, next;

    for(LL i=4; i<=20190324; ++i){

        next = (a + b + c) % 10000;

        a = b;

        b = c;

        c = next;

    }

    cout << c;

    return 0;

}

如果还是担心越界出错的问题 这种简单填空题可以用py写一下

image-f507c2ea

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()

{

    LL a=1, b=1, c=1, next;

    for(LL i=4; i<=20190324; ++i){

        next = (a + b + c) % 10000;

        a = b;

        b = c;

        c = next;

    }

    cout << c;

    return 0;

}

同类题型

视频讲解

⬅️ 2、年号字串 🏠 00-刷题理模型 ➡️ 4、数的分解