P3390 【模板】矩阵快速幂 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P3390，日期见页头。两边不一致时信原站。

题目背景

一个 m × n 的矩阵是一个由 m 行 n 列元素排列成的矩形阵列。本题中认为矩阵中的元素 aᵢⱼ 是整数。

两个大小分别为 m × n 和 n × p 的矩阵 A、B 相乘的结果为一个大小为 m × p 的矩阵 C，其中

C[i][j] = Σ(k = 1..n) A[i][k] · B[k][j]      (1 ≤ i ≤ m, 1 ≤ j ≤ p)

而如果 A 的列数与 B 的行数不相等，则无法进行乘法。

可以验证，矩阵乘法满足结合律，即 (A B) C = A (B C)。

一个大小为 n × n 的矩阵 A 可以与自身进行乘法，得到的仍是大小为 n × n 的矩阵，记作 A² = A × A。进一步地，还可以递归地定义任意高次方 Aᵏ = A × A^(k−1)。特殊地，定义 A⁰ 为单位矩阵 I（主对角线全是 1、其余全是 0）。

题目描述

给定 n × n 的矩阵 A，求 Aᵏ。

输入格式

第一行两个整数 n, k。接下来 n 行，每行 n 个整数，第 i 行的第 j 个数表示 A[i][j]。

输出格式

输出 Aᵏ。共 n 行，每行 n 个数，第 i 行第 j 个数表示 (Aᵏ)[i][j]，每个元素对 10⁹+7 取模。

数据范围

对于 100% 的数据，1 ≤ n ≤ 100，0 ≤ k ≤ 10¹²，|A[i][j]| ≤ 1000。

时限 1 秒，内存 256 MB（262144 KB）。

输入输出样例

输入

2 1
1 1
1 1

输出

1 1
1 1

样例一：A 是全 1 的 2×2 矩阵，k = 1 ⇒ 原样输出。

输入

输出

121824 149688 177552
275886 338985 402084
429948 528282 626616

样例二：3×3、k = 5。⚠ 这一组不是上一组的重复 —— 见第 5 步。

1第 ① 版：老老实实乘 k 次

p3390Brute.cpp第 ① 版：连乘 k 次 —— 参照物，而且它一分都拿不到

// 第 ① 版：老老实实乘 k 次 —— 参照物，而且它**一分都拿不到**
//
// 这道题没有分档（题面只有一句「对于 100% 的数据」），而 k 可以到 10¹²：
// 每次矩阵乘 O(n³) = 10⁶ ⇒ 连乘 10¹² 次是 10¹⁸ 次乘法。
// ⇒ 它的身份只有一个：**小 k 时的参照物**。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static const ll MOD = 1000000007LL;
static int n;
struct Mat { ll a[100][100]; Mat() { memset(a, 0, sizeof a); } };

static Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) {
            ll t = A.a[i][k];
            if (!t) continue;
            for (int j = 0; j < n; j++) C.a[i][j] = (C.a[i][j] + t * B.a[k][j]) % MOD;
        }
    return C;
}

int main() {
    ll k;
    if (scanf("%d %lld", &n, &k) != 2) return 0;
    Mat A;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) { ll x; if (scanf("%lld", &x) != 1) return 0; A.a[i][j] = ((x % MOD) + MOD) % MOD; }
    Mat res;
    for (int i = 0; i < n; i++) res.a[i][i] = 1;
    for (ll t = 0; t < k; t++) res = mul(res, A);       // 老老实实乘 k 次
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) printf("%lld%c", res.a[i][j], j + 1 == n ? '\n' : ' ');
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

这道题没有分档（题面只有一句「对于 100% 的数据」），而 k 可以到 10¹²：一次矩阵乘就是 O(n³) = 10⁶，连乘 10¹² 次是 10¹⁸ 次乘法。⇒ 0 分。

2★★★ 关键一步：快速幂要的只是结合律

★★★ 把第 42 章那五行原样搬过来 —— 一个字都不用改

第 42 章第 6 步那条拆分：

a^b = (a^(b/2))²          （b 是偶数）
a^b = a · (a^(b−1))       （b 是奇数）

