题目描述

题目链接
In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

An alternative formula for the Fibonacci sequence is
题目

Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

1
2
3
4
5
0
9
999999999
1000000000
-1

Sample Output

1
2
3
4
0
34
626
6875

Hint

hint

题解

就是矩阵快速幂的应用， 目前有两种方法

第一种：
方法

第二种
2

明显第二种要快一些， 根据评测也是这样。

AC代码

第一种方法：

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
65
66
67
//#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

#define esp 1e-6
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e2 + 5;
const int M = 1e9 + 5;;
const int mod = 1e4;


struct Matrix{
    ll m[N][N];
};

Matrix mul(Matrix a, Matrix b, int n, int m){ // a * b  n为a的行数， m为b的列数
    Matrix c;
    memset(c.m, 0, sizeof c.m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= n; k++)
                c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod ; // 取模在这里取

    return c;
}

Matrix q_pow(Matrix a, ll b, int n) { // a^b  n为矩阵大小
    Matrix ans;
    memset(ans.m, 0, sizeof ans.m);
    for (int i = 1; i <= n; i++)
        ans.m[i][i] = 1;
    while(b){
        if (b & 1)
            ans = mul(ans, a, n, n);
        a = mul(a, a, n, n);
        b >>= 1;
    }
    return ans;

}

int main(){
    Matrix a, b, c;
    ll k;
    a.m[1][1] = a.m[1][2] = a.m[2][1] = 1;
    a.m[2][2] = 0;
    b.m[1][1] = 1;
    b.m[1][2] = 0;
    while(cin >> k){
        if (!~k)
            break;
        if (k == 0 || k == 1){
            cout << k << "\n";
            continue;
        }
        c = q_pow(a, k - 1, 2);
        c = mul(c, b, 2, 1);
        cout << c.m[1][1] << "\n";
    }
    return 0;
}

第二种方法

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 <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

#define esp 1e-6
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e2 + 5;
const int M = 1e9 + 5;;
const int mod = 1e4;


struct Matrix{
    ll m[N][N];
};

Matrix mul(Matrix a, Matrix b, int n, int m){ // a * b  n为a的行数， m为b的列数
    Matrix c;
    memset(c.m, 0, sizeof c.m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= n; k++)
                c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod ; // 取模在这里取

    return c;
}

Matrix q_pow(Matrix a, ll b, int n) { // a^b  n为矩阵大小
    Matrix ans;
    memset(ans.m, 0, sizeof ans.m);
    for (int i = 1; i <= n; i++)
        ans.m[i][i] = 1;
    while(b){
        if (b & 1)
            ans = mul(ans, a, n, n);
        a = mul(a, a, n, n);
        b >>= 1;
    }
    return ans;

}

int main(){
    Matrix a, b, c;
    ll k;
    a.m[1][1] = a.m[1][2] = a.m[2][1] = 1;
    a.m[2][2] = 0;
    while(cin >> k){
        if (!~k)
            break;
        if (k == 0 || k == 1){
            cout << k << "\n";
            continue;
        }
        c = q_pow(a, k - 1, 2);
        cout << c.m[1][1] << "\n";
    }
    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan