题目描述

在斐波那契数列中，$Fib_0=0, Fib_1=1, Fib_n=Fib_{n-1}+Fib_{n-2} (n>1)$。

给定整数 $n$，求 $Fib_n \\bmod 10000$。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含一个整数 $n$。

当输入用例 $n=-1$ 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个整数表示结果。

每个结果占一行。

数据范围

$0 \\le n \\le 2 \\times 10^9$

输入样例：

0
9
999999999
1000000000

输出样例：

0
34
626
6875

算法

(矩阵快速幂) $O(logn)$

C++ 代码

/*
矩阵A
1 1
1 0

求A的n次方
然后右下角A11 就是fn
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e9 + 10, MOD = 10000;

int n;

// 矩阵乘法
vector<vector<int>> muli(vector<vector<int>> a, vector<vector<int>> b)
{

    vector<vector<int>> c(2, vector<int>(2));

    for(int i = 0; i < 2; i ++)
    {
        for(int j = 0; j < 2; j ++)
        {
            for(int k = 0; k < 2; k ++)
            {
                c[i][j] = (c[i][j] % MOD + a[i][k] % MOD * b[k][j] % MOD) % MOD;
            }
        }
    }

    return c;
}

// 矩阵快速幂
vector<vector<int>> qmi(vector<vector<int>> a, int n)
{
    vector<vector<int>> c(2, vector<int>(2));

    c[0][0] = c[0][1] = c[1][0] = 1;

    while (n)
    {
        if(n & 1) c = muli(c, a);
        a = muli(a, a);
        n >>= 1;
    }

    return c;
}


int main()
{
    vector<vector<int>> a(2, vector<int>(2));
    vector<vector<int>> res(2, vector<int>(2));

    a[0][0] = a[0][1] = a[1][0] = 1;

    while(cin >> n && n != -1)
    {
        res = qmi(a, n);
        cout << res[1][1] % MOD << endl;
    }

    return 0;
}