第一节 方程组与矩阵的互相转化#

假设我们有一个方程组：。首先将所有未知数提到等号左侧，常数全部移到右侧。我们暂时先忽略掉等号右边的常数项。我们将每行未知数的系数提取出来，放入矩阵的第一行，矩阵的第一行就表示方程组中第一个方程的未知数系数（没有默认为 0），以此类推到下边几行，最终你会得到一个列数与未知数个数相等、行数与方程个数相等的矩阵。本例中它长成这个样子：

如此得到的矩阵叫做系数矩阵，顾名思义，它只表示了原方程组的系数，而忽略了常数项。

它同时也是一个 矩阵。

一般地，对于一个 矩阵（），它有 行 列。

此时，如果我们加上等号右侧的常数项，原先的 矩阵会变成 的。

人们为了区分常数和系数，选择在书写时将常数加入到最右侧那一列，并且在最右一列的前面加上竖线分隔系数，如此得到的矩阵叫做增广矩阵。

本例中 的增广矩阵形式 写作：

当矩阵元素不明时，我们为了简便表示矩阵本身，采用字母 + 下标 + 括号的方式。例如一个 矩阵 ，可以写作：。

第二节 矩阵的基本运算#

第三节 消元#

按照一般思路（就是我们在小学学的方法），我们会选择通过方程互相加减各自的倍数，达到消去未知数的目的。这种方法在矩阵上同样适用，而且它有一个贼高坤的名称：高斯消元法（Gaussian Elimination）。

回忆一下我们从出生就会用的消元原理，我们的目标就是让每个未知数都对应一个常数项，那么它的值就可以直接用常数除以系数的方式求出。矩阵中也是如此，为了能够化简出可直接求解的矩阵，我们在此引入初等行变换的概念：

1. 交换某两行
2. 把矩阵的某一行同乘以一个非零的数
3. 把某行的若干倍加和到另一行

这三条很容易理解。第一条：相当于交换方程组顺序，不影响计算；第二条：相当于对某一行方程放缩某倍，它等价于原方程；第三条：相当于前两条的融合，也是消元的关键一招。这三条规则在之后的初等矩阵内容中会再次出现。

首先从一个例子讲起，让读者感受一下初等行变换的魅力：

考虑这个方程组：

按照如上所述，将它转写成增广矩阵的形式：

我们总结一下常用的消元原理，应用到矩阵上就是：

1. 枚举每一列 ，选出无序组中第 列系数绝对值最大的一行 ，并移到无序组的最上边。（变换规则一）
2. 行通过自乘，将第 列的系数变成 ，并标记 为有序。（变换规则二）
3. 通过加减有序组中某一行的非零倍，将之后所有行的第 列系数化为 。（变换规则三）

令矩阵 （有序组用绿色表示）

枚举第一列，。开始时，所有行均无序。选出绝对值最大的那一项，本例中为第二行，进行移动，原矩阵变为：

第二步，自乘并标记有序，因此第一行除以 ，原矩阵就变成了：

第三步，将无序组的第 列消成 。本例中，我们让第二行减去二倍第一行；第三行直接减去第一行，得到：

枚举第二列，此时 。第一步，选出第二列系数绝对值最大的那一行，移到无序组最上端。本例中无需移动，自乘 ，标记有序，原矩阵为：

最终的最终，第三行减 倍第二行，得到我们心心念念的化简后的矩阵：

为什么把矩阵化简成这种金字塔型的形式呢？你会发现：最后一行仅有一个带系数的未知数 ，我们直接求，。向上一行，现在 相当于常数，移到常数中与 合并， 也可直接求了……经过如上的反代操作，三个未知数都会被求出来。至此我们才发现这个三角形矩阵的魅力之处。

一般地，对于一个矩阵，如果它的非零系数呈阶梯形分布，则称这类矩阵为行阶梯形矩阵。将非零系数挑出来，它们组成的是一个上三角形矩阵；对应地，零项就会组成下三角矩阵。上三角矩阵通常以 表示、下三角矩阵通常用 表示。

原方程组有唯一解：

在这里，我没有给出代码实现。因为对于一些特殊情况，化简出的矩阵不能很好地被计算机处理，更适合算法竞赛体质的高斯消元模板将在本章第五节给出。

第四节 秩#

类比一元二次方程的实数根存在性判别法 —— 判别式法，即对于一元二次方程 ，实数根的个数 。那么，矩阵方程是否也有类似的根存在性判别方法呢？

答案是有的，而且不止一种，这意味着“矩阵是否有解” 这样的问题会有多种解决方案。现在介绍的是最为简单常用的一种——秩。

在线性代数中，一个矩阵 A 的列秩是 A 的线性独立的纵列的极大数目。类似地，行秩是 A 的线性无关的横行的极大数目。即如果把矩阵看成一个个行向量或者列向量，秩就是这些行向量或者列向量的秩，也就是极大无关组中所含向量的个数。

……咱们抛掉这种看也看不懂的高级语文句法，听我给你总结：

通俗来讲，把一个矩阵化成最简形式（特指行阶梯形）后，非零行的个数就是矩阵的秩。这其实是秩的最大线性无关组的定义。再次白话总结：如果存在三个行向量（列向量一样的，保证所有向量都是行 / 列向量即可）：。根据高中数学中立体几何的知识 —— 和 显然是共线的，这两个向量就是线性相关的。如果对于一组 维向量，可以成为 维空间的一组基底向量，那么它们就是线性无关的。

矩阵 的秩用 表示，或者用 、、 等表示。

现在明白了吧，如果一个矩阵的某两行线性相关，它们都会被初等行变换第三条狠狠薄纱 —— 在乘或除以一个非零数后相减，其中一行就会被全部消成 0，从方程组角度来看就是 ，带什么值都成立（相当于去重了一个方程）。

当然上边这一段也有表述不准确之处，假设有一个增广矩阵 。初等行变换第三条秒了第一、第二行，然而事情有些不对劲了……

第二行不乐意了，它还存留这最后一点倔强，好像在说：“你总结的不对呢真是雑鱼”。但是明眼人都看得出来， 这种事情是绝对不可能发生的，也就是无解。按照刚刚说的，这个增广矩阵的秩 ，可是它对应的系数矩阵 的秩 ，就有 且 ，于是我们就找到了矩阵无解的一个条件了。也就是 。

再考虑有无穷解的情况：无非就是出现了 的情况，此时 可以代任何值。与无解不同，这次的最简行阶梯形矩阵，无论是系数矩阵还是增广矩阵形式，它们的秩都是相同的，并且都浪费了至少一行方程式。我们知道：一个三元一次方程组是无法用相异的（行向量形式表示下不共线）两个方程解出唯一值的，相反，解形如： 表明 由 确定、而 又由 确定，然而这俩都不确定，导致这两个数可以取无穷多的值，也就导致矩阵有无穷组解。综上：矩阵有无穷组解的充要条件是 （ 为未知数个数）。

最后就是有唯一解：如果一切进行顺利的话，既没有全零行，也没有无解行。那么此时系数矩阵和增广矩阵的秩会相同，且等于未知数个数，即 。

总结，假设一个由 个未知数组成的最简行阶梯形矩阵 、以及它的增广矩阵 。矩阵解的个数由如下规则导出：

例 1.4.1 Delivery Mathematics 快递员的数学题#

「稻妻狛荷屋的人气跨国快递员绮良良在送货途中遇到了一个难题，你作为无所不知无所不晓的旅行者自然是乐意地接下了她的委托。当你来到委托地点时，你发现这是一道解谜题目……」

