5 条题解

  • 0
    @ 2025-7-27 9:52:32

    矩阵幂指数为什么是 n−3n-3，本质上是因为我们把「从第 3 项走到第 nn 项」的过程，分解成 n−3n-3 次「一步推进」：

    1. 初始状态 我们把

      $$S_x = \begin{pmatrix} a_x\\ a_{x-1}\\ a_{x-2} \end{pmatrix} $$

      在 x=3x=3 时刻，已经完全知道：

      $$S_3 = \begin{pmatrix} a_3\\ a_2\\ a_1 \end{pmatrix} = \begin{pmatrix} 1\\1\\1 \end{pmatrix}. $$

    2. 一步推进对应一次矩阵乘法 对于任意 x≥4x\ge4，我们有

      Sx=M Sx−1.S_x = M\,S_{x-1}.

      这就是 “每前进一步” 用一次矩阵 MM 去乘上一次旧的状态。

    3. 多步推进就是矩阵幂

      • 要从 S3S_3 推到 S4S_4，用一次：

        S4=M S3=M1 S3. S_4 = M\,S_3 = M^1\,S_3.

      • 要从 S3S_3 推到 S5S_5，需要两次：

        S5=M S4=M (M S3)=M2 S3. S_5 = M\,S_4 = M\,(M\,S_3) = M^2\,S_3.

      • …

      • 要从 S3S_3 推到一般的 SnS_n，就要做 n−3n-3 次这样的“乘 MM”操作：

        $$ S_n = \underbrace{M\,(M\,(\cdots\,(M}_{\displaystyle n-3\text{ 次}}\,S_3)\cdots)) = M^{\,n-3}\,S_3. $$

    4. 为什么不是 MnM^n 或者其它

      • 从 S1S_1 到 S3S_3 本身并不需要矩阵推进，因题已给 a1=a2=a3=1a_1=a_2=a_3=1。
      • 我们只需要从已知的 S3S_3 “走”到 SnS_n，一共做 (3→4),(4→5),…,((n−1)→n)(3\to4),(4\to5),\dots,((n-1)\to n) 这 n−3n-3 步。

    因此，最终要算的就是

    Sn=M n−3 S3,S_n = M^{\,n-3}\,S_3,

    然后取其第一行（即向量的第一分量）作为 ana_n。这就是为什么快速幂里 exponent 要用 n−3n-3。

    • 0
      @ 2025-7-27 9:40:05

      我们之所以要引入

      $$S_x = \begin{pmatrix} a_x\\ a_{x-1}\\ a_{x-2} \end{pmatrix} $$

      这个“状态向量”，本质上是为了把「高阶递推」变成「一次矩阵乘法」。原因可以分两步理解：

      一、为什么要把多个项打包成一个向量？

      你的递推式是

      ax=ax−1+ax−3.a_x = a_{x-1} + a_{x-3}.

      这是一个 3 阶（“依赖前三项”）的线性递推。要想通过「矩阵快速幂」直接跳到第 nn 项，就需要把当前项及其足够的“历史”集中在一个对象里，这样才能一次性地用一个矩阵去“推进”一步。

      • 如果递推只依赖前 1 项（比如斐波那契那样 Fx=Fx−1+Fx−2F_x = F_{x-1}+F_{x-2}），我们只需把 (Fx, Fx−1)\bigl(F_x,\,F_{x-1}\bigr) 放在一个 2 维向量里。
      • 现在依赖的是前 1 项和前 3 项，为了把前 3 项（也就是 ax−1,ax−2,ax−3a_{x-1},a_{x-2},a_{x-3}）都带到下一个状态里，我们就把 ax,ax−1,ax−2a_x,a_{x-1},a_{x-2} 放到一个 3 维向量中（注意：向量的第 3 分量存的其实是上一轮的第 2 分量，也就是 ax−2a_{x-2}；这样下次再推进一步，它就变成了 a(x+1)−3=ax−2a_{(x+1)-3}=a_{x-2}）。

      这样，每次 Sx−1→SxS_{x-1}\to S_x 的转换，只要写成一次矩阵乘法就能搞定。

      二、向量分量意义与递推式的对应

      设

      $$S_{x-1} = \begin{pmatrix} a_{x-1}\\ a_{x-2}\\ a_{x-3} \end{pmatrix}, \quad S_x = \begin{pmatrix} a_x\\ a_{x-1}\\ a_{x-2} \end{pmatrix}. $$

      我们要找一个 3×33\times3 的矩阵 MM，使得

      Sx=M Sx−1.S_x = M\,S_{x-1}.

      展开来看，就是：

      $$\begin{cases} a_x &= m_{11}\,a_{x-1} + m_{12}\,a_{x-2} + m_{13}\,a_{x-3},\\ a_{x-1} &= m_{21}\,a_{x-1} + m_{22}\,a_{x-2} + m_{23}\,a_{x-3},\\ a_{x-2} &= m_{31}\,a_{x-1} + m_{32}\,a_{x-2} + m_{33}\,a_{x-3}. \end{cases} $$
      • 第一行 用来重现我们的原递推 ax=ax−1+ax−3a_x = a_{x-1} + a_{x-3}，因此 (m11,m12,m13)=(1,0,1)(m_{11},m_{12},m_{13})=(1,0,1)。
      • 第二行 要把 “旧的第一分量” ax−1a_{x-1} 直接搬到新的第二分量，就写成 $a_{x-1}=1\cdot a_{x-1}+0\cdot a_{x-2}+0\cdot a_{x-3}$，对应行 (1,0,0)(1,0,0)。
      • 第三行 要把 “旧的第二分量” ax−2a_{x-2} 直接搬到新的第三分量，就写成 $a_{x-2}=0\cdot a_{x-1}+1\cdot a_{x-2}+0\cdot a_{x-3}$，对应行 (0,1,0)(0,1,0)。

      这样就得到

      $$M = \begin{pmatrix} 1 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}, $$

      满足恰好把递推封装成一次 Sx=M Sx−1S_x = M\,S_{x-1}。最后，通过快速幂算出 Mn−3M^{n-3}，再乘以初始向量 S3=[a3,a2,a1]T=[1,1,1]TS_3=[a_3,a_2,a_1]^T=[1,1,1]^T，就能在 O(log⁡n)\mathcal O(\log n) 内得到任意 ana_n 了。

      • 0
        @ 2025-7-27 8:48:39

        自己的方法略微变形:

        #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;              // 取模常数 10^9+7

using mat = vector<vector<ll>>;         // 动态数组矩阵类型

// 矩阵乘法：计算 3×3 矩阵 a * b，返回结果矩阵
mat mul(const mat &a, const mat &b) {
    mat c(3, vector<ll>(3, 0));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            ll s = 0;
            for (int k = 0; k < 3; k++) {
                // 按定义累加 a[i][k] * b[k][j]，并取模
                s = (s + a[i][k] * b[k][j]) % mod;
            }
            c[i][j] = s;
        }
    }
    return c;
}

// 矩阵快速幂：计算 a^e（3×3 矩阵），二进制快速幂
mat mpow(mat a, ll e) {
    mat r(3, vector<ll>(3, 0));
    // 初始化 r 为单位矩阵 I3
    for (int i = 0; i < 3; i++) r[i][i] = 1;
    // 按二进制位依次处理
    while (e > 0) {
        if (e & 1) {
            // 当前最低位为 1，则将 a 累乘到结果 r 上
            r = mul(r, a);
        }
        // a 自身平方，处理下一位
        a = mul(a, a);
        e >>= 1;
    }
    return r;
}

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

    int T;
    cin >> T;  // 询问次数
    while (T--) {
        ll n;
        cin >> n;  // 读取每个查询的 n

        // 对于 n <= 3，直接返回 1
        if (n <= 3) {
            cout << 1 << "\n";
            continue;
        }

        // ----- 下面将 calc 函数的逻辑直接内联到主函数中 -----

        // 构造转移矩阵 M，使得
        // [a_x, a_{x-1}, a_{x-2}]^T = M * [a_{x-1}, a_{x-2}, a_{x-3}]^T
        // 可以直接用二维数组初始化，然后复制到 vector 矩阵中
        ll M_arr[3][3] = {
            {1, 0, 1},  // a_x     = a_{x-1} + a_{x-3}
            {1, 0, 0},  // a_{x-1} = a_{x-1}
            {0, 1, 0}   // a_{x-2} = a_{x-2}
        };
        mat M(3, vector<ll>(3));
        // 直接 memcpy 或者双重循环都可以，这里用双重循环复制
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                M[i][j] = M_arr[i][j];
            }
        }

        // 快速幂计算 M^(n-3)
        mat P = mpow(M, n - 3);

        // 初始状态向量 V = [a3, a2, a1] = [1, 1, 1]
        // 则 a_n = P[0] · V = P[0][0]*1 + P[0][1]*1 + P[0][2]*1
        ll ans = (P[0][0] + P[0][1] + P[0][2]) % mod;

        // 输出结果
        cout << ans << "\n";
    }

    return 0;
}
        • 0
          @ 2025-7-22 16:55:21

          自己的方法

          #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;              // 取模常数 10^9+7

