形式化题目

给定整数矩阵 $A \in \mathbb{Z}^{n \times m}$ 与 $B \in \mathbb{Z}^{m \times k}$，其中 $1 \leqslant n, m, k < 100$，且每个元素的绝对值不超过 $1000$。求由

定义的 $n \times k$ 矩阵 $C$。

样例：$A$ 是 $3 \times 2$ 的全 $1$ 矩阵，$B$ 是 $2 \times 3$ 的全 $1$ 矩阵，乘积 $C$ 是 $3 \times 3$ 的全 $2$ 矩阵。

正解

思路

为什么没有别的做法。 定义已经把答案写死了：$C$ 的每个元素都是 $A$ 的一行与 $B$ 的一列这两个长度为 $m$ 的向量的点积，一共有 $n \cdot k$ 个这样的元素，整个问题没有任何需要搜索、排序或优化的自由度。所以正解就是照着公式枚举三层下标：

1. 枚举输出的行 $i$（$n$ 种）与列 $j$（$k$ 种）；
2. 对固定的 $(i, j)$，枚举中间下标 $t$（$m$ 种），把 $A[i][t] \cdot B[t][j]$ 累加进一个临时变量 dot；
3. 把 dot 写进 $C[i][j]$，最后按行输出。

规模上界是 $n \cdot m \cdot k < 100^3 = 10^6$ 次乘加，时限 $1000$ ms 下完全不构成压力，不需要任何优化。

每个元素是"一行乘一列"。 下面的图画出 $C[i][j]$ 的来源：$A$ 的第 $i$ 行横着取，$B$ 的第 $j$ 列竖着取，两者逐位相乘再求和。

1
2A 的第 i 行:  (1  1)
B 的第 j 列:  (1  1)   ->  1*1 + 1*1 = 2 = C[i][j]

样例里 $A$、$B$ 全是 $1$ 且 $m = 2$，所以每个 $C[i][j]$ 都等于 $2$。下表展开三个不同位置的元素，确认"行号只决定取 $A$ 的哪一行、列号只决定取 $B$ 的哪一列"：

观察重点：三个格子只是 $(i, j)$ 取值不同，求和结构完全一样，$t$ 是行和列共用的下标。这就是代码里最内层 for (t = 1; t <= m; t++) 存在的唯一理由。

循环顺序可以换。 把 $i$-$j$-$t$ 换成 $i$-$t$-$j$（先枚举行、再枚举中间下标、最后枚举列），得到的是"用 $A[i][t]$ 去更新 $C$ 第 $i$ 行的每个位置"，与定义完全等价：整数加法满足交换律和结合律，累加顺序不影响结果。这里选定义顺序 $i$-$j$-$t$，因为它与公式逐项对应、最好读；$i$-$t$-$j$ 的顺序让第 $i$ 行的更新连续访问内存，在大矩阵上对缓存更友好，但本题 $10^6$ 的规模下两者都是毫秒级，不构成取舍。

Python 里怎么写得短。 三层显式循环在 Python 里要写三层缩进，而"点积"正好可以交给标准库：先用 zip(*b) 把 $B$ 转成"按列存"的形式，再让 $A$ 的每一行依次与 $B$ 的每一列配对，math.sumprod(row, col) 一步算出点积。于是整个乘法只剩一行列表推导式，内层循环由 C 实现完成，代码短且不慢。

类型与溢出。 $|C[i][j]| \leqslant m \cdot 1000 \cdot 1000 \leqslant 10^8$，32 位 int 其实也放得下，但 C++ 代码统一用 long long 存放矩阵元素与点积，省掉"会不会刚好溢出"的推理；Python 整数本身没有溢出问题。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:03
# update_at: 2026-10-07 15:03

import sys
from collections.abc import Iterator
from math import sumprod

type Matrix = list[list[int]]  # 矩阵按行存：matrix[i] 是第 i 行，元素是整数
type Tokens = Iterator[bytes]  # 一次读入后按空白切分的整数流，顺序消费


def read_matrix(rows: int, cols: int, data: Tokens) -> Matrix:
    """从整数流里顺序取数，读入 rows 行 cols 列的矩阵。"""
    return [[int(next(data)) for _ in range(cols)] for _ in range(rows)]


def multiply(a: Matrix, b: Matrix) -> Matrix:
    """按定义做矩阵乘法：C[i][j] = Σ_t A[i][t] * B[t][j]。"""
    columns = list(zip(*b))  # zip(*b) 把 B 的第 j 列收成一个元组
    return [[sumprod(row, col) for col in columns] for row in a]  # sumprod 就是点积


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, m, k = int(next(data)), int(next(data)), int(next(data))
    a = read_matrix(n, m, data)
    b = read_matrix(m, k, data)
    for row in multiply(a, b):
        print(' '.join(map(str, row)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:03
 * update_at: 2026-10-07 15:03
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 105;

ll a[MAXN][MAXN]; // A 矩阵：n 行 m 列，a[i][j] 是第 i 行第 j 列的元素
ll b[MAXN][MAXN]; // B 矩阵：m 行 k 列，b[t][j] 是第 t 行第 j 列的元素
ll c[MAXN][MAXN]; // C 矩阵：n 行 k 列，c[i][j] 是 A 第 i 行与 B 第 j 列的点积

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%lld", &a[i][j]);

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= k; j++)
            scanf("%lld", &b[i][j]);

    // 三重循环按定义算 C：外层枚举行 i 与列 j，内层枚举中间的 t 累加乘积
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++) {
            ll dot = 0; // A 第 i 行与 B 第 j 列的点积，即 C[i][j]
            for (int t = 1; t <= m; t++)
                dot += a[i][t] * b[t][j];
            c[i][j] = dot;
        }

    // 输出 C：每行 k 个整数，整数之间用一个空格分开
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j > 1) printf(" ");
            printf("%lld", c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

复杂度

• 时间复杂度：$O(nmk)$。$C$ 有 $n \cdot k$ 个元素，每个元素花 $O(m)$ 做点积；输入规模本身就是 $nm + mk$ 个数，读入不超过 $O(nmk)$（因为 $k, m \geqslant 1$）。上界 $10^6$ 次乘加。
• 空间复杂度：$O(nm + mk + nk)$，即存下 $A$、$B$、$C$ 三个矩阵。Python 版额外用 zip(*b) 存了一份 $m \times k$ 的列视图，同阶；总内存远低于 $128$ MB。

总结

• 矩阵乘法没有算法空间：按定义枚举 $(i, j, t)$ 三重下标，$C[i][j]$ 就是 $A$ 第 $i$ 行与 $B$ 第 $j$ 列的点积。
• 三层循环的顺序可以任意调换，整数加法满足交换律与结合律；$i$-$j$-$t$ 最贴近公式，$i$-$t$-$j$ 对缓存更友好，本题规模下无差别。
• 复杂度 $O(nmk)$ 时间、$O(nm + mk + nk)$ 空间；$n, m, k < 100$ 时最多 $10^6$ 次乘加，$1000$ ms 时限下余量充足。
• 边界：$n$、$m$、$k$ 都可能取 $1$（真实数据里有 $1 \times 1 \times 1$ 和 $99 \times 1 \times 99$ 的极端形状），此时点积只有一项，代码不需要任何特判；元素含负数，答案也可能是负数，同样不需要特判。