\n \n {children}\n \n

\n );\n};\n\nexport default memo(Markdown, (prev, next) => prev.children === next.children);\n```\n\n","1741931826826",1741929279500,{"_12":128,"_33":129,"_35":130,"_37":131,"_39":132,"_41":133,"_43":134,"_45":135,"_47":46,"_48":46,"_49":24,"_50":51,"_26":136,"_28":137,"_53":186},{"_55":128,"_56":139,"_58":140,"_59":141},[188,192,196],{"_12":189,"_64":190,"_66":46,"_68":46,"_26":191,"_71":-5},"223831259095511040","hackertalk",1631173530752,{"_12":193,"_64":194,"_66":46,"_68":46,"_26":195,"_71":-5},"223454822580588544","editor",1631083781293,{"_12":63,"_64":65,"_66":67,"_68":69,"_26":70,"_71":-5},{"_73":180,"_74":57,"_75":57,"_76":30,"_77":198},114,[200],{"_12":96,"_33":102,"_35":103,"_37":46,"_39":104,"_41":105,"_43":44,"_45":46,"_47":46,"_48":46,"_49":24,"_50":51,"_26":106,"_28":107,"_53":201},{"_55":96,"_56":109,"_58":57,"_59":57},{"_12":203,"_14":204,"_5":16,"_17":205,"_19":206,"_21":207,"_23":24,"_25":24,"_26":208,"_28":208,"_29":30,"_31":209,"_60":222,"_53":235,"_79":237,"_81":24,"_82":24},"680159203975041024","382223475323219968","OI 中输入输出那些事","> 本文是为了教一个小学弟写的，为了文章完整性我全面总结了一些 OI 中经常用到的哪些输入输出技巧以及注意事项\n\n## `std::cin` 与 `std::cout`\n\n我相信你的第一行 C++ 代码一定是下面这个：\n\n```cpp\n#include \n\nusing namespace std;\n\nint main() {\n cout << \"Hello, world!\" << endl;\n return 0;\n}\n```\n\n接下来你一定还学过 `cout` 用于输入。但是这里有两个小问题，第一是在 CCF 举办的 NOI 赛事中，使用 `using namespace std` 有概率导致你的程序在 Windows 平台正常运行但在测评环境出错；第二是 `endl` 会强制刷新缓冲区，导致输出效率变慢。所以我更推荐你使用下面的写法：\n\n```cpp\n#include \n\nint main() {\n std::cout << \"Hello, world!\" << '\\n';\n return 0;\n}\n```\n\n顺带讲一下 `using namespace std` 的作用吧。这行代码表示“使用 `std` 命名空间”。如果你不理解，那么你只需要记住，使用这行代码可能会导致你的一些变量名与内置的一些符号产生冲突，经典的案例就是 `next` 和 `y0` 等。删除这一行代码之后，你无脑的在调用内置函数之前加上 `std::` 前缀即可。特别的，如果某个函数添加 `std::` 后出现问题但不添加就能正常运行，那你无脑不添加就好了，这往往是由于某些 C 语言的特性与 C++ 冲突而编译器不能很好地处理导致的。\n\n### `std::getline`\n\n另外值得一提的是，你可以使用 `std::getline` 读取一整行输入：\n\n```cpp\nstd::string s;\nstd::getline(std::cin, s);\n```\n\n另外还有一个 `getline` 方法可用于输入一行内容到 `char[]`：\n\n```cpp\nchar s[256];\nstd::cin.getline(s, 256);\n```\n\n## `printf` 与 `scanf`\n\n想必你一定也见过这两个函数。敏锐的你也许会注意到，这两个函数我并没有添加 `std::`，这是由于这两个函数源自 C 语言，因此也被称为 C 风格输入输出；相应地，`std::cin` 与 `std::cout` 被称为 C++ 风格的。你也许经常听到有人说这 C 风格的输入输出比 C++ 风格的更快，在一般情况下确实如此。\n\n顺带一提的是 C 风格输入输出的格式化字符串，这里给出一个列表用于快速查询：\n\n**整数类型**\n\n* **有符号整数**\n * `%d` 或 `%i`: 十进制整数\n * `%ld` 或 `%li`: 长整型（`long int`）\n * `%lld` 或 `%lli`: 长长整型（`long long int`）\n* **无符号整数**\n * `%u`: 无符号十进制整数（`unsigned int`）\n * `%lu`: 无符号长整型（`unsigned long int`）\n * `%llu`: 无符号长长整型（`unsigned long long int`）\n* **八进制**\n * `%o`: 八进制整数（默认为`int`）\n * `%lo`: 无符号长整型的八进制表示（`unsigned long int`）\n * `%llo`: 无符号长长整型的八进制表示（`unsigned long long int`）\n* **十六进制**\n * `%x` 或 `%X`: 十六进制整数（小写或大写字母）（默认为`int`）\n * `%lx` 或 `%lX`: 无符号长整型的十六进制表示（`unsigned long int`）\n * `%llx` 或 `%llX`: 无符号长长整型的十六进制表示（`unsigned long long int`）\n\n**浮点数类型**\n\n* **小数形式**\n * `%f`: 小数形式的浮点数（默认为`double`）\n * `%lf`: 双精度浮点数（`double`）\n * `%Lf`: 长双精度浮点数（`long double`）\n* **科学计数法**\n * `%e` 或 `%E`: 科学计数法表示的浮点数（小写或大写字母'e'）（默认为`double`）\n * `%le` 或 `%lE`: 双精度浮点数的科学计数法表示（`double`）\n * `%Le` 或 `%LE`: 长双精度浮点数的科学计数法表示（`long double`）\n* **自动选择格式**\n * `%g` 或 `%G`: 根据数值大小自动选择`%f`或`%e`（小写或大写字母）（默认为`double`）\n * `%lg` 或 `%lG`: 双精度浮点数的自动选择格式（`double`）\n * `%Lg` 或 `%LG`: 长双精度浮点数的自动选择格式（`long double`）\n\n**字符和字符串**\n\n* `%c`: 单个字符\n* `%s`: 字符串\n\n**指针**\n\n* `%p`: 指针地址\n\n**其他**\n\n* `%n`: 将当前已读取或写入的字符数量存入指向的整型变量中\n* `%%`: 输出百分号本身\n\n**精度和宽度控制**\n\n* **宽度控制**\n * `%5d`: 最少占用5个字符宽度，不足部分用空格填充（左对齐时加`-`，如`%-5d`）\n * `%05d`: 最少占用5个字符宽度，不足部分用0填充\n* **精度控制**\n * `%.2f`: 小数点后保留2位小数\n * `%.3e`: 科学计数法表示，小数点后保留3位小数\n * `%.4g`: 自动选择格式，小数点后最多保留4位有效数字\n\n事实上，这样的输入输出方式虽然有不少优点，但是也有不少弊端，因此我不是很推荐这种写法。\n\n## 同步流对速度的影响\n\n前面提到，C 风格的输入输出往往比 C++ 的更快，这是由于默认情况下 C++ 的输入输入输出需要与 C 风格的同步，借助于所谓同步流。我们可以通过关闭同步流解决这一问题：\n\n```cpp\nstd::cin.tie(nullptr)->sync_with_stdio(false);\n```\n\n只需要在 `main` 函数第一行添加上这句代码就可以了，此时 C++ 风格的速度往往与 C 风格的相同甚至更优。需要注意的是，使用这行代码后，你最好不要再使用 C 风格的输入输出，否则极有可能因为没有同步而导致出 bug。\n\n实际上，这行代码不仅关闭了同步流，还解除了 `std::cin` 与 `std::cout` 的绑定，也能在一定程度上提升速度。\n\n## 奇技淫巧：快读快写\n\n你也许还学过所谓快读快写，使用 `getchar` 和 `putchar` 来优化输入输出，像下面这样：\n\n```cpp\nint read() {\n int x = 0, w = 1;\n char ch = 0;\n while (ch < '0' || ch > '9') { // ch 不是数字时\n if (ch == '-') w = -1; // 判断是否为负\n ch = getchar(); // 继续读入\n }\n while (ch >= '0' && ch <= '9') { // ch 是数字时\n x = x * 10 + (ch - '0'); // 将新读入的数字「加」在 x 的后面\n // x 是 int 类型，char 类型的 ch 和 '0' 会被自动转为其对应的\n // ASCII 码，相当于将 ch 转化为对应数字\n // 此处也可以使用 (x<<3)+(x<<1) 的写法来代替 x*10\n ch = getchar(); // 继续读入\n }\n return x * w; // 数字 * 正负号 = 实际数值\n}\n\nvoid write(int x) {\n static int sta[35];\n int top = 0;\n do { sta[top++] = x % 10, x /= 10; } while (x);\n while (top) putchar(sta[--top] + 48); // 48 是 '0'\n}\n```\n\n需要注意的是，`putchar` 与 `getchar` 都是 C 风格的，因此与关闭同步流的 C++ 风格输入输出不兼容。\n\n当然了，还有更多复杂的技巧，但是个人不推荐使用也不推荐了解。这是由于在输入输出上花费这么多时间和精力得不偿失，只有毒瘤题会折腾输入输出。\n\n## 文件读写之 `freopen`\n\n`freopen` 可用于重定向输入输出到指定文件，使用格式如下：\n\n```cpp\nfreopen(\"test.in\", \"r\", stdin);\nfreopen(\"test.out\", \"w\", stdout);\n```\n\n将这两行代码添加到 `main` 函数开头就可以了。\n\n这也是一个 C 风格的函数，因此不建议使用。优点是可以通过注释或取消注释这两行代码快速实现文件读写与控制台输入输出的切换。\n\n## 文件读写之 `fopen`\n\n这种文件读写也是 C 风格的，请自行阅读示例代码：\n\n```cpp\nFILE *in_file = fopen(\"test.in\", \"r\"),\n *out_file = fopen(\"test.out\", \"w\");\nint number;\n// 从输入文件读取整数\nfscanf(in_file, \"%d\", &number);\n// 写入输出文件\nfprintf(out_file, \"%d\", number);\n// 关闭文件\nfclose(in_file);\nfclose(out_file);\n```\n\n在竞赛中没什么优势，不推荐使用。\n\n## C++ 风格文件流\n\n全文的重头戏来了！使用 C++ 风格的文件流进行文件读写不仅可以获得极致的速度，还能拥有舒适便捷的编码体验。只需要在 `main` 函数开头使用下面的代码打开文件：\n\n```cpp\nstd::ifstream fin(\"test.in\");\nstd::ofstream fout(\"test.in\");\n```\n\n接下来就可以使用 `fin` 与 `fout` 替换 `std::cin` 与 `std::cout` 进行文件读写：\n\n```cpp\nint n;\nfin >> n;\nfout << n << '\\n'; // 仍然不推荐使用 `std::endl` 用于换行\n\nstd::string str;\nstd::getline(fin, str);\n\nchar s[256];\nfin.getline(s, 256);\n```\n\n当然了，你还可以通过添加下面的代码对 `std::cin` 与 `std::cout` 重定向：\n\n```cpp\nstd::cin.rdbuf(fin.rdbuf());\nstd::cout.rdbuf(fout.rdbuf());\nstd::cin.tie(nullptr)->sync_with_stdio(false);\n```\n\n这样就可以照常使用 `std::cin` 与 `std::cout` 进行文件读写了。同时可以通过注释或取消注释这两行代码实现文件读写与控制台输入输出的切换。有测试表明这种方法是不使用奇技淫巧的前提下的普遍最优读写方式。\n\n## C++ 风格格式化输入输出\n\n以下是C++中常用的输入输出格式化控制方法示例：\n\n```cpp\n// 1. 浮点数精度控制\ndouble pi = 3.1415926535;\nstd::cout << std::fixed << std::setprecision(2) << pi << \"\\n\"; // 输出3.14\nstd::cout << std::scientific << pi << \"\\n\"; // 输出3.14e+00\n\n// 2. 数值进制控制\nint num = 255;\nstd::cout << std::hex << num << \"\\n\"; // 输出ff\nstd::cout << std::oct << num << \"\\n\"; // 输出377\nstd::cout << std::dec << num << \"\\n\"; // 恢复十进制\n\n// 3. 宽度与填充\nstd::cout << std::setw(10) << std::setfill('*') << 123 << \"\\n\"; // 输出*******123\n\n// 4. 对齐方式\nstd::cout << std::left << std::setw(10) << \"Hello\" << \"\\n\"; // 左对齐\nstd::cout << std::right << std::setw(10) << \"World\" << \"\\n\"; // 右对齐\n\n// 5. 其他常用格式\nstd::cout << std::boolalpha << true << \"\\n\"; // 输出true（而非1）\nstd::cout << std::showpos << 42 << \"\\n\"; // 输出+42\nstd::cout << std::uppercase << 3.14e2 << \"\\n\"; // 输出3.14E+02\n\n// ========== 输入格式化 ==========\nint year, month;\n// 输入格式：YYYY/MM\nstd::cin >> year >> std::ws; // 跳过空白字符\nstd::cin.ignore(1); // 跳过分隔符'/'\nstd::cin >> month;\n\n// 恢复默认设置\nstd::cout.unsetf(std::ios::fixed | std::ios::scientific);\nstd::cout.precision(6); // 恢复默认精度\n```\n\n**常用格式化操作符对照表**：\n\n| 操作符/函数 | 作用 | 示例效果 |\n| ------------------------ | ----------------------- | ------------------------ |\n| `std::setprecision(n)` | 设置浮点数精度 | `3.1416` → `3.14` |\n| `std::fixed` | 固定小数位显示 | `123.456` → `123.46` |\n| `std::scientific` | 科学计数法显示 | `1234.5` → `1.2345e+03` |\n| `std::hex`/`std::oct` | 十六进制/八进制显示 | `255` → `ff` / `377` |\n| `std::setw(n)` | 设置字段宽度 | `123` → `\" 123\"` |\n| `std::setfill(c)` | 设置填充字符 | `123` → `\"****123\"` |\n| `std::left`/`std::right` | 左对齐/右对齐 | `\"Hello\"` → `\"Hello \"` |\n| `std::boolalpha` | 布尔值文字显示 | `true` → `\"true\"` |\n| `std::showpos` | 显示正数符号 | `42` → `+42` |\n| `std::uppercase` | 大写格式（与hex/scientific配合） | `0xff` → `0XFF` |\n\n**重要特性**：\n\n1. **持久性设置**：多数格式设置会保持生效，直到被显式修改\n2. **作用域控制**：可通过`{}`限定格式作用范围\n\n ```cpp\n {\n std::ios_base::fmtflags f = std::cout.flags(); // 保存状态\n std::cout << std::hex << 255; // 临时使用十六进制\n std::cout.flags(f); // 恢复状态\n }\n ```\n3. **性能影响**：频繁切换格式设置可能影响I/O性能（建议批量处理）\n\n## 对结构体添加输入输出支持\n\n这部分相当简单，请看示例代码：\n\n```cpp\nstruct person {\n std::string name;\n int age;\n\n friend std::istream &operator>>(std::istream &is, const person &p) {\n is >> p.name >> p.age;\n return is;\n }\n friend std::ostream &operator<<(std::ostream &os, const person &p) {\n os << p.name << \": \" << p.age;\n return os;\n }\n};\n\nperson p;\nstd::cin >> p;\nstd::cout << p << '\\n';\n```","1739973610963",1739970590963,{"_12":204,"_33":210,"_35":211,"_37":212,"_39":213,"_41":214,"_43":44,"_45":215,"_47":46,"_48":46,"_49":24,"_50":51,"_26":216,"_28":217,"_53":218},"Expector","gh_BU3uOcd0sAA","『我是星 \\\n我愿投身前途未卜的群星 \\\n为梦长明 \\\n让希望 \\\n做我无声永存的墓志铭』\n\n如无说明，本人作品均使用CC BY-NC-ND进行许可，代码使用MIT许可","u/avatar/KKoP5V-OJ0gYAN","users/-/covers/10d18bcc-1ab4-47a7-bbf5-70266177c2fe","https://expector.netlify.app/",1668937177885,1693107989977,{"_55":204,"_56":219,"_58":220,"_59":221},60,10,9,[223,229],{"_12":224,"_64":225,"_66":226,"_68":227,"_26":228,"_71":-5},"223247345129844736","c++","tag/cplusplus.svg","一种被广泛使用的计算机程序设计语言，最早由 Bjarne Stroustrup 在贝尔实验室创建，作为 C 语言的增强版本，C++ 与 C 的代码执行效率往往相差在 ±5% 之间",1631034314814,{"_12":230,"_64":231,"_66":232,"_68":233,"_26":234,"_71":-5},"223244278292508672","c","tag/c.svg","C 是一种通用编程语言，最早出现在1972年，为了移植与开发UNIX操作系统，由丹尼斯·里奇与肯·汤普逊，以B语言为基础，在贝尔实验室设计、开发出来",1631033583623,{"_73":203,"_74":57,"_75":30,"_76":30,"_77":236},151,[],{"_12":239,"_14":204,"_5":16,"_17":240,"_19":241,"_21":242,"_23":24,"_25":24,"_26":243,"_28":243,"_29":30,"_31":244,"_60":246,"_53":257,"_79":259,"_81":24,"_82":24},"676130204843180032","[OI 向] 深入理解二阶线性递推","> 本文主要面向普及/提高组 OIer 和 ACMer。考虑大多数 OIer 的情况，本文默认读者只会矩阵乘法，不了解矩阵的行列式，矩阵的秩等内容。本文使用 C++ 编写代码示例。\n\n## 什么是二阶线性递推\n\n二阶线性递推数列在 OI 界还有个著名的名字：[广义斐波那契数列](https://www.luogu.com.cn/problem/P1349)。其所指为如下数列 $\\{a_n\\}$：\n\n$$\na_{n} = pa_{n - 1} + qa_{n - 2}\n$$\n\n其中，$p,q\\in \\mathbb{R}$，数列前两项为 $a_0, a_1$。\n\n由于该数列的递推关系是线性的，且每一项都和前两项有关，因此称为二阶线性递推数列。\n\n### 斐波那契数列与朴素算法\n\n当前文的数列 $\\{a_n\\}$ 中 $p=q=1,a_0=a_1=1$ 时，该数列就是大名鼎鼎的斐波那契数列 $\\{f_n\\}$：\n\n$$\nf_n=f_{n-1}+f_{n-2}\n$$\n\n基于这样的递推关系，我们可以写出线性复杂度 $\\mathcal{O}(n)$ 的朴素算法：\n\n```cpp\nint f(int n) {\n if (n == 0 || n == 1) {\n return 1;\n }\n return f(n - 1) + f(n - 2);\n}\n```\n\n对于较为[简单的情况](https://www.luogu.com.cn/problem/P1720)，这样的算法是可以接受的。\n\n我们可以很容易的推广到更一般的情况，所以对于一般的二阶线性递推的朴素算法就留给读者练习吧。\n\n## 通过矩阵乘法来优化递推\n\n直接根据递推式计算虽然简单，但是实在是太慢了，我们需要优化。如果你还没有学过矩阵乘法，请移步至 [OI Wiki](https://oi-wiki.org/math/linear-algebra/matrix/#%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95)（记得顺便把方阵的逆看看，后面要用）。如果你学过矩阵乘法，应当对下面的式子不陌生（如果你对这个式子有点陌生的话，请尝试手动计算左面的矩阵乘法）：\n\n$$\n\\begin{bmatrix}\n f_{n-1} & f_{n-2}\n\\end{bmatrix}\n\\begin{bmatrix}\n 1 & 1\\\\\n 1 & 0\n\\end{bmatrix}\n=\n\\begin{bmatrix}\n f_{n} & f_{n-1}\n\\end{bmatrix}\n$$\n\n这个式子旨在将斐波那契递推关系用矩阵乘法表示，以进行进一步的操作。其中 $\\begin{bmatrix}f_{n-1} & f_{n-2}\\end{bmatrix}$ 被称为状态矩阵（在本例中，它也是个向量），$\\begin{bmatrix} 1 & 1\\\\ 1 & 0\\end{bmatrix}$ 被称为转移矩阵。这样的转移在线性代数中属于线性变换，其中转移矩阵被称为线性算子。我们可以很容易的推广到一般的二阶线性递推上：\n\n$$\n\\begin{bmatrix}\n a_{n-1} & a_{n-2}\n\\end{bmatrix}\n\\begin{bmatrix}\n p & 1\\\\\n q & 0\n\\end{bmatrix}\n=\n\\begin{bmatrix}\n a_{n} & a_{n-1}\n\\end{bmatrix}\n$$\n\n据此可以得出使用矩阵乘法表示的二阶线性递推的通项公式：\n\n$$\n\\begin{bmatrix}\n a_{n} & a_{n-1}\n\\end{bmatrix}\n=\n\\begin{bmatrix}\n a_0 & a_1\n\\end{bmatrix}\n\\begin{bmatrix}\n p & 1\\\\\n q & 0\n\\end{bmatrix}^n\n$$\n\n通过矩阵快速幂算法就可以将算法优化到对数复杂度 $\\mathcal{O}(\\log n)$，这在一般情况下已经是最优的了（至于是不是真的是最优的，我也不知道，我也不会证）。\n\n代码也是很好实现的，以斐波那契为例：\n\n```cpp\nusing vec = array;\nstruct matrix : public array {\n using array::array;\n matrix(const vec &a, const vec &b) : array{a, b} {\n (*this)[0] = a;\n (*this)[1] = b;\n }\n matrix &operator*=(const matrix &other) {\n matrix res{};\n for (int i{0}; i < 2; ++i)\n for (int j{0}; j < 2; ++j)\n for (int k{0}; k < 2; ++k)\n res[i][j] += (*this)[i][k] * other[k][j];\n return *this = res;\n }\n} e{{1, 0}, {0, 1}};\n\nmatrix qpow(matrix x, int n) {\n auto res{e};\n while (n) {\n if (n & 1)\n res *= x;\n x *= x, n >>= 1;\n }\n return res;\n}\n\nint fib(int n) {\n return qpow(matrix{{1, 1}, {1, 0}}, n)[0][0];\n}\n```\n\n### 一种更有趣的优化算法\n\n> 接下来的这部分内容会有点抽象，如果你学过抽象代数那看这部分内容就再好不过了。\n\n我们可以找到另一种递推的矩阵表示：\n\n$$\n\\begin{bmatrix}\n a_{n-1}\\color{red}{\\cdot p+}qa_{n-2} & a_{n-1}\\color{red}{\\cdot q}\\\\\n a_{n-1} & qa_{n-2}\n\\end{bmatrix}\n\\begin{bmatrix}\n 1\\color{red}{\\cdot p+}0 & 1\\color{red}{\\cdot q}\\\\\n 1 & 0\n\\end{bmatrix}\n=\n\\begin{bmatrix}\n a_{n}\\color{red}{\\cdot p+}qa_{n-1} & a_{n}\\color{red}{\\cdot q}\\\\\n a_{n} & qa_{n-1}\n\\end{bmatrix}\n$$\n\n如果你乍一眼看不出来，可以计算一下。为了找到这个式子，我思考了一个晚上。注意到在这个式子中所有的矩阵都形如：\n\n$$\n\\begin{bmatrix}\n a\\color{red}{\\cdot p+}b & a\\color{red}{\\cdot q}\\\\\n a & b\n\\end{bmatrix}\n$$\n\n每个矩阵都只与两个元素有关，因此我们可以使用一个二元组来表示这类矩阵，并定义二元组上的乘法：\n\n$$\n\\begin{aligned}\n(a,b)*(c,d)&=\\begin{bmatrix}\n a\\color{red}{\\cdot p+}b & a\\color{red}{\\cdot q}\\\\\n a & b\n\\end{bmatrix}\n\\begin{bmatrix}\n c\\color{red}{\\cdot p+}d & c\\color{red}{\\cdot q}\\\\\n c & d\n\\end{bmatrix}\n\\\\&=\n\\begin{bmatrix}\n (pac+ad+bc)\\color{red}{\\cdot p+}qac+bd & (pac+ad+bc)\\color{red}{\\cdot q}\\\\\n pac+ad+bc & qac+bd\n\\end{bmatrix}\n\\\\&=(pac+ad+bc,qac+bd)\n\\end{aligned}\n$$\n\n事实上，在抽象代数领域，这是找到了一个特定类型矩阵的同构：\n\n$$\n\\phi(a,b)=\\begin{bmatrix}\n a\\color{red}{\\cdot p+}b & a\\color{red}{\\cdot q}\\\\\n a & b\n\\end{bmatrix}\n$$\n\n因此矩阵原有的代数性质对于二元组也是成立的，比如最重要的结合律，这是快速幂得以使用的基础。很容易得出使用这种二元组表示的通项公式：\n\n$$\n(a_{n+1},a_n)=(a_1,a_0)*(1,0)^n\n$$\n\n很容易观察到二元组乘法的单位元：\n\n$$\n(a,b)*(0,1)=(0,1)*(a,b)=(a,b)\n$$\n\n而且不难找到 $(1,0)$ 的逆元：\n\n$$\n(1,0)*\\left(q^{-1},-pq^{-1}\\right)=(0,1)\n$$\n\n这样我们就可以方便的实现倒推了。\n\n理论上讲由于这个方法相比矩阵会少算两三次乘法或加法，因此常数会小一点，实际上没什么差距。下面是针对斐波那契数列的代码：\n\n```cpp\nstruct phi_tuple : pair {\n using pair::pair;\n phi_tuple &operator*=(const phi_tuple &other) {\n // 这里计算的时候提取了公因式以减少一次乘法\n return *this = {first * (other.first + other.second) +\n second * other.first,\n first * other.first + second * other.second};\n }\n} e{0, 1};\n\nphi_tuple qpow(phi_tuple x, int n) {\n auto res{e};\n while (n) {\n if (n & 1)\n res *= x;\n x *= x, n >>= 1;\n }\n return res;\n}\n\nint fib(int n) {\n return qpow(phi_tuple{1, 0}, n + 1).first;\n}\n```\n\n## 特征根法求通项公式的线性代数理解\n\n对于二阶线性递推，一种广为人知的求通项公式的方法是特征根法。对于二阶线性递推：\n\n$$\na_{n} = pa_{n - 1} + qa_{n - 2}\n$$\n\n有特征方程：\n\n$$\n\\varphi^2=p\\varphi+q\n$$\n\n可以解出该方程的两个复根：\n\n$$\n\\varphi_1=\\phi,\\varphi_2=\\psi\n$$\n\n当 $\\phi\\neq\\psi$ 时（即 $\\Delta\\neq0$），有：\n\n$$\na_n=s\\phi^n+t\\psi^n\n$$\n\n当 $\\phi=\\psi$ 时（即 $\\Delta=0$），有：\n\n$$\na_n=(s+tn)\\varphi^n\n$$\n\n接下来只需要将 $a_0,a_1$ 代入求出 $s,t$ 即可。\n\n------\n\n下面我们以斐波那契数列为例。斐波那契数列的特征方程为：\n\n$$\n\\varphi^2=\\varphi+1\n$$\n\n解得：\n\n$$\n\\phi=\\dfrac{1-\\sqrt{5}}{2},\\psi=\\dfrac{1+\\sqrt{5}}{2}\n$$\n\n于是：\n\n$$\nf_n=s\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^n+t\\left(\\dfrac{1+\\sqrt{5}}{2}\\right)^n\n$$\n\n将 $f_0=1,f_1=1$ 代入，会得到一坨很复杂的东西，于是方便起见取 $f_0=0,f_1=1$：\n\n$$\ns=-\\dfrac{1}{\\sqrt{5}},t=\\dfrac{1}{\\sqrt{5}}\n$$\n\n这样我们就可以得到取 $f_0=0,f_1=1$ 时的斐波那契通项公式了：\n\n$$\nf_n=\\dfrac{1}{\\sqrt{5}}\\left[\\left(\\dfrac{1+\\sqrt{5}}{2}\\right)^n-\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^n\\right]\n$$\n\n程序实现请继续往后看……\n\n### 相似对角化和矩阵特征值与特征向量\n\n> 方便起见，如无特殊说明，本节内容均以 $2\\times 2$ 矩阵为例\n\n上面的方法有多种证明，在这里我们从线性代数的角度考虑。一种很自然的想法是想办法展开矩阵表示的通项公式：\n\n$$\n\\begin{bmatrix}\n a_{n} & a_{n-1}\n\\end{bmatrix}\n=\n\\begin{bmatrix}\n a_0 & a_1\n\\end{bmatrix}\n\\begin{bmatrix}\n p & 1\\\\\n q & 0\n\\end{bmatrix}^n\n$$\n\n显然问题的关键在于展开右侧的方阵幂。乍一看会有点没思路，不妨从更简单的对角矩阵考虑。对角矩阵指的是形如下面的方阵：\n\n$$\n\\boldsymbol{\\Lambda}=\\begin{bmatrix}\n m & \\\\\n & n\n\\end{bmatrix}\n$$\n\n其中空白的区域表示省略的 $0$。观察对焦方阵的平方以及立方：\n\n$$\n\\begin{bmatrix}\n m & \\\\\n & n\n\\end{bmatrix}^2=\n\\begin{bmatrix}\n m^2 & \\\\\n & n^2\n\\end{bmatrix}\n\\\\\\begin{bmatrix}\n m & \\\\\n & n\n\\end{bmatrix}^3=\n\\begin{bmatrix}\n m^3 & \\\\\n & n^3\n\\end{bmatrix}\n$$\n\n猜测对角矩阵的幂满足：\n\n$$\n\\begin{bmatrix}\n m & \\\\\n & n\n\\end{bmatrix}^k=\n\\begin{bmatrix}\n m^k & \\\\\n & n^k\n\\end{bmatrix},k\\in\\mathbb{N}\n$$\n\n很容易通过数学归纳法证明。于是我们找到了计算对角矩阵的幂次的方法，接下来考虑推广到一般的方阵。最直接的想法是将方阵转化为对角矩阵。考虑下面的式子：\n\n$$\n\\boldsymbol{A}=\\boldsymbol{P}\\boldsymbol{\\Lambda}\\boldsymbol{P}^{-1}\n$$\n\n注意到：\n\n$$\n\\boldsymbol{A}^n=\\left(\\boldsymbol{P}\\boldsymbol{\\Lambda}\\boldsymbol{P}^{-1}\\right)\\left(\\boldsymbol{P}\\boldsymbol{\\Lambda}\\boldsymbol{P}^{-1}\\right)\\cdots\\left(\\boldsymbol{P}\\boldsymbol{\\Lambda}\\boldsymbol{P}^{-1}\\right)\n$$\n\n其中 $\\boldsymbol{P}$ 和 $\\boldsymbol{P}^{-1}$ 成对出现，于是：\n\n$$\n\\boldsymbol{A}^n=\\boldsymbol{P}\\boldsymbol{\\Lambda}^n\\boldsymbol{P}^{-1}\n$$\n\n接下来只需找到 $\\boldsymbol{A}$ 对应的 $\\boldsymbol{P}$ 和 $\\boldsymbol{\\Lambda}$ 即可，这个过程被称为矩阵的相似对角化。\n\n在寻找相似对角化的方法之前，我们先补充一些知识。你也许已经知道线性方程组可以用矩阵乘法等价表示：\n\n$$\n\\left\\{\n \\begin{matrix}\n a_{11}x_1+a_{12}x_2=b_1\\\\\n a_{21}x_1+a_{22}x_2=b_2\n \\end{matrix}\n\\right.\n\\iff\n\\begin{bmatrix}\n a_{11} & a_{12}\\\\\n a_{21} & a_{22}\n\\end{bmatrix}\n\\begin{bmatrix}\n b_1\\\\\n b_2\n\\end{bmatrix}\n=\n\\begin{bmatrix}\n b_1\\\\\n b_2\n\\end{bmatrix}\n$$\n\n基于此，线性方程组均可视为 $\\boldsymbol{Ax}=\\boldsymbol{b}$ 的形式。当 $\\boldsymbol{b}=\\boldsymbol{0}$ 时，称其为齐次线性方程组，每个方阵都唯一对应一个齐次线性方程组。\n\n另外，你还可能听说过行列式：\n\n$$\n\\begin{vmatrix}\n a & b\\\\\n c & d\n\\end{vmatrix}\n=ad-bc\n$$\n\n方阵 $\\boldsymbol{A}$ 的行列式可以显示方阵的一些性质，比如方阵对应的齐次方程组的解的情况和是否可逆：\n\n1. $|\\boldsymbol{A}| = 0$ 时，方阵不可逆，有无穷多解，且任意解之间都线性相关，也就是说每个解都可以通过数乘另一个解得到\n2. $|\\boldsymbol{A}| \\neq 0$ 时，方阵可逆，只有零解\n\n因篇幅有限，在此不做证明。\n\n相似对角化需要利用矩阵的特征值 $\\lambda$ 和特征向量 $\\boldsymbol{x}$，其满足：\n\n$$\n\\boldsymbol{A}x=\\lambda \\boldsymbol{x},\\boldsymbol{x}\\neq\\boldsymbol{0}\n$$\n\n等号右侧可以乘上单位矩阵 $\\boldsymbol{E}$ 来变形：\n\n$$\n\\left(\\boldsymbol{A}-\\lambda\\boldsymbol{E}\\right)\\boldsymbol{x}=\\boldsymbol{0}\n$$\n\n由于 $\\boldsymbol{x}\\neq\\boldsymbol{0}$ 故\n\n$$\n|\\boldsymbol{A}-\\lambda\\boldsymbol{E}|=0\n$$\n\n这其实就是一个关于 $\\lambda$ 的多项式方程，实际上等号左边被称为矩阵的特征多项式。由于本文以二阶方阵为例，因此特征多项式是一元二次的，那么就有两个根 $\\lambda_1,\\lambda_2$，这两个根都是矩阵的特征值。将 $\\lambda$ 回代即可得求出特征向量 $\\boldsymbol{x}$，每个 $\\lambda_i$ 均对应无穷多组解 $k\\boldsymbol{x_i},k\\in\\mathbb{R}$。\n\n回到相似对角化，可以证明，如果一个矩阵是可以相似对角化的，那么必然有下面的相似对角化方案：\n\n$$\n\\boldsymbol{\\Lambda}=\\begin{bmatrix}\n \\lambda_1 & \\\\\n & \\lambda_2\n\\end{bmatrix},\n\\boldsymbol{P}=\\begin{bmatrix}\n \\boldsymbol{x}_1 & \\boldsymbol{x}_2\n\\end{bmatrix}\n$$\n\n其中 $\\boldsymbol{x}_i$ 是任意一个特征值 $\\lambda_i$ 对应的非零特征向量。其中 $\\boldsymbol{P}$ 被称为特征矩阵。当且仅当 $\\lambda_i$ 两两不同时，矩阵 $\\boldsymbol{P}$ 可逆，读者自证不难。解线性方程组和求逆矩阵都可以通过高斯消元法，限于篇幅，这里就不展开了。\n\n-----\n\n接下来仍然以斐波那契数列为例。以 $f_0=1$ 为首项。有矩阵通项公式（其中 $\\odot$ 表示不重要的元素，下同）：\n\n$$\n\\begin{bmatrix}\n f_n & f_{n-1}\\\\\n \\odot & \\odot\n\\end{bmatrix}\n=\n\\begin{bmatrix}\n 1 & 1\\\\\n 1 & 0\n\\end{bmatrix}^n\n$$\n\n转移矩阵的特征多项式、特征值和特征向量：\n\n$$\n\\lambda^2-\\lambda-1\n$$\n\n$$\n\\lambda_1=\\dfrac{1+\\sqrt{5}}{2},\\lambda_2=\\dfrac{1-\\sqrt{5}}{2}\n$$\n\n$$\n\\boldsymbol{x}_1=\\begin{bmatrix}1\\\\-\\dfrac{1-\\sqrt{5}}{2}\\end{bmatrix},\n\\boldsymbol{x}_2=\\begin{bmatrix}1\\\\-\\dfrac{1+\\sqrt{5}}{2}\\end{bmatrix}\n$$\n\n相似对角矩阵和特征矩阵：\n\n$$\n\\boldsymbol{\\Lambda}=\\begin{bmatrix}\n \\dfrac{1 + \\sqrt{5}}{2}&\\\\\n &\\dfrac{1 - \\sqrt{5}}{2}\n\\end{bmatrix}\n$$\n\n$$\n\\boldsymbol{P}=\\begin{bmatrix}\n 1&1\\\\\n -\\dfrac{1 - \\sqrt{5}}{2}&-\\dfrac{1 + \\sqrt{5}}{2}\n\\end{bmatrix}\n$$\n\n特征矩阵的逆：\n\n$$\n\\boldsymbol{P}^{-1}=\\dfrac{1}{\\sqrt{5}}\\begin{bmatrix}\n \\dfrac{1 + \\sqrt{5}}{2}&1\\\\\n -\\dfrac{1 - \\sqrt{5}}{2}&-1\n\\end{bmatrix}\n$$\n\n相似对角化求幂次：\n\n$$\n\\begin{aligned}\n\\begin{bmatrix}\n 1 & 1\\\\\n 1 & 0\n\\end{bmatrix}^n\n&=\\dfrac{1}{\\sqrt{5}}\n\\begin{bmatrix}\n 1&1\\\\\n -\\dfrac{1 - \\sqrt{5}}{2}&-\\dfrac{1 + \\sqrt{5}}{2}\n\\end{bmatrix}\n\\begin{bmatrix}\n \\dfrac{1 + \\sqrt{5}}{2}&\\\\\n &\\dfrac{1 - \\sqrt{5}}{2}\n\\end{bmatrix}^n\n\\begin{bmatrix}\n \\dfrac{1 + \\sqrt{5}}{2}&1\\\\\n -\\dfrac{1 - \\sqrt{5}}{2}&-1\n\\end{bmatrix}\\\\\n&=\n\\begin{bmatrix}\n \\dfrac{1}{\\sqrt{5}}\\left[\\left(\\dfrac{1+\\sqrt{5}}{2}\\right)^{n+1}-\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^{n+1}\\right]&\\odot\\\\\n \\odot&\\odot\n\\end{bmatrix}\n\\end{aligned}\n$$\n\n于是我们就得到了通项公式：\n\n$$\nf_n=\\dfrac{1}{\\sqrt{5}}\\left[\\left(\\dfrac{1+\\sqrt{5}}{2}\\right)^{n+1}-\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^{n+1}\\right]\n$$\n\n----\n\n接下来就是写代码了。方便起见，后文就以 $f_0=0$ 作为首项……（说实话我也不知道我为啥要在这里绕来绕去，但是懒得改了）我们有通项公式：\n\n$$\nf_n=\\dfrac{1}{\\sqrt{5}}\\left[\\left(\\dfrac{1+\\sqrt{5}}{2}\\right)^{n}-\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^{n}\\right]\n$$\n\n如果只是要某一项的值的话，那直接在浮点数环境下计算就可以了。事实上，我们可以发现一个常数对半砍的公式：\n\n$$\nf_n=\\operatorname{round}\\left[\\dfrac{1}{\\sqrt{5}}\\left(\\dfrac{1+\\sqrt{5}}{2}\\right)^{n}\\right]\n$$\n\n其中 $\\mathrm{round}(x)$ 表示四舍五入到整数。这是由于 $\\left|\\tfrac{1}{\\sqrt{5}}\\left(\\tfrac{1-\\sqrt{5}}{2}\\right)^{n}\\right|<\\tfrac{1}{2}$，因此四舍五入可以忽略这部分影响。更加激进的，根据工程经验（其实是懒得误差分析），由于 $\\tfrac{1}{\\sqrt{5}}\\approx 0.447,\\tfrac{1-\\sqrt{5}}{2}\\approx 1.618$，下面的公式可以完美作为通项公式：\n\n$$\nf_n=\\operatorname{round}\\left(0.447\\cdot1.618^n\\right)\n$$\n\n代码也很好实现，适用于[不需要取模的情况](https://www.luogu.com.cn/problem/P1720)：\n\n```cpp\nfloat qpow(float x, int n) {\n float r = 1;\n while (n) {\n if (n & 1)\n r *= x;\n x *= x, n >>= 1;\n }\n return r;\n}\n\nint fib(int n) {\n return round(0.447 * qpow(1.618, n));\n}\n```\n\n但是如果你的需求是斐波那契数列取模，因为涉及到 $\\sqrt5$，那就比较复杂了。第一想法是二次剩余，但是 $5$ 在很多常见模数下没有二次剩余（如果你不知道什么是二次剩余，可以简单的理解为模意义下的平方根，这是数论的内容）。如果你了解过抽象代数或者代数数论，你肯能会想到一个东西——二次整数环。\n\n### 二次整数环\n\n二次整数环就是所有由整数加上一个特殊无理数后，通过加减乘得到的数所组成的集合。这些数不仅保留了整数环的性质，还可以在更广的范围内进行带余除法等操作。如果你学过复数，那就像复数是由实数和虚数部分组成一样，二次整数环是由整数和一个特定的无理数（如 $\\sqrt5$）的整数倍组合而成的数，这通常表示为 $\\mathbb{Z}[\\sqrt{d}]$。二次整数环 $\\mathbb{Z}[\\sqrt{d}]$ 上的运算和二次根式运算是一致的：\n\n1. 加减法：$(a_1+a_2\\sqrt{d})+(b_1+b_2\\sqrt{d}) = (a_1+b_1)+(a_2+b_2)\\sqrt{d}$\n2. 乘法：$(a_1+a_2\\sqrt{d})(b_1+b_2\\sqrt{d})=(a_1b_1+a_2b_2d)+(a_1b_2+a_2b_1)\\sqrt{d}$\n\n由于除法较为复杂而且我们现在用不到，就不做讨论了。在模意义下，每次计算完分别对整数部分和根式部分的系数取模即可，这实际上构成了二次整数环的剩余类环，一般记作 $\\mathbb{Z}[\\sqrt{d}]/\\{p\\}$，$p$ 是模数。在模意义下二次整数除以一个纯整数依旧是转化为乘上该整数的数论倒数（逆元）。除以二次整数的情况过于复杂且暂时本文用不到，就不做讨论了。\n\n接下来就是愉快的代码实现环节：\n\n```cpp\nusing i64 = int64_t;\n\nconstexpr i64 m = 1e9 + 7;\n\ntemplate constexpr num qpow(num a, i64 n) {\n num r = 1;\n while (n) {\n if (n & 1)\n r *= a;\n a *= a, n >>= 1;\n }\n return r;\n}\n\nstruct m64 {\n i64 x;\n constexpr m64(const i64 x) : x(((x % m) + m) % m) {\n }\n constexpr operator i64() const {\n return x;\n }\n constexpr m64 operator-() const {\n return m64(-x);\n }\n constexpr m64 operator*(const m64 &o) const {\n return m64((x * o.x) % m);\n }\n constexpr m64 &operator*=(const m64 &o) {\n *this = *this * o;\n return *this;\n }\n constexpr m64 operator/(const m64 &o) const {\n return m64(*this * qpow(o, m - 2));\n }\n};\n\nstruct sr5m64 {\n m64 x, s;\n constexpr sr5m64(m64 x, m64 s) : x(x), s(s) {\n }\n constexpr sr5m64(i64 x) : x(x), s(0) {\n }\n constexpr sr5m64 operator-() const {\n return sr5m64(-x, -s);\n }\n constexpr sr5m64 operator+(const sr5m64 &o) const {\n return sr5m64(x + o.x, s + o.s);\n }\n constexpr sr5m64 operator-(const sr5m64 &o) const {\n return *this + (-o);\n }\n constexpr sr5m64 operator*(const sr5m64 &o) const {\n return sr5m64(x * o.x + 5 * s * o.s, x * o.s + s * o.x);\n }\n constexpr sr5m64 &operator*=(const sr5m64 &o) {\n *this = *this * o;\n return *this;\n }\n constexpr sr5m64 operator/(const m64 &o) const {\n return sr5m64(x / o, s / o);\n }\n};\n\nconstexpr m64 fib(i64 n) {\n return ((qpow(sr5m64(1, 1) / 2, n) - qpow(sr5m64(1, -1) / 2, n)) * sr5m64(0, 1) / 5).x;\n}\n```\n\n## 二阶线性递推的一些性质\n\n### 模意义下的周期性\n\n任何的二阶线性递推在模 $m$ 下都是具有周期性的。考虑矩阵表示中的状态模 $m$\n\n$$\n\\begin{bmatrix}\na_{n}\\bmod{m}&a_{n-1}\\bmod{m}\n\\end{bmatrix}\n$$\n\n显然状态的每一项最多只有 $m$ 种，因此所有可能的状态最多有 $m^2$ 种，所以在二阶线性递推充分多次后必然产生两个相同的状态，因此会呈现出周期性。这个结论也可以推广到任意阶线性递推。\n\n由于求解最小正周期需要用到二项式定理等内容，在此不做展开，详情参考[皮萨诺周期](https://oi-wiki.org/math/combinatorics/fibonacci/#%E7%9A%AE%E8%90%A8%E8%AF%BA%E5%91%A8%E6%9C%9F)。一道[广为流传的题目](https://www.luogu.com.cn/problem/P4000)可能需要这部分知识。\n\n### 斐波那契数列相邻两项之比趋于黄金分割比\n\n黄金分割比指的是\n\n$$\n\\phi=\\dfrac{\\sqrt{5}-1}{2}\n$$\n\n很显然其是斐波那契数列的一个特征根。本节小标题的意思是：\n\n$$\n\\lim_{n\\to \\infty}\\dfrac{f_n}{f_{n+1}}=\\phi\n$$\n\n直接代入通项公式暴力求极限即可：\n\n$$\n\\begin{aligned}\n\\lim_{n\\to \\infty}\\dfrac{f_n}{f_{n+1}}&=\\lim_{n\\to \\infty}\n\\dfrac{\\dfrac{1}{\\sqrt{5}}\\left[\\left(\\dfrac{1+\\sqrt{5}}{2}\\right)^{n}-\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^{n}\\right]}{\\dfrac{1}{\\sqrt{5}}\\left[\\left(\\dfrac{1+\\sqrt{5}}{2}\\right)^{n+1}-\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^{n+1}\\right]}\\\\\n&=\\lim_{n\\to \\infty}\n\\dfrac{\\dfrac{\\sqrt{5}-1}{2}+(-1)^n\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^{2n+1}}{1+(-1)^n\\left(\\dfrac{1-\\sqrt{5}}{2}\\right)^{2n+2}}\\\\\n&=\\dfrac{\\sqrt{5}-1}{2}=\\phi\n\\end{aligned}\n$$\n\n对于一部分二阶线性递推，也能得出相似的结论。\n\n## 结语\n\n累了，就先写到这里吧…","1739012466028",1739010002721,{"_12":204,"_33":210,"_35":211,"_37":212,"_39":213,"_41":214,"_43":44,"_45":215,"_47":46,"_48":46,"_49":24,"_50":51,"_26":216,"_28":217,"_53":245},{"_55":204,"_56":219,"_58":220,"_59":221},[247,251,256],{"_12":248,"_64":249,"_66":46,"_68":46,"_26":250,"_71":-5},"224861462605381632","linear-algebra",1631419150409,{"_12":252,"_64":253,"_66":46,"_68":254,"_26":255,"_71":-5},"223449464344641536","math","数学没有普遍接受的定义。亚里士多德将数学定义为“数量的科学”，这个定义一直流行到 18 世纪",1631082503790,{"_12":224,"_64":225,"_66":226,"_68":227,"_26":228,"_71":-5},{"_73":239,"_74":57,"_75":30,"_76":30,"_77":258},125,[],{"_89":261,"_262":263},"Njc2MTMwMjA0ODQzMTgwMDMy","prev","Njk1MzI5NjE0NzIzMzU0NjI0","cacheHit","actionData","errors"]

markdown很好用