using mat = vector<vector<ll>>;         // 动态数组矩阵类型

// 矩阵乘法：计算 3×3 矩阵 a * b，返回结果矩阵
mat mul(const mat &a, const mat &b) {
    mat c(3, vector<ll>(3, 0));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            ll s = 0;
            for (int k = 0; k < 3; k++) {
                // 按定义累加 a[i][k] * b[k][j]，并取模
                s = (s + a[i][k] * b[k][j]) % mod;
            }
            c[i][j] = s;
        }
    }
    return c;
}

// 矩阵快速幂：计算 a^e（3×3 矩阵），二进制快速幂
mat mpow(mat a, ll e) {
    mat r(3, vector<ll>(3, 0));
    // 初始化 r 为单位矩阵 I3
    for (int i = 0; i < 3; i++) r[i][i] = 1;
    // 按二进制位依次处理
    while (e > 0) {
        if (e & 1) {
            // 当前最低位为 1，则将 a 累乘到结果 r 上
            r = mul(r, a);
        }
        // a 自身平方，处理下一位
        a = mul(a, a);
        e >>= 1;
    }
    return r;
}

// 计算数列第 n 项 a[n]
// 数列定义：a[1]=a[2]=a[3]=1；a[x]=a[x-1]+a[x-3]（x>=4）
ll calc(ll n) {
    if (n <= 3) return 1;  // 前三项直接返回 1
    // 构造转移矩阵 M，使得
    // [a_x, a_{x-1}, a_{x-2}]^T = M * [a_{x-1}, a_{x-2}, a_{x-3}]^T
    mat M(3, vector<ll>(3, 0));
    M[0][0] = 1; M[0][1] = 0; M[0][2] = 1; // a_x = a_{x-1} + a_{x-3}
    M[1][0] = 1; M[1][1] = 0; M[1][2] = 0; // a_{x-1} = a_{x-1}
    M[2][0] = 0; M[2][1] = 1; M[2][2] = 0; // a_{x-2} = a_{x-2}
    // 快速幂计算 M^(n-3)
    mat P = mpow(M, n - 3);
    // 初始状态向量 V = [a3, a2, a1] = [1, 1, 1]
    // 则 a_n = P[0] · V = P[0][0]*1 + P[0][1]*1 + P[0][2]*1
    ll ans = (P[0][0] + P[0][1] + P[0][2]) % mod;
    return ans;
}

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

    int T;
    cin >> T;                   // 询问次数
    while (T--) {
        ll n;
        cin >> n;               // 读取每个查询的 n
        cout << calc(n) << "\n";// 输出 a[n] mod 10^9+7
    }
    return 0;
}
          • 0
            @ 2025-3-26 19:00:31

            洛谷题解1

            • 1

            # P1939 矩阵加速（数列）

            信息

            ID
            1134
            时间
            1000ms
            内存
            256MiB
            难度
            10
            标签
            递交数
            8
            已通过
            3
            上传者
            1. Language
            2. 兼容模式
            3. 主题
            3. Worker 0, 31ms
            4. Powered by Hydro v5.0.0-beta.11 Community