题目描述

在斐波那契数列中，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

算法1

经过精心设置的矩阵相乘是可以从Fn-1 Fn-2推导出Fn的

那么设置好的矩阵的多次相乘是不是就可以从F0 F1推到出Fn呢？

是的 如图

1 1

1 0 矩阵为A那么

A^(n-1) 与F1 F0矩阵的乘法就是可以推到出 Fn

代码借用了之前的快速幂代码 不是模板 所以虽然可以AC但是代码复用性不好
思想为主

C++ 代码

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

struct matrix {
    int data[35][35];
};

int n = 2;
int m = 10000;
int k = 0;

//矩阵乘法
matrix mul(matrix a, matrix b)
{
    matrix c;
    memset(c.data, 0, sizeof(c.data));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                c.data[i][j] = (c.data[i][j] + 1ll * a.data[i][k] * b.data[k][j]) % m;
            }
        }
    }

    return c;
}

//矩阵加法
matrix add(matrix a, matrix b) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a.data[i][j] = (a.data[i][j] + b.data[i][j]) % m;
        }
    }
    return a;
}

//矩阵快速幂
matrix quickpow(matrix a, int k) {
    matrix  c;
    memset(c.data, 0, sizeof(c.data));
    for (int i = 1; i <= n; i++)
        c.data[i][i] = 1;
    while (k) {
        if (k & 1) c = mul(c, a);
        k >>= 1;
        a = mul(a, a);
    }
    return c;
}


int main()
{
    int j;
    while (1) {
        cin >> j;
        if (j == -1) break;
        if (j == 0) {
            cout << 0 << endl; continue;
        }
        if (j == 1 || j == 2) {
            cout << 1 << endl; continue;
        }
        matrix  base;
        base.data[1][1] = 1; base.data[1][2] = 1;
        base.data[2][1] = 1; base.data[2][2] = 0;

        matrix fn;
        fn.data[1][1] = 1;
        fn.data[2][1] = 0;

        matrix baseN = quickpow(base, j-1);

        matrix c;
        memset(c.data, 0, sizeof(c.data));

        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= 1; j++) {
                for(int k =1;k<=2;k++){
                    c.data[i][j] = (c.data[i][j] + 1ll * baseN.data[i][k] * fn.data[k][j]) % m;
                }
            }
        }
        cout << c.data[1][1] << endl;
    }
    return 0;
}