矩阵快速幂

1. 什么是矩阵快速幂

矩阵快速幂是把「对一个方阵求大幂」的问题用二分法（指数快速幂 / 指数平方）加速计算的技巧。直接把矩阵乘 k 次需要 $O(k * m^3)$ （m 为矩阵维度，方阵常见为 2），而矩阵快速幂可以把复杂度降到 $O(log k * m^3)$ 。

这个技巧常用于线性递推（线性齐次递推）问题，例如斐波那契、K 项线性递推、一些动态规划转化为线性变换的场景。

2. 为什么用矩阵可以求斐波那契数列

斐波那契数列满足递推：

$F_n = F_{n-1} + F_{n-2}$

把状态向量设为 $[F_n, F_{n-1}]^T$ ，则可以写成矩阵形式：

$\begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}$

记转换矩阵为 M = [[1,1],[1,0]]，则反复递推：

$\begin{bmatrix}F_n\\F_{n-1}\end{bmatrix} = M^{n-1} \begin{bmatrix}F_1\\F_0\end{bmatrix}$

因此，只要计算矩阵 M 的 n-1 次幂，再乘以基向量，就能得到 $F_n$ 。

3. 指数快速幂（二分幂）思想

计算 $a^k$ （这里的 a 是矩阵）可以按二分法：

若 k 为偶数： $a^k = (a^{k/2}) * (a^{k/2})$
若 k 为奇数： $a^k = a * (a^{k-1})$

通过递归或迭代不断把 k 右移（除 2），可以在 $O(log k)$ 次乘法内算出幂。但注意这里的乘法是矩阵乘法，成本为 $O(m^3)$ （矩阵维度 m）。对于 2x2 矩阵，矩阵乘法是常数时间（8 次乘法，4 次加法），因此非常快。

4. 矩阵快速幂实现细节

实现要点：

定义矩阵乘法函数（适用于 2×2 或通用 m×m）。
定义单位矩阵（单位矩阵是乘法中不改变数值的矩阵）。
用迭代或递归实现快速幂，一般推荐迭代版（循环右移指数，遇到 1 就乘上当前基矩阵）。
注意数据类型溢出问题：如果 n 很大或不取模，结果会溢出 64 位整数。常见做法是对一个模 MOD 取模。

5. 示例代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;

struct Mat {
    ll a[2][2];
};

Mat mul(const Mat &x, const Mat &y) {
    Mat r;
    r.a[0][0] = ( (x.a[0][0]*y.a[0][0])%MOD + (x.a[0][1]*y.a[1][0])%MOD ) % MOD;
    r.a[0][1] = ( (x.a[0][0]*y.a[0][1])%MOD + (x.a[0][1]*y.a[1][1])%MOD ) % MOD;
    r.a[1][0] = ( (x.a[1][0]*y.a[0][0])%MOD + (x.a[1][1]*y.a[1][0])%MOD ) % MOD;
    r.a[1][1] = ( (x.a[1][0]*y.a[0][1])%MOD + (x.a[1][1]*y.a[1][1])%MOD ) % MOD;
    return r;
}

Mat mat_pow(Mat base, long long exp) {
    Mat res;
    res.a[0][0] = 1; res.a[0][1] = 0;
    res.a[1][0] = 0; res.a[1][1] = 1;

    while (exp > 0) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

ll fibonacci_mod(long long n) {
    if (n == 0) return 0;
    Mat M;
    M.a[0][0] = 1; M.a[0][1] = 1;
    M.a[1][0] = 1; M.a[1][1] = 0;

    Mat R = mat_pow(M, n-1);
    return R.a[0][0] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    while (cin >> n) {
        cout << fibonacci_mod(n) << '\n';
    }
    return 0;
}