稻妻号称最难的方块解谜是一组由 个正方体可旋转方块组成的阵列，击打其中的某个方块会使得与之相关联的其他方块共同旋转一个特定角度。在这个谜题中，每个方块每次仅能水平顺时针旋转 90 度，传动方式在下图给出。问若要使所有方块同时朝向北方，需要如何击打方块？给出任意可行解，但需要保证每个方块旋转的次数不超过 4（不击打也可以，相当于次数为 0）。

由于钟离先生远在海那一头的璃月喝茶听评书、宵宫也正忙着制作夏日祭的烟花而无法抽身、香菱在万民堂做饭、安柏在侦察蒙德郊区、芙宁娜忙着吃蛋糕…… 总之没有其他人召唤物能帮你解决这个问题，你只能凭借自己的力量解开这个谜题。

问题分析：首先我们要搞清楚传动规则，我们会发现当你击打了一个方块，包括它在内、再按顺时针方向数两个方块都在旋转相同的角度。这也是这道题被称作难题的原因之一，只用想象力是很难想象的出来的…… 于是为了用代数方法解决该问题，我们选择用四个未知数、四个方程表示每个方块操作后的状态，问题解决的标志既为四个方块的状态均为 （ 表示北方）。

算法设计：考虑到单个方块每旋转四次就相当于一次循环，因此我们重定义方向标，从北开始，顺时针方向将方位标记为 。这么做可以避免一些复杂的取模运算。接着我们根据传动规则表示每个方块的状态，令方块 1-4 被击打次数分别为 。以方块 1 为例：击打自己、3 号和 4 号都会导致 1 号顺时针旋转 90°，再算上 1 号初始朝向为 ，得到：。其他方块以此类推，解析出的方程组对其求解即可。这样的矩阵一定有唯一解，每个未知数都以 表示，将一个自然数代入 值即可解出答案。

解：设方块 1-4 的击打次数分别为 ，设朝向从北方按顺时针方向分别为 。

根据传动规则，有如下线性方程组：

增广矩阵形式为：

（化简过程略），行阶梯形式为：

因为系数矩阵的秩与增广矩阵的秩相同且都等于未知数个数 ，因此矩阵有唯一解 。易知 的合法值满足 的数学关系，此处求最小值，令 ，得到 。

因此，最佳方案是暴击击打 2 号和 3 号方块各两次。

后日谈：有些读者可能会问，这个难道不是有无穷解吗？为什么上边说这个矩阵只有唯一解？其实这个矩阵确实只有唯一解，因为 ，造成它有无数组解的原因是 这个自然数。我们在开头只为这个矩阵设定了四个未知数 ，因此矩阵只有四个元，因而有唯一解。事实上，这个问题也可以转化成同余高斯消元，在普通高斯消元的基础上变除法为乘逆元即可。

对于有 （质数）个有效旋转面的方块，详见洛谷 P10315，顺便推一下 我的题解。

第五节 计算机高斯消元#

1
int gauss() {
2
    int rank = 0; // 秩
3
    for (int c = 1, r = 1; c <= n; c++) {
4
        int t = r;
5
        for (int i = r; i <= n; i++) {
6
            if (abs(matrix[i][c]) > abs(matrix[t][c])) t = i; // 找出主元绝对值最大的那一行
7
        }
8
        if (abs(matrix[t][c]) < EPS) continue; // 非零才能消成1
9
        if (t != r) swap(matrix[t], matrix[r]); // 交换
10
        for (int i = n + 1; i >= c; i--) matrix[r][i] /= matrix[r][c]; // 主元消成1
11
        for (int i = 1; i <= n; i++) { // 反复消元，成为对角线矩阵
12
            if (abs(matrix[i][c]) > EPS && i ^ r) { // 当前行不消，若当前位已经是零了也不消
13
                for (int j = n + 1; j >= c; j--) {
14
                    matrix[i][j] -= matrix[i][c] * matrix[r][j]; // 消成零
15
                }
16
            }
17
        }
18
        r++;
19
        rank++;
20
    }
21
    if (rank < n) {
22
        // 无解or无数组解
23
        for (int i = rank + 1; i <= n; i++) {
24
            for (int j = 1; j <= n + 1; j++) {
25
                if (abs(matrix[i][j]) > EPS) return NO_SOLUTION; // 无解
26
            }
27
        }
28
        for (int i = 1; i <= n; i++) {
29
            for (int j = 1; j <= n; j++) {
30
                if (abs(matrix[i][j]) > EPS) {
31
                    ans[j] = matrix[i][n + 1]; // 无数组解，找到主元并直接赋值，剩余的自由元自动赋值为0
32
                    break;
33
                }
34
            }
35
        }
36
        return INFINITE_SOLUTIONS;
37
    }
38
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有唯一解，此时常数项即为答案
39
    return UNIQUE_SOLUTION;
40
}