⇒ 它凭什么成立？只凭结合律 (A·B)·C = A·(B·C) —— 「先乘哪一对」不影响结果，所以才能把 b 个 a 任意分组。 ⚠ 交换律一次都没用到。

⇒ 于是把三样东西换掉，那五行就能跑：

快速幂里的	换成
数的乘法 `a * b`	矩阵乘 `mul(A, B)`，`O(n³)`
初值 `1`	★ 单位矩阵（题面自己定义了 `A⁰ = I`）
`res * a % p`	矩阵乘完每个元素取模

★ 题面自己把前提写出来了：「可以验证，矩阵乘法满足结合律」—— ⇒ 读题时看到这句话，就该想到「这道题是给快速幂准备的」。

复杂度 O(n³ log k)：顶格 100³ × 40 × 2 ≈ 8×10⁷ ⇒ 独占实测 41 毫秒 / 时限 1 秒 （一共只做 53 次矩阵乘，而连乘要做 10¹² 次 —— 差 189 亿倍）。

p3390.cpp★ 正解：矩阵快速幂 —— 顶格 41 毫秒

// P3390【模板】矩阵快速幂 —— 正解：快速幂那五行**一个字不改**
//
// ★★★ 这道题是整章的题眼：快速幂到底要什么？
//   它只用到一件事 —— **结合律**：(A·B)·C = A·(B·C)。
//   有了结合律，「a^b = (a^(b/2))²」这条拆分就成立，而**交换律一次都没用到**。
//   ⇒ 把「乘」换成矩阵乘、把「1」换成单位矩阵，那五行原样能跑。
//
// ⚠ 三笔必须自己算的账（见页面第 3、4 步）：
//   ① 内层累加：n 项、每项 < (10⁹)² = 10¹⁸ ⇒ n ≥ 10 就会撑破 long long
//      （9.22×10¹⁸ / (10⁹)² ≈ 9.2）⇒ **每加一项就取一次模**；
//   ② |A_ij| ≤ 1000 ⇒ **输入可以是负数**，读进来先 ((x % M) + M) % M；
//   ③ k 可以是 0 ⇒ res 的初值必须是**单位矩阵**。
//
// 复杂度 O(n³ log k)：100³ × 40 × 2 ≈ 8×10⁷。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static const ll MOD = 1000000007LL;
static int n;

struct Mat {
    ll a[100][100];
    Mat() { memset(a, 0, sizeof a); }
};

static Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) {
            if (!A.a[i][k]) continue;              // 顺手跳过 0，常数小一半
            ll t = A.a[i][k];
            for (int j = 0; j < n; j++)
                C.a[i][j] = (C.a[i][j] + t * B.a[k][j]) % MOD;   // ★ 每加一项就取模
        }
    return C;
}

int main() {
    ll k;
    if (scanf("%d %lld", &n, &k) != 2) return 0;
    Mat A;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            ll x;
            if (scanf("%lld", &x) != 1) return 0;
            A.a[i][j] = ((x % MOD) + MOD) % MOD;    // ★ 输入可能是负数
        }
    Mat res;
    for (int i = 0; i < n; i++) res.a[i][i] = 1;    // ★ k = 0 时答案就是它
    while (k) {
        if (k & 1) res = mul(res, A);
        A = mul(A, A);
        k >>= 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) printf("%lld%c", res.a[i][j], j + 1 == n ? '\n' : ' ');
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

3⚠ 「res = A · res」看着很危险 —— 而它一次都不会错

p3390Order.cpp⚠ 不是 bug：把乘的顺序反过来

★★★ 矩阵乘法不满足交换律，可这一行照样是对的 —— 而理由和自检都只要一句

量的是（300 组随机矩阵）	实测
`A² · A³ == A³ · A²` 的组数	★ 300 / 300
`A · B == B · A` 的组数（`A`、`B` 是两个不同的随机矩阵）	★ 0 / 300

第一行就是理由：快速幂里的 res 和 base 从头到尾都是同一个矩阵的幂，而 Aⁱ · Aʲ = A^(i+j) = Aʲ · Aⁱ —— 同一个矩阵的两个幂互相可交换。 第二行就是自检：换成两个不同的矩阵，当场分家。

