$$矩阵$$

1.定义：一组数的整体，在[ ]内排列成 m 行 n 列的数表

• 对于矩阵$A$，主对角线是指$ A_{i,i} $ 的元素
• 单位矩阵$I$： 行和列数相等；且主对角线元素都为 1;

$$ I: \left[ \begin{matrix} 1 & 0 & \cdots & 0 \\\ 0 & 1 & \cdots & 0 \\\ \vdots & 0 & \ddots & 0 \\\ 0 & 0 & \cdots & 1 \\\ \end{matrix} \right] \tag{1} $$

2. 性质

• 矩阵的逆: $A$ 的逆矩阵 $P$ 是使得 $ A * P = I$ 的矩阵 (可以使用高斯消元求得)

3.运算:

• 加法和减法: 两个矩阵相对应的位置相加减即可
• 矩阵乘法: $C_{i,j}$ = $\sum_{k=1}^{1} {A_{i,k}}$ $B_{k,j}；$ $\qquad$ $A是n * m 的矩阵, B是r * m的矩阵$
• 简便记忆(矩阵原理): 对于 $C_{i,j}$ 是由$ A $的 第$ i $ 行 $B $的第$ j $行 一 一对应相乘在求和而得到的
• 注意:矩阵乘法满足结合律，不满足一般的交换律。

$$ \left[ \begin{matrix} 1 & 2 \\\ 3 & 4 \\\ 5 & 6 \\\ \end{matrix} \right] \times \left[ \begin{matrix} 1 & 2 \\\ 3 & 4 \\\ \end{matrix} \right] = \left[ \begin{matrix} 1\times1+2\times3 & 1\times2+2\times4 \\\ 3\times1+4\times3 & 3\times2+4\times4 \\\ 5\times1+6\times3 & 5\times2+6\times4 \\\ \end{matrix} \right] = \left[ \begin{matrix} 7 & 10 \\\ 15 & 22 \\\ 23 & 34 \\\ \end{matrix} \right] \tag{2} $$

由于方阵的特殊性质（能自己乘自己），在做递推时可以利用矩阵的性质降低时间复杂度

例题:斐波那契

$$f(n)= \begin{cases} 1 & \text{$n \leq 2$} \\\\ f(n-1) + f(n-2) & \text{$n \geq 3$} \end{cases}\tag{3}$$

对于 $f_n$和$f_{n-1}$有

$$ f_n = f_{n-1} + f_{n-2} \tag{4} $$
$$ f_{n-1} = f_{n-1} + 0 * f_{n-2} \tag{5}$$

构造出矩阵

$$ \left[ \begin{matrix} f(n) & f(n-1) \\\ \end{matrix} \right] = \left[ \begin{matrix} f(2) & f(1) \\\ \end{matrix} \right] \times \left[ \begin{matrix} 1 & 1 \\\ 1 & 0 \\\ \end{matrix} \right]^{(n-2)} \tag{6} $$

对于后面这一项可以使用快速幂使复杂度降到$O(logn)$,总时间复杂度$O(k\times logn)$

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int sz = 2, MOD = 10000;
typedef long long ll;

int n;

struct mat{
    ll a[sz][sz];  // 对于 fib 只要 2 * 2 的矩阵就足够了

    // 初始化函数，没有这个函数那么初始 a 是随机的,会出错误
    inline mat() {memset(a, 0, sizeof a); }

    // 矩阵加法
    inline mat operator + (const mat &T) const{
        mat res ;
        for(int i = 0; i < sz; i++)
          for(int j = 0; j < sz; j++)
            res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
        return res;
    }

    // 矩阵减法
    inline mat operator - (const mat &T) const{
        mat res;
        for(int i = 0; i < sz; i++)
          for(int j = 0; j < sz; j++)
            res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
        return res;
    }

    // 矩阵乘法
    inline mat operator * (const mat &T) const{
        mat res;  int r ;
        for(int i = 0; i < sz; i++) 
          for(int k = 0; k < sz; k++) {
              r = a[i][k];                        // 对于小的矩阵,可以直接展开循环以减小常数。
              for(int j = 0; j < sz; j ++)        // 也可以写一个矩阵乘法函数mul; 
                  res.a[i][j] = (res.a[i][j] + T.a[k][j] * r) % MOD; // res.a[i][j] = mul(a[i][k],T.a[k][j]);
          }
        return res;
    }

    // 矩阵 快速幂 k 次方
    inline mat operator ^ (ll k) const{
        mat res, base;
        res.a[0][0] = res.a[0][1] = 1; // 构造初始矩阵
        base.a[0][0] = base.a[0][1] = base.a[1][0] = 1;

       /* 或者这么写；对于矩阵比较小而且初始化都差不多的时候，第一种会更方便；否则建议使用for接受数值
        for(int i = 0; i < sz; i++)
          for(int j = 0; j < sz; j++)
            base.a[i][j] = a[i][j]; 
        */   
        while(k){ // 快速幂
            if(k & 1) res = res * base; // 注意不能写成 res *= base , 因为没有重载 *=
            base = base * base;
            k >>= 1;
        }
        return res;
    }

}ans, bas;

// 初始化矩阵
void init(){
    bas.a[0][0] = bas.a[0][1] = bas.a[1][0] = 1;
    ans.a[0][0] = ans.a[0][1] = 1;
}

int main(){
    while(cin >> n && n != -1){
        if(n == 0) { puts("0"); continue; }

        init();
        ans = ans * (bas ^ (n - 2)); // 由于初始化就有 f1 f2 , 再乘一次就是 f3所以是 (n - 2) 次方
        cout << ans.a[0][0] % MOD << endl;
    }
    return 0;
}