【Loj #10222. 「一本通 6.5 例 4」佳佳的 Fibonacci】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15789018.html

题目链接

题目

佳佳对数学，尤其对数列十分感兴趣。在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。例如用 $S(n)$ 表示 Fibonacci 前 $n$ 项和 $\bmod m$ 的值，即 $S(n)=(F_1+F_2+...+F_n)\bmod m$，其中 $F_1=F_2=1, F_i=F_{i-1}+F_{i-2}$ 。可这对佳佳来说还是小菜一碟。
终于，她找到了一个自己解决不了的问题。用 $T(n)=(F_1+2F_2+3F_3+...+nF_n)\bmod m$ 表示 Fibonacci 数列前 $n$ 项变形后的和 $\bmod m$ 的值。
现在佳佳告诉你了一个 $n$ 和 $m$，请求出 $T(n)$ 的值。

思路

设

$$\Large S_n=\sum_{i=1}^n f_i$$

$$\Large W_n=\sum_{i=1}^n f_i\times (n-i)$$

由 ：

$$\Large T_n=\sum_{i=1}^n f_i\times i$$

可得：

$$\Large T_n=S_n\times n-W_n$$

由 $W_n=\sum_{i=1}^n f_i\times (n-i)$ 可得：

$$W_n=\sum_{i=1}^{n-1}S_n$$

故可以用矩阵快速幂算出 $S_n$ 和 $W_n$。

列出矩阵：

$$\Large \begin{bmatrix}1,1,0,0\\1,0,0,0\\1,0,1,0\\0,0,1,1\end{bmatrix}\times \begin{bmatrix}F_n\\F_{n-1}\\S_{n-1}\\W_{n-1}\end{bmatrix}= \begin{bmatrix}F_{n+1}\\F_n\\S_n\\W_n\end{bmatrix}$$

总结

这是一道挺好的矩阵快速幂的题，既有思维含量，又有算法含量。

首先思维方面，这题可以巧妙的转化 $T_n$，把一个难求的值变成两个易求的值相减。

另一方面，矩阵快速幂也调了我很久，一个 n\time m 的矩阵和一个 $m\times q$ 的矩阵相乘，三层循环分别是 $n,q,m$，注意顺序。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, i, j, k;
int a[5][5]= {
	{0,0,0,0,0},
	{0,1,1,0,0},
	{0,1,0,0,0},
	{0,1,0,1,0},
	{0,0,0,1,1}
};
int ans[5][5], mo;
void cheng(int a[5][5], int b[5][5], int n, int m, int q) {
	int c[5][5]= {0}, i, j, k;
	for(i=1; i<=n; ++i)
		for(j=1; j<=q; ++j)
			for(k=1; k<=m; ++k)
				c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mo;
	memset(a, 0, sizeof(c));
	memcpy(a, c, sizeof(c));
}
signed main() {
	scanf("%lld%lld", &n, &mo); m=n;
	ans[1][1]=ans[2][2]=ans[3][3]=ans[4][4]=1;
	while(n) {
		if(n&1) cheng(ans, a, 4, 4, 4);
		n>>=1; cheng(a, a, 4, 4, 4);
	}
	memset(a, 0, sizeof(a)); a[1][1]=1;
	cheng(ans, a, 4, 4, 1);
	printf("%lld", ((ans[3][1]*m-ans[4][1])%mo+mo)%mo);
	return 0;
}