⇒ 六个档 1800 轮，这一版被抓 0 次。 ⇒ 又一次「看着像 bug，其实一次都不会错」 —— ⚠ 而这一次值钱的是它把「结合律」和「交换律」的分工说清楚了： 快速幂靠结合律成立，而这一行的安全靠的是另一件事。

4★★★ 三笔必须自己算的账 —— 而顺手写的生成器把三个坑全盖住了

p3390NoMod.cpp✗ 错法一：内层加完 n 项才取一次模

p3390Neg.cpp✗ 错法二：忘了输入可以是负数

p3390Zero.cpp✗ 错法三：res 初值写成 A（k = 0 时就错）

★ 第一笔：内层能安全加几项，是一句除法

每一项 A[i][k] · B[k][j] 最大是 (10⁹+6)² ≈ 10¹⁸，而 long long 上限是 2⁶³−1 = 9.22×10¹⁸：

(2⁶³−1) / (10⁹+6)² = 9

⇒ 最多安全加 9 项 ⇒ n ≥ 10 起就可能溢出，而题面 n ≤ 100。 ⇒ 正解写的是 每加一项就取一次模（代价是每次多一个 %，而它换来的是不用做这道算术）。

★★★ 而这条线是两层的 —— 第一层在两个档上都是 300，一点区分度都没有

档位（每档 300 轮）	第一层：`n ≥ 10`	★ 第二层：那一行的和真的越过 2⁶³	✗ 「加完才取模」被抓
0 顺手写的（`n ≤ 4`、非负）	0	0	★ 精确的 0
3 `n ∈ [10, 16]`	300	★ 37	★ 37
5 `n ∈ [90, 100]`（顶格附近）	300	★ 300	★ 300

★★ 第一层（n ≥ 10）在档 3 和档 5 上都是 300 —— 它只是必要条件，真正决定抓不抓得到的是第二层：那一行的 n 项加起来有没有越过 2⁶³。 ⇒ 「第一层写得越显然，越要提防它没有区分度」的又一次（n ∈ [10,16] 时一行只有十几项，平均和约 3×10¹⁸，离 9.22×10¹⁸ 还差一截； n 到 90 以上就必爆）。

★ 而第二层和抓获数一个不差（0 ≡ 0、37 ≡ 37、300 ≡ 300）。

★★ 另外两笔账，各被一个「最自然的默认值」盖住

档位（每档 300 轮）	✗ 忘了负数取模	✗ 初值不是单位矩阵
0 顺手写的（元素非负、`k ≥ 1`）	★ 精确的 0	★ 精确的 0
1 元素照题面取 `[−1000, 1000]`	228（含负数的轮数 262）	0
4 `k = 0`	0	★ 300 / 300

负数：题面写的是 |A[i][j]| ≤ 1000 —— 那个绝对值号就是在说「会有负数」。而「顺手 rng() % 1001」造出来的全是非负数 ⇒ 这个坑一次都露不出来。（第 42 章第 5 步 ② 那条老账：C++ 的 % 跟着被除数走。）
k = 0：题面写的是 0 ≤ k，而顺手写的生成器 k 一般从 1 起。 ⇒ 「至多 K 个」在 K = 0 那几轮是精确的 0 的同一个形状。

⇒ ★★ 这道题三个坑，全都写在数据范围那一行里（0 ≤ k、|A| ≤ 1000、n ≤ 100），而顺手写的生成器把三个同时盖住 —— 这是本书见过最集中的一次。

⚠⚠ 顺带一个看起来很像 bug、其实是这一档自己的性质的现象：档 4（k = 0）里「输入含负数」有 252 轮、「矩阵不对称」有 220 轮，可「忘了负数取模」和「转置」两个错法在那一档都是精确的 0 —— 因为 k = 0 时答案恒是单位矩阵，A 一次都没被乘过。 ⇒ 「一致有两种：都算对了，和都没算」的又一次，而这一次「没算」的不是答案，是输入本身没被用到。

5⚠⚠ 官方给了两组样例 —— 而它们不是同一件事的重复

p3390Trans.cpp✗ 错法四：矩阵乘法的下标写成 A[k][i]（算成了转置）