1
int gauss() {
2
    int rank = 0; // 矩阵的秩
3
    for (int c = 1, r = 1; c <= n; c++) {
4
        int t = r;
5
        for (int i = r; i <= n; i++) {
6
            if (matrix[i].test(c)) {
7
                // 找到绝对值最大的行（只要第一个系数是 1 即可）
8
                t = i;
9
                break;
10
            }
11
        }
12
        if (!matrix[t].test(c)) continue; // 跳过零行
13
        if (t ^ r) swap(matrix[r], matrix[t]); // 交换到第一行
14

15
        for (int i = 1; i <= n; i++) {
16
            // 与普通高斯消元的不同之处，对 1~n 行全部消元
17
            if (matrix[i].test(c) && i ^ r) {
18
                // 当前行不消，零行不消
19
                matrix[i] ^= matrix[r]; // 异或代替减法进行消元
20
            }
21
        }
22
        r++;
23
        rank++;
24
    }
25
    if (rank < n) {
26
        // 秩小于 n，可能是无数组解、有可能无解
27
        for (int i = rank + 1; i <= n; i++) {
28
            if (matrix[i].test(n + 1)) return NO_SOLUTION; // 存在类似于 0=k 的矛盾情况，无解
29
        }
30
        for (int i = 1; i <= n; i++) {
31
            for (int j = 1; j <= n + 1; j++) {
32
                if (matrix[i].test(j)) {
33
                    // 无数组解，找到主元并赋值
34
                    ans[j] = matrix[i][n + 1];
35
                    break;
36
                }
37
            }
38
        }
39
        return INFINITE_SOLUTIONS;
40
    }
41
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有唯一解，对角矩阵每个未知数的解就是常数项的值
42
    return UNIQUE_SOLUTION;
43
}

第一节 什么是矩阵乘法#

你经常能在各种线性代数的书上看到这样一串定义式：。这对于自学者（比如说我自己）其实是非常不友好的。他们在举例计算时很容易被 绕进去，不仅计算速度慢不说，还很容易出错…… 那我在此举出一个简记方法：

将左边的矩阵的每一行看作每个未知数都代了确定值的方程、右边的矩阵每一列看作是前者方程的未知数系数。二者相乘本质上就是让未知数和系数匹配上，并计算出结果放入结果矩阵的特定位置。这个特定位置也有讲究，假如选择了前一个矩阵的 行和后一个矩阵的 列进行运算，求和过后的答案应该放在答案矩阵的 位置。看以下例子来加深理解：

那么什么样的矩阵才能进行乘法运算呢？答案是一个 和一个 的矩阵。观察规律，我们发现前矩阵的列数需要等于后矩阵的行数。根据如上概括的矩阵乘法的意义——即搭配未知数与系数。显然，当后一个矩阵的列数大于前一个矩阵的行数时，我们进行系数配对时就会发现多出几个失配的系数。矩阵乘法国不养闲人，这种单身汉显然是不可以光天化日下大摇大摆出来遛弯的。因此保证其中一个矩阵的行数等于另一个矩阵的列数后方可相乘。

