蓝桥杯第十届 数列求值
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
给定数列 1,1,1,3,5,9,17,⋯从第 4 项开始，每项都是前 3 项的和。
求第 20190324 项的最后 4 位数字。
-
模运算的分配律：
根据模运算性质，有：(a + b + c) mod m = [(a mod m) + (b mod m) + (c mod m)] mod m因此，无论先计算总和再取模，还是每一步都取模，最终结果一致。
-
防止溢出的必要性：
原始数列增长极快（类似三阶斐波那契），第20190324项的值远超long long的范围（约±9e18）。不取模会导致数值溢出，得到错误结果。
#include<iostream>
using namespace std;
int a[20200000]={0, 1, 1, 1}; //这里不能用long long，会超时
int ans;
const int MOD = 10000;
int main()
{
for(int i=4; i<=20190324; ++i)
{
//每一步都取模防止溢出
a[i] = (a[i-1] + a[i-2] + a[i-3]) % MOD;
}
ans = a[20190324]%MOD;
cout<<ans;
return 0;
}