★★★ 样例一放过它，样例二一测就死 —— 而原因一句话说得清

	样例一 `[[1,1],[1,1]]`、`k=1`	样例二 `[[1,2,3],[4,5,6],[7,8,9]]`、`k=5`
正解	`1 1 / 1 1`	`121824 …`
✗ 下标写成 `A[k][i]`	★ 一个字不差	★ 第一个数就错（286956）

为什么：写成 A[k][i] 之后算的是 Aᵀ · B —— 而样例一那个矩阵是对称的（Aᵀ = A）⇒ 它和正解做的是同一件事。

⇒ 「官方给了几组就跑几组，它们不是同一件事的重复」 —— ⚠ 而这一次两组样例的分工特别干净：一组对称、一组不对称。

★ 对拍那边也印证了同一件事：专造对称矩阵那一档，这个错法是 ★ 精确的 0 （而随机档被抓 195 / 300，n ≥ 10 那两档 300 / 300）。 ⇒ 那一档同时是这个 0 的自检。

p3390Gen.cpp生成器（六档：顺手 / 含负数 / 对称 / n≥10 / k=0 / n≈100）

6★ 哪一版就已经能过了

p3390Count.cpp本页所有数字的出处

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

// P3390 的度量程序：./p3390Count csv        （本页的数字都出自它）
//
//   line  : ★★★ 「内层加完才取模」那条线是一句除法：(2⁶³−1) / (10⁹+6)² —— 算出来 n 能到几。
//   two   : ★★ 而它是**两层的**：第一层「n ≥ 10」在档 3 / 5 上都是 300（没有区分度），
//           第二层「那一行的和真的越过 2⁶³」才是抓获数（档 3 只有 37，档 5 是 300）。
//   comm  : ★★★ 「res = A·res 也对」不是运气：**同一个矩阵的两个幂互相可交换**。
//           这里给它配一条自检 —— 换成两个**不同**的矩阵，A·B ≠ B·A 的组数。
//   ms    : 顶格 n = 100、k = 10¹² 的秒表，以及「连乘 k 次」要多少次乘法。
//
// ⚠ 这里**复刻**了 p3390Gen.cpp 的档位逻辑（同一个 mt19937、同一个种子公式）。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
typedef long long ll;
typedef __int128 lll;

static const ll MOD = 1000000007LL;
static const ll LL_TOP = 9223372036854775807LL;

struct Mat { vector<vector<ll>> a; Mat(int m = 0) : a(m, vector<ll>(m, 0)) {} };

static Mat mul(const Mat& A, const Mat& B, int m) {
    Mat C(m);
    for (int i = 0; i < m; i++)
        for (int k = 0; k < m; k++) {
            ll t = A.a[i][k];
            if (!t) continue;
            for (int j = 0; j < m; j++) C.a[i][j] = (C.a[i][j] + t * B.a[k][j]) % MOD;
        }
    return C;
}
/** 复刻「加完才取模」那一版，但用 __int128 记账：这一次乘法有没有让部分和越过 2⁶³ */
static bool mulOverflows(const Mat& A, const Mat& B, int m) {
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++) {
            lll s = 0;
            for (int k = 0; k < m; k++) {
                s += (lll)A.a[i][k] * B.a[k][j];
                if (s > (lll)LL_TOP) return true;
            }
        }
    return false;
}

