题解 [email protected]洛谷 | [email protected] 【FIBOSUM - Fibonacci Sum】

我也不知道我怎么找到的这题,但是既然 AC 了,就来写一篇题解。

题意简述:共 TT 组询问,每次读入两个数 n,mn,m,输出 i=nmaimod(109+7)\displaystyle\sum_{i=n}^ma_i\mod (10^9+7) 的值,其中 aia_i 为斐波那契数。


由于洛谷爬的时候漏掉了数据范围,可以到原题目中查看:T103,0nm109T\le 10^3,0 \le n\le m\le 10^9,可以看到暴力求出所有斐波那契数的前缀和后求解显然会超时,容易想到矩阵加速。

我们使用矩阵维护第 ii 项、第 i+1i+1 项的值及前 ii 项的和,下面考虑构造转移矩阵。

根据斐波那契数列的定义,我们知道:

{ai+1=ai+1ai+2=ai+ai+1si+1=si+ai+1\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}

经过一些简单变换即可得到转移矩阵:

[aiai+1si]×[010111001]=[ai+1ai+2si+1]\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}

此时,我们可以通过类似于题目矩阵加速的方式利用矩阵快速幂在 log\log 时间内求出对于一个整数 kksks_k 的值。我们要求的答案即为 smsn1mod(109+7)s_m-s_{n-1}\mod (10^9+7)

代码:

//By: [email protected]_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;
}