题解 SP8001 【FIBOSUM - Fibonacci Sum】
rui_er
2020-08-18 14:17:01
我也不知道我怎么找到的这题，但是既然 AC 了，就来写一篇题解。
题意简述：共 $T$ 组询问，每次读入两个数 $n,m$，输出 $\displaystyle\sum_{i=n}^ma_i\mod (10^9+7)$ 的值，其中 $a_i$ 为斐波那契数。
---
由于洛谷爬的时候漏掉了数据范围，可以到原题目中查看：$T\le 10^3,0
\le n\le m\le 10^9$，可以看到暴力求出所有斐波那契数的前缀和后求解显然会超时，容易想到矩阵加速。
我们使用矩阵维护第 $i$ 项、第 $i+1$ 项的值及前 $i$ 项的和，下面考虑构造转移矩阵。
根据斐波那契数列的定义，我们知道：
$$\begin{cases}a_{i+1}=&a_{i+1}\\a_{i+2}=&a_{i}+a_{i+1}\\s_{i+1}=&s_i+a_{i+1}\end{cases}$$
经过一些简单变换即可得到转移矩阵：
$$\begin{bmatrix}a_i&a_{i+1}&s_i\end{bmatrix}\times\begin{bmatrix}0&1&0\\1&1&1\\0&0&1\end{bmatrix}=\begin{bmatrix}a_{i+1}&a_{i+2}&s_{i+1}\end{bmatrix}$$
此时，我们可以通过类似于题目[矩阵加速](/problem/P1939)的方式利用矩阵快速幂在 $\log$ 时间内求出对于一个整数 $k$ 的 $s_k$ 的值。我们要求的答案即为 $s_m-s_{n-1}\mod (10^9+7)$。
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll T, n, m;
struct Matrix {
ll id[4][4];
Matrix() {}
Matrix(int x, int y, int z) {id[1][1]=x;id[1][2]=y;id[1][3]=z;}
~Matrix() {}
void clear() {memset(id, 0, sizeof(id));}
void init(ll k) {clear(); for(ll i=1;i<=k;i++) id[i][i] = 1;}
}a, b;
Matrix operator * (const Matrix &a, const Matrix &b) {
Matrix c;
c.clear();
for(ll i=1;i<=3;i++)
for(ll j=1;j<=3;j++)
for(ll k=1;k<=3;k++)
c.id[i][j] = (c.id[i][j] + a.id[i][k] * b.id[k][j] % mod) % mod;
return c;
}
Matrix operator ^ (Matrix &a, ll k) {
Matrix res;
res.init(3);
for(;k;k>>=1,a=a*a) if(k&1) res = res * a;
return res;
}
Matrix calc(ll k) {
if(k <= 0) return Matrix(0, 0, 0);
if(k == 1) return Matrix(0, 1, 1);
if(k == 2) return Matrix(1, 1, 2);
a.clear(); b.clear();
a.id[1][1] = a.id[1][2] = a.id[1][3] = 1;
b.id[1][2] = b.id[2][1] = b.id[2][2] = b.id[2][3] = b.id[3][3] = 1;
a = a * (b ^ (k - 1));
return a;
}
int main() {
scanf("%lld", &T);
while(T--) {
scanf("%lld%lld", &n, &m);
printf("%lld\n", (calc(m).id[1][3]%mod-calc(n-1).id[1][3]%mod+mod)%mod);
}
return 0;
}
```