CF - 450 -- B.Jzzhu and Sequences【矩阵快速幂+如何构造核心矩阵】

Jzzhu and Sequences

思路

题意让我们求f[i] = f[i-1] + f[i+1] 将其转化为 f[i] = f[i - 1] + f[i - 2]（i >= 2）

如果你不会构造核心矩阵，那么这篇文章将会帮助你如何构造核心矩阵

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
struct Mat{
	ll m[5][5];
}arr, temp;//arr输入矩阵,temp为核心矩阵 
ll MOD;
Mat operator *(Mat a, Mat b){//矩阵a X 矩阵b
	Mat temp;
	memset(temp.m, 0, sizeof(temp.m));
	for (int i = 0; i < 5; ++i)
		for (int j = 0; j < 5; ++j)
			for (int k = 0; k < 5; ++k)
				temp.m[i][j] = (temp.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
	return temp;
}
Mat fast_power(Mat a, ll b, int n){//矩阵a的b次方,n为矩阵a的大小 
	//初始化为单位矩阵 
	Mat res;
	memset(res.m, 0, sizeof(res.m));
	for (int i = 0; i < n; ++i)	res.m[i][i] = 1;
	while (b > 0){
		if (b & 1)	 res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
void solve(){
	int x, y, n;
	scanf("%d%d%d", &x, &y, &n);
	arr.m[0][0] = x;
	arr.m[0][1] = y;
	//核心矩阵
	temp.m[0][0] = 0;
	temp.m[0][1] = -1;
	temp.m[1][0] = 1;
	temp.m[1][1] = 1;
	Mat res = fast_power(temp, n - 1, 2);
	res = arr * res;
	printf("%lld\n", (res.m[0][0] + mod) % mod);
}
int main(){
	solve();
	return 0;
}