斐波拉契数列IV

题目链接：SSL 1531

题目大意

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

思路

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

一开始的矩阵：

1(F[n-2])	1(F[n-1])	3(每次要加的n)	1(每次要加的1)

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

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

0	1	0	0
1	1	0	0
0	1	1	0
0	1	1	1

然后用就行了。

代码

#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;
}