题目描述

在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。

给定整数n，求Fibnmod10000。

输入格式
输入包含多组测试用例。

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

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

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

每个结果占一行。

数据范围
0≤n≤2∗109

样例

输入样例：

0
9
999999999
1000000000
-1

输出样例：

0
34
626
6875

Tips:
可以递推，可是数据范围是2e9，计算内存不超限那2e9的遍历也必定会超时；
设F[N] = [ fib(N), fib(N+1) ] ,则F[N - 1] = [ fib(N - 1), fib(N) ],
则F[0] = [0, 1];而转移矩阵P就等于p[2][2]= { {0, 1} , {1, 1} };这样
F[N] = F[N - 1] * p[2][2]，F[N - 1] = F[N - 2] * p[2][2]，按此递推
则F[N] = F[0] * P[2][2]^N,此时问题将会变成求F[0] * P[2][2]^N，而F[0]
已知，这样快速求P[2][2]^N变成主要问题了；

F[N] = F[0] * P[2][2]^N = F[1] * P[2][2]^(N - 1) = F[2] * P[2][2]^(N - 2)......

matrix_mul(ali, p)，跟新斐波那契数列的下标，这是最终答案的过程解，如20的二进制代码
就是10100b，则 (9^20)%mod 的快速幂取模就是ans = [(9 ^(2 ^2) %mod) * (9 ^(2^ 4) %mod)] %mod
其中2^x中x为二进制代表的幂运算，而matrix_mul(ali, p)，中ans就代表这样的过程量；

矩阵乘法：

1. 一行n列 × n行n列：

for (int i = 0; i < 2; i++)
        for (int m = 0; i < 2; m++)
            tmp[i] += tmp[m] * kk[m][i];

1. n行n列 × n行n列

for (int i = 0; i < 2; i++)
    for (int m = 0; m < 2; m++)
        for (int n = 0; n < 2; n++)
            ret[i][m] += ali[i][n] * kk[n][m];

C++ 代码

#include<iostream>
#include<cstring>

const int mod = 1e4;

void change_matrix(int kk[2][2])
{
    int ali[2][2] = { {} };

    for (int i = 0; i < 2; i++)
        for (int m = 0; m < 2; m++)
            for (int n = 0; n < 2; n++)
                ali[i][m] += (kk[i][n] * kk[n][m]) % mod, ali[i][m] %= mod;

    memcpy(kk, ali, sizeof(ali));
    return;
}

void change_matrix(int kk[2][2],int ali[2][2])
{
    int ret[2][2] = { {} };

    for (int i = 0; i < 2; i++)
        for (int m = 0; m < 2; m++)
            for (int n = 0; n < 2; n++)
                ret[i][m] += (ali[i][n] * kk[n][m]) % mod, ret[i][m] %= mod;

    memcpy(ali, ret, sizeof(ret));

    return;
}

void matrix_mul(int ali[2], int kk[2][2])
{
    int tmp[2] = {};

    for (int j = 0; j < 2; j++)
        for (int m = 0; m < 2; m++)
            tmp[j] += (kk[m][j] % mod) * (ali[m] % mod), tmp[j] %= mod;

    memcpy(ali, tmp, sizeof(tmp));
    return;
}

int show(int n)
{
    int ali[2] = { 0,1 };
    int p[2][2] = { {0,1},{1,1} };
    int ans[2][2] = { {1,0},{0,1} };
    int first = 1;
    while (n)
    {
        if (n & 1)
        {
            if (first)memcpy(ans, p, sizeof(p));ans保存p^n的结果
            else change_matrix(p, ans);
            first = 0;
        }
        change_matrix(p);
        n >>= 1;
    }
    matrix_mul(ali, ans);//最后计算a*p^n的结果并返回
    return ali[0];
}

int main(void)
{
    int n;
    while (1)
    {
        scanf("%d", &n);
        if (-1 == n)break;
        printf("%d\n", show(n));
    }
    return 0;
}