类比四则运算的乘法，矩阵乘法是否也有结合律、分配律和交换律呢？很遗憾，不完全是，前二者是矩阵乘法运算所具备的性质、但最后那个交换律不是。不是所有的矩阵相乘都满足乘法交换律。但是还是有满足交换律的特例：同型零矩阵相乘、一个矩阵（可逆）和它的逆矩阵相乘，矩阵乘法满足交换律的充要条件证明过于复杂烧脑，此处不做陈述主要是我也不会证满足交换律的充要条件 qwq……。

例 2.1.1 Akasha Browser with Irminsul Kernel 世界树搜索引擎#

你作为刚刚清除了须弥世界树痼疾的英雄旅行者，突然对虚空终端的运作方式有了兴趣。你从大贤者那里了解逼问到，虚空终端实质上是一个仅显示搜索结果的前端程序，但关键词搜索功能却是基于须弥地下空间的世界树。带着这个疑问，你再次来到了世界树前，见到了小吉祥草王大人，希望能让她告诉你世界树的运作方式……

背景知识： 很多浏览器的检索功能都依赖于矩阵运算，这里属于最简单的一种——我们只需要矩阵的乘法运算（某些情况下会用到转置，甚至正交性）。然而随着科技的快步发展，数据量的快速增加，这种方式如今只在很小的范围内被使用（由于码量小思维简单，它有时会在个人博客的关键词搜索功能中被用到）；目前广泛使用的一种是向量相似性搜索，它本质上是在一定范围内搜索与目标向量辐角最为接近的已有向量，在“矩阵的几何表示” 章节中会涉及到。这里介绍的是简单匹配搜索。

问题分析：因为矩阵乘法本质上是未知数和系数的配对求值，我们需要构造一个方法来使得“搜索内容” 和“已有内容” 配对。并且搜索引擎总会返回与你搜索的内容最为相似的结果，搜索“比尔・盖茨”，第一条肯定是关于他个人的介绍，而绝对不可能是一则寻狗启示……因此，我们设计的矩阵必须能在经历一轮运算后能够正确返回每个关键词出现的频率（简单点说就是出现次数），这样虚空终端才能对频率进行排序，并返回频率最大的那个结果。

算法设计：不妨考虑这样几个矩阵 —— 其中一个存储关键词、另一个存储搜索内容。比如我需要将几篇论文（为方便使用英文表示，并且假设词根相同的单词为同一个单词，即不考虑词汇变形）《Basic Structure of Elemental Monuments》（元素方碑的底层构造）、《Junior Elemental Reaction》（初等元素反应）、《Advanced Elemental Theory》（高等元素论）、《Architectural Structure in the Mausoleum of King Deshret》（赤王陵的建筑结构）以及《Advanced Sumeru Linguistic Analysis》（高等须弥语音学解析）。我们在此次挑选一些关键词存储（方便读者观察）：Structure、Element、Junior 和 Advanced。为每篇论文编号 1-5，矩阵如下图：

假如热爱学习的艾尔海森来到了教令院的大图书馆，它想测试一下这全新开发的文献查询系统，输入了 Advanced 一词。假设已录入数据库就是以上形式，我们如何构造一个“查询矩阵” 来和数据库矩阵进行运算呢？

首先根据矩阵乘法的前提要求，这个查询矩阵必须是四行。不妨让每行代表我们的词库词语，艾尔海森输入的是 Advanced—— 即对应数据库矩阵的第四列（未知数），我们要配对它的系数，因此它必须在第四行，才能保证系数正确匹配未知数。同理，查询矩阵的第一行对应 Structure、第二行 Element、第三行 Junior。他输入了一个 Advanced，因此我们的查询矩阵如下图：

乘法的目的是将二者匹配起来，得到的结果如下图：

返回矩阵的数字代表关键词在对应数据库项中的出现次数，也就是说，如果此时再加入一篇论文《Advanced Usage of the Word Advanced》（“Advanced” 一词的进阶用法），返回矩阵的最后一行（第六行）会出现一个 。经过虚空终端的一轮排序，它自然就会来到第一位的位置。如果要分别查询两个不同关键词，在查询矩阵右侧再加一列即可，返回矩阵中多出的一列就是新关键词的出现次数；如果需要同时查询两个关键词，在同一列对应位置写入 即可……

