HJ69. 矩阵乘法
题目描述
给定 A(m×s)、B(s×n) 两个矩阵，计算乘积 C = A × B。
输入格式
- 第 1 行：m、s、n
- 接下来 m 行：A 的每行 s 个数
- 接下来 s 行：B 的每行 n 个数
输出格式
m 行，每行 n 个数，即 C 的每一行（空格分隔）。
示例
示例 1
输入：
2 3 2
1 2 3
3 2 1
1 2
2 1
3 3
输出：
14 13
10 11
说明： A 为 2×3 矩阵，B 为 3×2 矩阵，乘积 C 为 2×2 矩阵。
解题思路
第一步：理解问题本质
矩阵乘法定义：C[i][j] = Σ_k A[i][k] * B[k][j]。结果的第 i 行第 j 列，等于 A 的第 i 行与 B 的第 j 列对应元素相乘后求和。A 的列数 s 必须等于 B 的行数 s。
第二步：暴力解法（按公式直接三重循环）
最直接的方式就是按公式，对每个 C[i][j] 求和 s 项：
C = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
for k in range(s):
C[i][j] += A[i][k] * B[k][j]
这就是标准解法，复杂度 O(m·s·n)。
第三步：关于更优解法的思考
对于一般的稠密矩阵乘法，目前最优算法（Strassen 等）也只是渐进上的改进，工程中很少使用。本题矩阵规模不大，直接用三重循环即可达到最优的实用效果。
第四步：最终实现
读取 A、B 后，三重循环计算 C，按行输出即可。
完整代码实现
算法可视化 · 逐帧回放这道题的代码3 帧 · 录制输入
import sys
def solve() -> None:
data = sys.stdin.buffer.read().split()
it = iter(data)
m, s, n = int(next(it)), int(next(it)), int(next(it))
A = [[int(next(it)) for _ in range(s)] for _ in range(m)]
B = [[int(next(it)) for _ in range(n)] for _ in range(s)]
C = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
total = 0
for k in range(s):
total += A[i][k] * B[k][j]
C[i][j] = total
for row in C:
print(' '.join(map(str, row)))
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，A 为 2×3，B 为 3×2：
A = [[1, 2, 3],
[3, 2, 1]]
B = [[1, 2],
[2, 1],
[3, 3]]
计算 C[0][0]（A 第 0 行 × B 第 0 列）：
1*1 + 2*2 + 3*3 = 1 + 4 + 9 = 14
计算 C[0][1]（A 第 0 行 × B 第 1 列）：
1*2 + 2*1 + 3*3 = 2 + 2 + 9 = 13
计算 C[1][0]（A 第 1 行 × B 第 0 列）：
3*1 + 2*2 + 1*3 = 3 + 4 + 3 = 10
计算 C[1][1]（A 第 1 行 × B 第 1 列）：
3*2 + 2*1 + 1*3 = 6 + 2 + 3 = 11
结果矩阵：
14 13
10 11
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 三重循环 | O(m·s·n) | O(m·n) | 存储结果矩阵 C |
m、s、n 分别为 A 的行数、A 的列数（B 的行数）、B 的列数
易错点总结
1. 维度匹配错误
矩阵乘法要求 A 的列数等于 B 的行数（都是 s），否则无法相乘。读取时 A 读 s 个数每行，B 读 n 个数每行，不能搞混。
2. 累加忘记清零
每个 C[i][j] 必须独立累加，若用同一个 total 变量而未在每轮归零，会累加错误。
3. 三重循环的下标对应错误
内层求和下标是 k，C[i][j] 累加的是 A[i][k] * B[k][j]，写反成 A[k][i] * B[j][k] 会报错或得到错误结果。
扩展思考
- 数据量很大时可用 NumPy 的矩阵运算加速，但 ACM 环境通常只允许标准库。
- 矩阵乘法的结合律、交换律性质是理解动态规划矩阵链乘优化（最优括号化）的基础。