poj 3070(矩阵快速幂)

poj 3070

求Fibonacci数列,但是这里直接递推肯定炸。
我们根据
$$F_{n} = F_{n-1} +F_{n-2}$$
构造矩阵
$$
\begin{pmatrix}
1 & 1 \\\
1 & 0
\end{pmatrix}
\times
\begin{pmatrix}
F_{n-1} \\\
F_{n-2}
\end{pmatrix}
=
\begin{pmatrix}
F_{n} \\\
F_{n-1}
\end{pmatrix}
$$
矩阵快速幂即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 4, MO = 10000;
int n;
struct matrix {
int x, y, ma[MAXN][MAXN];
void init(int x, int y) {this->x = x, this->y = y; for (int i=0;i<MAXN;i++) for (int j=0;j<MAXN;j++) ma[i][j] = (i==j);}//初始化为单位矩阵
void init2(int x, int y) {this->x = x, this->y = y; for (int i=0;i<MAXN;i++) for (int j=0;j<MAXN;j++) ma[i][j] = 0;}//初始化为空矩阵
}a;
matrix mul(matrix ai, matrix bi) {//矩阵乘法
matrix ret;
ret.init2(2, 2);
for (int i=0;i<ai.x;i++) {
for (int j=0;j<bi.y;j++) {
for (int k=0;k<ai.y;k++) {
ret.ma[i][j] = (ret.ma[i][j]%MO + (ai.ma[i][k]%MO) * (bi.ma[k][j]%MO))%MO;
}
}
}
return ret;
}
matrix poww(matrix ai, int x) {//快速幂
matrix s, ret;
s = ai, ret.init(2, 2);
while (x) {
if (x&1) ret = mul(ret, s);
s = mul(s, s);
x>>=1;
}
return ret;
}
void clean() {}
void solve() {
clean();
if (n==0) {printf("0\n"); return ;}
if (n==1||n==2) {printf("1\n"); return ;}
a.init(2,2), a.ma[0][0] = 1, a.ma[0][1] = 1, a.ma[1][0] = 1, a.ma[1][1] = 0;//矩阵初始化
matrix b = poww(a, n-1);
printf("%d\n", b.ma[0][0]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d", &n)==1&&n!=-1) solve();
return 0;
}

------ 本文结束 ------