例 2.1.2 Light Novel Query 轻小说查询#

八重堂的主编八重神子最近在为轻小说的事情发愁…… 并不是因为销量不够，正相反：八重堂最近推出了一项跨国销售项目，各种经典作品被远销往了枫丹廷。这就牵涉出一个问题 —— 枫丹的市民们不想远离枫丹城区、横穿须弥沙漠、翻越璃月高山、躲避稻妻雷暴就为了看一看有哪些轻小说符合自己的独特口味…… 于是八重神子找到了见多识广的你，希望你能帮她做出一套轻小说内容检索系统。当然作为报酬给你的原石和摩拉是肯定是不会少的……

当然，这套系统有一定要求。因为有很多轻小说为了吸引读者，取的标题和内容是完全对不上号的，神子的想法是做一套正文内容检索 —— 每本轻小说的总字数在出版时就统计好了，但是苦于稻妻的信息存储技术不是很发达，神子希望存储在数据库矩阵里的数据尽可能小。请问该如何设计符合要求的存储算法？

问题分析：每本书中特定的词可能重复出现成百上千次（同样用英文单词表示，且同词根不同词形的两个词算作同一个单词参与计数），我们的要求是让数据尽可能小，既然总字数都已经给出了，我们不妨使用指定词出现的频率来表示这个词的出现次数（单词出现次数 = 全书总词数 × 出现频率）。这样的搜索方法叫做相对频率搜索。

算法设计：大致原理和例 2.1.1 里的一模一样，只是数据库矩阵存储的不再是出现总次数，而是对应词的相对频率。因而图例 2.1.3 可以变化为如下形式：

明显一看，第三篇文章出现 Advanced 的频率最高，应该优先返回。但是这个例子并不是很好（明明说了按内容搜索你还在这搜索标题），但是当加入大量的正文内容时，这个方法的优势也就体现出来了。这里由于篇幅原因就不举过于复杂的例子，本例仅作对相对频率搜索的原理的理解。

第二节 初等矩阵与矩阵递推#

假设存在一个 的单位矩阵 ，对 只进行一次初等行变换得到的矩阵叫做初等矩阵，通常用 表示。一个矩阵的行变换和列变换都可以用初等矩阵的乘法进行。

仅交换了两行的单位矩阵称作第 I 类初等矩阵（只进行了初等行变换第一条），将它左乘到一个矩阵前，可以进行相应的行运算；右乘到一个矩阵后可以进行相应的列运算。比如，一个第 I 类初等矩阵 （交换第一、二行），和一个 矩阵 。左乘就是 （交换一、二行）；右乘就是 （交换一、二列）。

仅将某一行乘以一个非零倍数的矩阵叫做第 II 类初等矩阵（只进行了初等行变换第二条），左乘行运算、右乘列运算。例如一个第 II 类初等矩阵 （第一行乘 3）和一个 矩阵 。（第一行乘 3）；（第一列乘 3）。

仅将某一行的非零倍加到另一行上的矩阵叫做第 III 类初等矩阵（只进行了初等行变换第三条），同样是左乘行运算、右乘列运算，但是有一点点小不同，不要根据思维定势随便写答案！例如一个第 III 类初等矩阵 （第二行乘 2 加到第一行）和祖传的矩阵 。（第二行的 2 倍加到第一行）；（第一列的 2 倍加到第二列）。注意初等矩阵的行列变换与乘法后矩阵的行列变换，哪一行/列乘了倍数、哪一行/列被加上了！

因此我们可以不必使用高斯消元，仅使用初等矩阵乘法也可以达到将普通矩阵消元变成最简行阶梯形矩阵！而且它可以进行列运算，甚至比高斯消元法更高级一点。

接下来是我们的矩阵递推。大家都知道斐波那契数列，它的前两项均为 1，此后的每一项都是前两项之和，即 。大多数信息竞赛生在学习到递归算法时都会被要求写程序求解斐波那契数列的某一项，当然代码也非常的简单，如下：

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
long long fib(int n)
5
{
6
    if (n == 1 || n == 2)
7
        return 1;
8
    return fib(n - 1) + fib(n - 2);
9
}
10

11
int main()
12
{
13
    int n;
14
    cin >> n;
15
    cout << fib(n) << endl;
16
    return 0;
17
}

这段代码其实就是照搬了上面的通项公式，但是递归有个弊端就是效率和内存，当 为百万级别、甚至十亿级别时它就显得很小丑了。那么我们如何用矩阵加速计算呢？我们用斐波那契数列的递推来向读者介绍矩阵递推的操作方法：

首先我们将通项公式变成我们想要求的形式，为了便于输出，要求结果矩阵的第一个元素就是答案，因此结果矩阵就是：。又因为 ，并且 。我们还需要保证初始矩阵在经历一轮变换前后，始终都是同型的，这里是 的矩阵，操作后也应该是 的矩阵。于是我们的递推矩阵应该是一个 矩阵。不妨将递推矩阵 的每一行从上至下分别表示为 和 的系数，由以上二式可得：。别急，左边还有一列未填满 —— 我们希望每次操作都会把矩阵元素整体向左移一个位置，就好像一个滑动窗口（但不是单调队列），我们的第一列也可以求出来了。最终就是

那么求数列第 项 —— 每次右乘 都相当于多求出一项，并且当 只被乘了一次时，结果矩阵的第一个元素是 。因此要让第 项来到第一个位置，我们需要进行 次乘法， 也就是 的第一行第一列元素。可以写出如下代码：

1
#include <bits/stdc++.h>
2
#define MOD 1000000007
3
#define N 15
4
using namespace std;
5

6
typedef long long ll;
7

8
int n = 2; // 递推矩阵行列数均为2
9

10
struct Matrix {
11
    ll mat[N][N];
12

13
    Matrix()
14
    {
15
        memset(mat, 0.0, sizeof mat); // 初始化时内部变量自动置零，无需每次定义变量时再置零
16
    }
17

18
    void I()
19
    {
20
        for (int i = 1; i <= n; i++)
21
            mat[i][i] = 1; // 构造2×2单位矩阵
22
    }
23
};
24

25
Matrix operator*(const Matrix& l, const Matrix& r)
26
{
27
    // 重载乘法运算符，实现矩阵乘法
28
    Matrix res;
29
    for (int k = 1; k <= n; k++) {
30
        for (int i = 1; i <= n; i++) {
31
            for (int j = 1; j <= n; j++) {
32
                // res.mat[i][j] = (res.mat[i][j] + l.mat[i][k] * r.mat[k][j] % MOD) % MOD; // 取模用这个
33
                res.mat[i][j] += l.mat[i][k] * r.mat[k][j];
34
            }
35
        }
36
    }
37
    return res;
38
}
39

40
Matrix qpow(Matrix a, ll b)
41
{
42
    Matrix res;
43
    res.I(); // 单位矩阵相当于实数运算中的 1，因此任何矩阵乘以一个单位矩阵的结果都是这个矩阵
44
    while (b) {
45
        if (b & 1)
46
            res = res * a;
47
        a = a * a;
48
        b >>= 1;
49
    }
50
    return res;
51
}
52

53
int main()
54
{
55
    int a;
56
    cin >> a;
57

58
    Matrix A;
59
    A.mat[1][1] = A.mat[1][2] = 1; // 初始矩阵
60
    Matrix M;
61
    M.mat[1][2] = M.mat[2][2] = M.mat[2][1] = 1; // 递推矩阵
62
    A = A * qpow(M, a - 1);
63
    cout << A.mat[1][1] << endl;
64
    return 0;
65
}