/** 复刻 p3390Gen.cpp */
static void gen(unsigned seed, int mode, Mat& A, int& m, ll& k) {
    mt19937 rng(seed * 1000003u + 20260902u);
    int lo, hi; bool sym = false;
    if (mode == 0)      { m = 1 + (int)(rng() % 4u); k = 1 + (ll)(rng() % 8u); lo = 0; hi = 1000; }
    else if (mode == 1) { m = 1 + (int)(rng() % 4u); k = 1 + (ll)(rng() % 8u); lo = -1000; hi = 1000; }
    else if (mode == 2) { m = 2 + (int)(rng() % 3u); k = 1 + (ll)(rng() % 8u); lo = -1000; hi = 1000; sym = true; }
    else if (mode == 3) { m = 10 + (int)(rng() % 7u); k = 4 + (ll)(rng() % 5u); lo = -1000; hi = 1000; }
    else if (mode == 4) { m = 1 + (int)(rng() % 4u); k = 0; lo = -1000; hi = 1000; }
    else                { m = 90 + (int)(rng() % 11u); k = 4 + (ll)(rng() % 5u); lo = -1000; hi = 1000; }
    vector<vector<ll>> raw(m, vector<ll>(m));
    for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) { ll v = lo + (ll)(rng() % (unsigned)(hi - lo + 1)); raw[i][j] = v; }
    if (sym) for (int i = 0; i < m; i++) for (int j = 0; j < i; j++) raw[i][j] = raw[j][i];
    A = Mat(m);
    for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) A.a[i][j] = ((raw[i][j] % MOD) + MOD) % MOD;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    /* ① 那条线：一句除法 */
    ll maxEntry = MOD - 1;
    ll lineN = LL_TOP / (maxEntry * maxEntry);      // 最多能安全累加几项

    /* ② 六个档：n ≥ 10 的轮数（第一层）／ 真的加爆的轮数（第二层）／ 输入含负数的轮数 */
    int bigN[6] = {0}, realOv[6] = {0}, hasNeg[6] = {0}, kZero[6] = {0}, asym[6] = {0};
    for (int mode = 0; mode < 6; mode++)
        for (int s = 1; s <= 300; s++) {
            Mat A; int m; ll k;
            gen((unsigned)s, mode, A, m, k);
            if (m >= 10) bigN[mode]++;
            if (k == 0) kZero[mode]++;
            bool ne = false, as = false;
            for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) {
                if (A.a[i][j] > MOD / 2) ne = true;             // 归正之后的负数长这样
                if (A.a[i][j] != A.a[j][i]) as = true;
            }
            if (ne) hasNeg[mode]++;
            if (as) asym[mode]++;
            // 跑一遍快速幂，看「加完才取模」那一版有没有哪一次乘法真的越界
            Mat res(m); for (int i = 0; i < m; i++) res.a[i][i] = 1;
            Mat B = A; ll b = k; bool ov = false;
            while (b) {
                if (b & 1) { if (mulOverflows(res, B, m)) ov = true; res = mul(res, B, m); }
                if (mulOverflows(B, B, m)) ov = true;
                B = mul(B, B, m);
                b >>= 1;
            }
            if (ov) realOv[mode]++;
        }

    /* ③ 交换律：A 的两个幂 ↔ 两个不同的矩阵 */
    int powCommute = 0, diffCommute = 0;
    {
        mt19937 rng(20260902u);
        for (int t = 0; t < 300; t++) {
            int m = 2 + (int)(rng() % 3u);
            Mat A(m), B(m);
            for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) {
                ll u = (ll)(rng() % 2001u) - 1000, v = (ll)(rng() % 2001u) - 1000;
                A.a[i][j] = ((u % MOD) + MOD) % MOD;
                B.a[i][j] = ((v % MOD) + MOD) % MOD;
            }
            Mat A2 = mul(A, A, m), A3 = mul(A2, A, m);
            if (mul(A2, A3, m).a == mul(A3, A2, m).a) powCommute++;      // A² · A³ ↔ A³ · A²
            if (mul(A, B, m).a == mul(B, A, m).a) diffCommute++;         // A · B ↔ B · A
        }
    }

    /* ④ 顶格秒表：n = 100、k = 10¹² */
    double msFast; ll mulCount;
    {
        int m = 100;
        Mat A(m);
        mt19937 rng(7u);
        for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) A.a[i][j] = (ll)(rng() % 2001u);
        ll k = 1000000000000LL;
        auto t0 = steady_clock::now();
        Mat res(m); for (int i = 0; i < m; i++) res.a[i][i] = 1;
        Mat B = A; ll b = k; mulCount = 0;
        while (b) { if (b & 1) { res = mul(res, B, m); mulCount++; } B = mul(B, B, m); mulCount++; b >>= 1; }
        msFast = duration<double, milli>(steady_clock::now() - t0).count();
        volatile ll sink = res.a[0][0]; (void)sink;
    }

    if (csv) {
        printf("lineN,%lld\n", lineN);
        for (int i = 0; i < 6; i++) printf("bigN%d,%d\n", i, bigN[i]);
        for (int i = 0; i < 6; i++) printf("realOv%d,%d\n", i, realOv[i]);
        for (int i = 0; i < 6; i++) printf("hasNeg%d,%d\n", i, hasNeg[i]);
        for (int i = 0; i < 6; i++) printf("asym%d,%d\n", i, asym[i]);
        for (int i = 0; i < 6; i++) printf("kZero%d,%d\n", i, kZero[i]);
        printf("powCommute,%d\n", powCommute);
        printf("diffCommute,%d\n", diffCommute);
        printf("msFast,%.0f\n", msFast);
        printf("mulCount,%lld\n", mulCount);
        printf("bruteMuls,%s\n", "1e12");
        return 0;
    }
    printf("① 「内层加完才取模」那条线：(2⁶³−1) / (10⁹+6)² = **%lld** ⇒ 最多安全加 %lld 项 ⇒ **n ≥ %lld 起危险**\n",
           lineN, lineN, lineN + 1);
    printf("\n② 六个档各 300 轮\n");
    const char* NM[6] = {"顺手写的（n≤4、非负）", "含负数", "对称矩阵", "n ∈ [10,16]", "k = 0", "n ∈ [90,100]"};
    for (int i = 0; i < 6; i++)
        printf("   档 %d %-22s n ≥ 10 的 %3d 轮 ／ **真的加爆的 %3d 轮** ／ 含负数 %3d ／ 不对称 %3d ／ k=0 %3d\n",
               i, NM[i], bigN[i], realOv[i], hasNeg[i], asym[i], kZero[i]);
    printf("   ⇒ ★★ 第一层（n ≥ 10）在档 3 和档 5 上都是 300，**一点区分度都没有**；\n");
    printf("      真正决定抓不抓得到的是第二层「那一行的和有没有越过 2⁶³」\n");
    printf("\n③ 交换律：300 组随机矩阵\n");
    printf("   A² · A³ == A³ · A² 的组数：%d / 300（★ 同一个矩阵的两个幂**总是**可交换）\n", powCommute);
    printf("   A · B  == B · A  的组数：%d / 300（★ 两个不同的矩阵**几乎从不**可交换）\n", diffCommute);
    printf("   ⇒ 「res = A · res」不是 bug，靠的正是第一行；而第二行就是它的自检\n");
    printf("\n④ 顶格 n = 100、k = 10¹²（独占实测）：快速幂 %.0f 毫秒，一共做了 %lld 次矩阵乘\n", msFast, mulCount);
    printf("   而「连乘 k 次」要做 10¹² 次矩阵乘 ⇒ 差 %.0f 亿倍\n", 1e12 / mulCount / 1e8);
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

