题面
给定数列 1,1,1,3,5,9,17,⋯，从第 4 项开始，每项都是前 3 项的和。
求第 20190324 项的最后 4 位数字。
题解
数学，斐波那契数列
题目只要求知道结果的后四位数字，则每次求和运算完成直接模掉 10000 保留最后四位数字即可。
由于数组开不到 20190324 那么大，这里使用状态压缩数组进行替换，f[i % 3] 表示第 i + 1 项的结果。
注意： 此题不能直接使用 long long 类型进行累加计算，在达到 70项的时候，就已经超出了 long long 的数据范围了，只能借助 模 10000 来快速解决。
答案：
4659
代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e4;
int f[3] = {1, 1, 1};
int main() {
int n = 20190324;
for (int i = 3; i < n; i++) {
f[i % 3] = (f[0] + f[1] + f[2]) % MOD;
}
cout << f[(n - 1) % 3] << endl;
return 0;
}
| 标题： | 2019年第十届蓝桥杯省赛-C.数列求值 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/213 |
| 更新： | 2022-09-18 22:48:45 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |