UVa 10229 - Modular Fibonacci

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

用 Matrix exponentiation 算 fibnonacci,再加上 矩陣快速冪。 邊做邊取模,以免溢位。
(小心 m = 0 時的 case)

Code

UVa 10229UVa 10229 - Modular Fibonacci
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
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
typedef long long LL;
struct Matrix
{
LL n[2][2];
int mod;

//邊做矩陣乘法邊 mod
Matrix operator*(Matrix& a)
{
Matrix t;
t.n[0][0] = (n[0][0] * a.n[0][0] + n[0][1] * a.n[1][0]) % mod;
t.n[0][1] = (n[0][0] * a.n[1][0] + n[0][1] * a.n[1][1]) % mod;
t.n[1][0] = (n[1][0] * a.n[0][0] + n[1][1] * a.n[1][0]) % mod;
t.n[1][1] = (n[1][0] * a.n[0][1] + n[1][1] * a.n[1][1]) % mod;
t.mod = mod;
return t;
}

//快速冪
Matrix operator^(int x)
{
Matrix M, A;
M.n[0][1] = 0, M.n[1][0] = 0;
M.n[0][0] = 1, M.n[1][1] = 1;
M.mod = mod;
if (!x)return M;
if (x == 1) return *this*M;
A = *this;
for (; x; x >>= 1, A = A * A)
if (x & 1)
M = M * A;

return M;
}

Matrix operator=(Matrix m)
{
mod = m.mod;
n[0][0] = m.n[0][0];
n[0][1] = m.n[0][1];
n[1][0] = m.n[1][0];
n[1][1] = m.n[1][1];
return *this;
}
};
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
Matrix M;
M.n[0][0] = 1;
M.n[0][1] = 1;
M.n[1][0] = 1;
M.n[1][1] = 0;
M.mod = 1 << m;

printf("%d\n", (M ^ (n)).n[0][1]);
}

return 0;
}