只有第 ② 版能交，而它和第 42 章那五行是同一段代码

版本	顶格 `n = 100, k = 10¹²`	交上去
① 连乘 `k` 次	10¹² 次矩阵乘	0 分
★ ② 矩阵快速幂	53 次矩阵乘 / 41 毫秒	★ AC

⇒ 这道题的价值不在「写一个矩阵乘」，在看懂快速幂到底依赖什么：

它要的只是结合律。 换成矩阵能用，换成「只留末 500 位」也能用（下一道 P1045 就是后者）。

⚠ 而三个坑全长在数据范围那一行上（0 ≤ k、|A| ≤ 1000、n ≤ 100）， 顺手写的生成器会把三个一起盖住 —— 这一页的四张表就是为这件事准备的。

洛谷 P3390 【模板】矩阵快速幂

0题目原文（本地存了一份）

输入

输出

输入

输出

1第 ① 版：老老实实乘 k 次

2★★★ 关键一步：快速幂要的只是结合律

3⚠ 「res = A · res」看着很危险 —— 而它一次都不会错

4★★★ 三笔必须自己算的账 —— 而顺手写的生成器把三个坑全盖住了

5⚠⚠ 官方给了两组样例 —— 而它们不是同一件事的重复

6★ 哪一版就已经能过了