[

矩

阵

乘

法

]

裴

波

拉

契

数

列

I

I

I

[矩阵乘法]裴波拉契数列III

[矩阵乘法]裴波拉契数列III

Description

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

Input

n(1＜n＜２³¹-1)

Output

一个数为裴波拉契数列的第n项mod 9973;

Sample Input

12345

Sample Output

8932

题目解析

对于为什么用矩阵乘法来做，详见博客斐波那契数列II

我们考虑矩阵

⊏

[

−

]

[

−

]

⊐

\sqsubset f[n - 2] , f[n - 1] , 1\sqsupset

⊏f[n−2],f[n−1],1⊐并利用斐波那契数列的递推关系来得到式子

⊏

[

]

[

−

]

⊐

⊏

[

−

]

[

−

]

[

−

]

⊐

\sqsubset f[n] , f[n - 1] , 1\sqsupset = \sqsubset f[n - 2] + f[n - 1] + 1, f[n - 1], 1\sqsupset

⊏f[n],f[n−1],1⊐=⊏f[n−2]+f[n−1]+1,f[n−1],1⊐

然后可以构造出一个

∗

3 * 3

3∗3的矩阵

∣

\begin{vmatrix} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{vmatrix}

∣∣∣∣∣∣010111001∣∣∣∣∣∣
然后可以通过

⊏

[

]

[

]

⊐

∗

⊏

[

]

[

]

⊐

\sqsubset f[1] , f[2] , 1\sqsupset * T = \sqsubset f[2] , f[3], 1 \sqsupset

⊏f[1],f[2],1⊐∗T=⊏f[2],f[3],1⊐来实现代码了

Code

#include <cmath>

#include <cstdio>

#include <iostream>

using namespace std;

int nt;

const int MOD = 9973;

struct matrix

{

	int n, m;

	int t[10][10];

}t1, t2, t3;

matrix operator *(matrix t, matrix r)

{

	matrix c;

	c.n = t.n, c.m = r.m;

	for (int i = 1; i <= c.n; ++ i)

	 for (int j = 1; j <= c.m; ++ j)

	  c.t[i][j]=0;

	for (int k = 1; k <= t.m; ++ k)

	 for (int i = 1; i <= t.n; ++ i)

	  for (int j = 1; j <= r.m; ++ j)

	   c.t[i][j] = (c.t[i][j] + t.t[i][k] * r.t[k][j] % MOD) % MOD;

	return c;

}

void rt (int k)

{

	if (k == 1)

	{

		t2 = t1;

		return;

	}

	rt (k / 2);

	t2 = t2 * t2;

	if (k & 1) t2 = t2 * t1;

}

int main()

{

	scanf ("%d", &nt);

	if (nt == 1)

	{

		printf ("1");

		return 0;

	}

	t3.n = 1;

	t1.n = t1.m = t3.m = 3;

	t1.t[1][1] = 0, t1.t[1][2] = 1, t1.t[1][3] = 0;

	t1.t[2][1] = 1, t1.t[2][2] = 1, t1.t[2][3] = 0;

	t1.t[3][1] = 0, t1.t[3][2] = 1, t1.t[3][3] = 1;

	t3.t[1][1] = t3.t[1][2] = t3.t[1][3] = 1;

	rt (nt - 1);

	t3 = t3 * t2;

	printf ("%d", t3.t[1][1]);

	return 0;

}

巴特西

[矩阵乘法]裴波拉契数列III

[

矩

阵

乘

法

]

裴

波

拉

契

数

列

I

I

I

[矩阵乘法]裴波拉契数列III

[矩阵乘法]裴波拉契数列III

Description

Input

Output

Sample Input

Sample Output

题目解析

Code

最新文章

热门文章

巴特西

[矩阵乘法]裴波拉契数列III

[ 矩 阵 乘 法 ] 裴 波 拉 契 数 列 I I I [矩阵乘法]裴波拉契数列III [矩阵乘法]裴波拉契数列III

Description

Input

Output

Sample Input

Sample Output

题目解析

Code

最新文章

热门文章

[

矩

阵

乘

法

]

裴

波

拉

契

数

列

I

I

I

[矩阵乘法]裴波拉契数列III

[矩阵乘法]裴波拉契数列III