python/TangDou/AcWing/Floyd/205.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 10; //这个黄海实测，写成3也可以AC，考虑到矩阵乘法的维度，一般写成10，差不多的都可以过掉
const int MOD = 10000;

int base[N][N], res[N][N];
int t[N][N];

//矩阵乘法,为快速幂提供支撑
inline void mul(int c[][N], int a[][N], int b[][N]) {
    memset(t, 0, sizeof t);

    //一个套路写法
    for (int i = 1; i <= 2; i++)
        for (int k = 1; k <= 2; k++) {
            if (!a[i][k]) continue; //对稀疏矩阵很有用
            for (int j = 1; j <= 2; j++)
                t[i][j] = (t[i][j] + (a[i][k] * b[k][j]) % MOD) % MOD;
        }
    memcpy(c, t, sizeof t);
}

//快速幂
void qmi(int k) {
    memset(res, 0, sizeof res);
    res[1][1] = res[1][2] = 1; //结果是一个横着走，一行两列的矩阵
                               // P * M 与 M * Q 的矩阵才能做矩阵乘积，背下来即可
    //矩阵快速幂,就是乘k次 base矩阵，将结果保存到res中
    //本质上就是利用二进制+log_2N的特点进行优化
    while (k) {
        //比如 1101
        if (k & 1) mul(res, res, base); // res=res*b
        mul(base, base, base);          //上一轮的翻番base*=base
        k >>= 1;                        //不断右移
    }
}

int main() {
    int n;
    while (cin >> n) {
        if (n == -1) break;
        if (n == 0) {
            puts("0");
            continue;
        }
        if (n <= 2) {
            puts("1");
            continue;
        }

        // base矩阵
        memset(base, 0, sizeof base);
        /**
         1 1
         1 0

         第一行第一列为1
         第一行第二列为1
         第二行第一列为1
         第二行第二列为0 不需要设置，默认值
        */
        base[1][1] = base[1][2] = base[2][1] = 1;

        //快速幂
        qmi(n - 2);

        //结果
        printf("%d\n", res[1][1]);
    }

    return 0;
}