Description

求数列f[n]=f[n-1]+f[n-2]+1的第N项.f[1]=1,f[2]=1.

Input

n(1＜n＜２^31-1)

Output

第Ｎ项的结果 mod 9973

Sample Input

12345

Sample Output

8932

---

解题思路

详情参见裴波拉契数列II

+1其实很好处理
把A矩阵改为

B矩阵改为

A = A = A= { 0 ， 1 ， 0 ， 1 ， 1 ， 1 ， 0 ， 0 ， 1 0，1，0，1，1，1，0，0，1 0，1，0，1，1，1，0，0，1｝
B = B = B= { f [ n − 2 ] , f [ n − 1 ] , 1 f[n -2], f[n - 1], 1 f[n−2],f[n−1],1}
A ∗ B A * B A∗B
= = ={ f [ n − 2 ] ∗ 0 + f [ n − 1 ] ∗ 1 + 1 ∗ 0 , f [ n − 2 ] ∗ 1 + f [ n − 1 ] ∗ 1 + 1 ∗ 1 , f [ n − 2 ] ∗ 0 + f [ n − 1 ] ∗ 0 + 1 ∗ 1 f[n - 2] * 0 + f[n - 1] * 1 + 1*0,f[n - 2] * 1 + f[n - 1] * 1 + 1 * 1,f[n - 2] * 0 + f[n - 1] * 0 + 1 * 1 f[n−2]∗0+f[n−1]∗1+1∗0,f[n−2]∗1+f[n−1]∗1+1∗1,f[n−2]∗0+f[n−1]∗0+1∗1}
= = ={ f [ n − 1 ] , f [ n ] , 1 f[n - 1],f[n],1 f[n−1],f[n],1}

---

Code

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int Mod = 9973;
long long n;

struct DT{
	int n, m;
	int aed[5][5];
}A, B, Ac;

DT operator *(DT a, DT b){//矩阵乘法
	DT c;
	c.n = a.n, c.m = b.m;
	memset (c.aed, 0, sizeof (c.aed));
	for (int k = 1; k <= a.m; k++)
		for (int i = 1; i <= c.n; i++)
			for (int j = 1; j <= c.m; j++)
				c.aed[i][j] = (c.aed[i][j] + a.aed[i][k] * b.aed[k][j] % Mod) % Mod;
	return c;
}

void power (long long n){//快速幂
	if (n == 1)
	{
		Ac = A;
		return;
	}
	power (n / 2);
	Ac = Ac * Ac;
	if (n % 2) Ac = Ac * A; 
}

int main(){
	A.n = A.m = 3;
	A.aed[1][2] = A.aed[2][1] = A.aed[2][2] = A.aed[3][2] = A.aed[3][3] = 1;
	B.n = 1, B.m = 3;
	B.aed[1][1] = B.aed[1][2] = B.aed[1][3] = 1;
	//初始化矩阵
	scanf ("%lld", &n);
	power (n - 1);
	B = B * Ac;
	printf ("%d", B.aed[1][1]);
}