斐波拉契数列IV

题目链接：SSL 1531

题目大意

就是定义一个函数：$f_i=f_{i-1}+f_{i-2}+n+1$，问你某一项是什么。
注：$f_1=f_2=1$

思路

这道题，我们继续在原来的基础上改（虽然我每次都重新打）
原来的基础：斐波那契数列III

一开始的矩阵：

（因为你从 $3$ 开始才要用矩阵，前两项都已经确定了，所以加 $n$ 的地方从 $3$ 开始）

那我们可以很容易的推出转移矩阵：

然后用就行了。

代码

#include<cstdio>
#define mo 9973

using namespace std;

struct matrix {
	int n, m, a[5][5];
}a, b, ans, re;
int n;

matrix operator *(matrix x, matrix y) {
	re.n = x.n;
	re.m = y.m;
	for (int i = 0; i < re.n; i++)
		for (int j = 0; j < re.m; j++)
			re.a[i][j] = 0;
	
	for (int k = 0; k < x.m; k++)
		for (int i = 0; i < re.n; i++)
			for (int j = 0; j < re.m; j++)
				re.a[i][j] = (re.a[i][j] + (x.a[i][k] * y.a[k][j]) % mo) % mo;
	
	return re;
}

void jzksm(int now) {
	b = a;
	now--;
	while (now) {
		if (now & 1) b = b * a;
		a = a * a;
		now /= 2;
	}
}

int main() {
	scanf("%d", &n);
	
	if (n == 1) {
		printf("1");
		return 0;
	}
	
	ans.n = 1;
	ans.m = 4;
	ans.a[0][0] = 1;//1*4的矩阵
	ans.a[0][1] = 1;
	ans.a[0][2] = 3;
	ans.a[0][3] = 1;
	
	a.n = 4;//4*4的转移矩阵
	a.m = 4;
	a.a[1][0] = 1;
	a.a[0][1] = 1;a.a[1][1] = 1;a.a[2][1] = 1;a.a[3][1] = 1;
	a.a[2][2] = 1;a.a[3][2] = 1;
	a.a[3][3] = 1;
	
	jzksm(n - 1);
	
	ans = ans * b;
	
	printf("%d", ans.a[0][0]);
	
	return 0;
}