传送门
思路
这是一个晴朗的上午，你正在机房里打比赛，突然发现了第二题是一个打印斐波那契数列。此时的你想到了最近学过的矩阵快速幂，感觉到了一丝恶心，但你还是下定决心开始切这道题……
时间过得真快，一转眼就过去了两转眼的时间，可是你的矩阵快速幂竟然打挂了。怎么办？就在你着急的时候，人类智慧来到了你的身旁，拍拍你的肩说：“何不打表找规律呢？”
此时的你猛然被厉害的人类智慧厉害到了，于是你开始打表。在你使用了大眼睛观察法找规律时，你突然发现，原来斐波那契数列模 \(100\) 的值以 \(300\) 为一周期，于是你瞬间恍然大悟。想到了存储前 \(300\) 位数的值，然后进行计算 \(1\sim r\) 的斐波那契值然后减去 \(1\sim l - 1\) 的值。最终，你自信的交上了一个十分短的代码，然后直接开下一题。
赛后，你发现这道题用打表的方法做竟然拿了满分，于是特写此题解以记之。
代码
#include<bits/stdc++.h>
#define int long long
#define inf (1ll << 62)
#define regint register int
#define pb push_back
#define mp make_pair
#define PII pair<int , int>
using namespace std;
const int MAXN = 500;
int T;
int a[MAXN] , s[MAXN];signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);a[1] = a[2] = 1;s[1] = 1;s[2] = 2;for(regint i = 3;i <= 300;i ++) {a[i] = (a[i - 1] + a[i - 2]) % 100;s[i] = s[i - 1] + a[i];}cin >> T;while(T --) {int l , r;cin >> l >> r;int l1 = (l - 1) / 300 * s[300] + s[(l - 1) % 300];int r1 = r / 300 * s[300] + s[r % 300];cout << r1 - l1 << '\n';}return 0;
}