前置：

矩阵运算：（以下几种运算都设 $C$ 的行数为 $r$, 列数为 $c$）

1. 加法：
   若 $C = A + B$(matrix A,B,C), 则
   $\forall 1 \le i \le r, 1 \le j \le c$，使得 $C_{i,j}=A_{i,j}+B_{i,j}$
   满足加法交换律及加法结合律。

   例如：
   

2. 减法：
   若 $C = A - B$(matrix A,B,C)，则 $B + C = A$，即：
   $\forall 1 \le i \le r, 1 \le j \le c$，使得 $C_{i,j}=A_{i,j}-B_{i,j}$

   例如：
   

3. 数乘：
   若 $C = A \times B$(matrix A,C, int B)，则
   $\forall 1 \le i \le r, 1 \le j \le c$，使得 $C_{i,j}=A_{i,j} \times B$

   这个太简单了，就不举例了qwq

4. 乘法：
   若 $C = A \times B$(matrix A,C, int B)，设 $A$ 为 $n \times m$ 矩阵，$B$ 为 $m \times p$ 矩阵，则
   $\forall 1 \le i \le n, 1 \le j \le p$，$C_{i,j} = \displaystyle\sum_{k=1}^n (A_{i,k} \times B_{k,j})$
   满足乘法对加法的分配律、结合律，不满足乘法交换律。

   例如：
   

   注：该例子不够典型，仅供参考，请读者参考其他资源。

正文：

本题求的是斐波那契数列，斐波那契数列原本是 $O(N)$ 的递推就能求出来的，可是显然毒瘤的 oier 不满足于 $O(N)$，硬生生弄出了 $1 \le N \le 2 \times 10^{9}$，所以我们要换一种方法：

求出斐波那契的第 $n$ 项只需要用到 $f_{n-1},f_{n-2}$，所以我们只需要存住 $\left(f_n, f_{n-1}\right)$ 即可。
但如何利用 $f_{n-1},f_{n-2}$ 更快推出 $f_n,f_{n-1}$ 呢？就要用到上述的矩阵乘法。

只要仔细去研究斐波那契数列，我们可以得出 ，又因为矩阵乘法满足乘法对加法的分配率，所以我们可以用快速幂$O\left(log_2N\right)$求出 的矩阵后，再将它乘以初始矩阵。

code（同学，别抄，会编译错误）：

#include <bits/stdc++.h>

using namespace std;

const int P = 1e4;

struct matrix {

    int p[10][10];

    void clear() {

        memset (p, 0, sizeof p);
    }

    void mod () {

        for (int i = 1; i <= 5; i ++)
            for (int j = 1; j <= 5; j ++)
                p[i][j] %= P;
    }

    matrix() {}
};

matrix operator * (matrix a, matrix b) {

    matrix c; c.clear();
    a.mod(); b.mod(); 

    for (int i = 1; i <= 5; i ++)
        for (int j = 1; j <= 5; j ++)
            for (int k = 1; k <= 5; k ++)
                c.p[i][j] += a.p[i][k] * b.p[k][j];

    c.mod();            
    return c;
}

matrix qmi (matrix a, int b) {

    matrix res; res.clear();
    bool f = 0;
    a.mod();

    for (; b; b >>= 1, a = a * a)
        if (b & 1)
            if (f)
                res = res * a;

            else {

                res = a; f = 1;
                res.mod();
            }

    return res;
}

signed mian() {

    int n;
    scanf ("%d", &n);

    while (~n) {

        matrix a, b;
        a.clear(); b.clear();

        a.p[1][1] = 0; a.p[2][1] = 1;
        b.p[1][1] = 0; b.p[1][2] = b.p[2][1] = b.p[2][2] = 1;

        a = a * qmi (b, n + 1);

        printf ("%d\n", a.p[2][1]);
        scanf ("%d", &n);
    }

    return qwq;
}

这只蒟蒻写了一个小时，就点个赞呗/kk