Problem Solving►UVa

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;
}