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

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

矩

阵

乘

法

]

裴

波

拉

契

数

列

I

I

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

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

形如 1 1 2 3 5 8 13 21 34 55 89 144…的数列,求裴波拉契数列的第n项。

Input

n (1< n <2^31）

Output

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

Sample Input

123456789

Sample Output

4514

题目解析

首先看题面，是斐波那契数列。

首先想到递归，但考虑到N的值比较大，就想办法将时间复杂度降到

O

(

l

o

g

N

)

O(logN)

O(logN)以达到目的。

那么怎么将时间复杂度降下来呢？

我们将斐波那契数列的第

n

n

n项定义为

f

(

n

)

f(n)

f(n)，然后考虑用矩阵乘法进行一个时间复杂度的优化

那么我们考虑矩阵

⊏

f

[

n

−

2

]

,

f

[

n

−

1

]

⊐

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

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

⊏

f

[

n

]

,

f

[

n

−

1

]

⊐

=

⊏

f

[

n

−

2

]

+

f

[

n

−

1

]

,

f

[

n

−

1

]

⊐

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

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

然后可以构造出一个

2

∗

2

2 * 2

2∗2的矩阵

T

T

T

∣

0

1

1

1

∣

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

∣∣∣∣​01​11​∣∣∣∣​

然后可以通过

f

[

1

]

,

f

[

2

]

∗

T

=

f

[

2

]

,

f

[

3

]

f[1] , f[2] * T = f[2] , f[3]

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

Code

#include <cmath>

#include <cstdio>

#include <iostream>

using namespace std;

const int MOD = 10000;

int n;

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",&n);

	if (n == 1)

	{

		printf("1\n");

		return 0;

	}

	t1.n = 2,t1.m = 2;

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

	rt (n - 1);

	t3.n = 1,t3.m = 2;

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

	t3 = t3 * t2;

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

	return 0;

}