题目描述
算法1
使用数组处理该数列,并在存储时进行取模
for (int i = 3; i <= n; i++) {
a[i] = (a[i - 1] + a[i - 2]) % mod;
}
最后调用数组进行累加取模
for (int i = 1; i <= n; i++){
sum = (sum + a[i]) % mod;
}
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10 ;
const long long mod = 1e11 + 3 ;
int n;
ll a[N];
ll sum;
int main() {
scanf("%d", &n);
a[1] = 1, a[2] = 3;
for (int i = 3; i <= n; i++) {
a[i] = (a[i - 1] + a[i - 2]) % mod;
}
for (int i = 1; i <= n; i++){
sum = (sum + a[i]) % mod;
}
printf("%lld", sum);
return 0;
}