题目来源：改编自严蔚敏《数据结构（C 语言版）》3.3 数组的顺序存储与寻址、王道《数据结构》3.3 多维数组的行优先/列优先地址计算。
数组逻辑上可以有很多维，物理上却只是一段连续的内存。把多维下标映射到这段内存的哪一个位置，取决于两件事：存储顺序（行优先还是列优先）与元素字节数 w。Lab 03-E-09 只做了行优先偏移；本题在同一个程序里把行优先偏移、列优先偏移、以及它们对应的真实字节地址一起算出来，并统一按“第 k 维下标每 +1，偏移增加多少”这个 stride（跨度） 的口径来推导两种公式。规模上本题也刻意放大：当 n=10、每维长度都是 20 时，数组共有 20¹⁰ ≈ 1.02×10¹³ 个元素，地址可达 8.3×10¹³——int 一定会溢出，必须用 64 位整数。
题目
行优先与列优先的内存布局
设 n 维数组 A[b[0]][b[1]]…[b[n-1]]，各维下标从 0 开始，idx[k] ∈ [0, b[k]-1]，元素大小为 w 字节，基址（第 0 个元素的首字节地址）为 base。
行优先（Row Major Order）：最后一维的下标变化最快——先把最后一维走完，再进倒数第二维，依此类推。列优先（Column Major Order）：第一维的下标变化最快。两种顺序下，第 k 维下标每增加 1，一维偏移就增加一个固定的量，这个量就是该维的 stride：
- 行优先：
rowStride[k] = b[k+1] × b[k+2] × … × b[n-1]（k = n-1时是空乘积，取1）； - 列优先：
colStride[k] = b[0] × b[1] × … × b[k-1]（k = 0时是空乘积，取1）。
于是两种偏移都写成“下标 × stride”的求和：
两个公式只在连乘的范围上不同：行优先乘的是下标之后各维的长度，列优先乘的是下标之前各维的长度。两者的关系是
（下标 k 之前的长度进了 colStride[k]，之后的长度进了 rowStride[k]，再补上自己这一维就是全乘积），并且两端都是空乘积：rowStride[n-1] = colStride[0] = 1。
一句话记法：行优先——前面的维“重”，最后一维“轻”；列优先正好反过来，第一维“轻”，后面的维“重”。 同一组下标在两种顺序下的偏移一般不同（只有 n=1、或各维长度为 1、或恰好在“两端”时才可能相等）。
从偏移到字节地址
一维偏移量是“第几个元素”（从 0 数起），真实地址要再乘上元素字节数，并加上基址：
这就是教材里的 LOC(j₀,…,j_{n-1}) = base + (Σ j_k·stride_k) × w：先算元素偏移，再乘字节数。w 可以取 1（char）、2（short）、4（int）、8（long long / double）。
任务要求
- 从标准输入读入维数
n、各维长度b[0..n-1]、元素字节数w、基址base、查询个数q，以及q组下标； - 对每组下标输出一行四个整数：
行优先偏移 行优先地址 列优先偏移 列优先地址； - 偏移与地址都必须精确，不允许溢出；
- 四个整数用单个空格分隔，行末无多余空格；输出行数与查询个数
q相同。
输入格式
- 第一行：
n（维数）； - 第二行：
n个整数，各维长度b[0..n-1]； - 第三行：
w（每个元素占用的字节数）； - 第四行：
base（基址，即偏移为0的元素的地址）； - 第五行：
q（查询个数）； - 随后
q行，每行n个整数，表示一组下标idx[0..n-1]（0-based，保证合法）。
输出格式
- 共
q行，每行四个整数：行优先偏移 行优先地址 列优先偏移 列优先地址。
数据范围与限制
| 项目 | 范围 |
|---|---|
n | 1 ≤ n ≤ 10 |
b[k] | 1 ≤ b[k] ≤ 20 |
w | 1 ≤ w ≤ 8 |
base | 0 ≤ base ≤ 10¹² |
q | 1 ≤ q ≤ 3×10³ |
| 总元素数 | 最大 20¹⁰ ≈ 1.02×10¹³ |
| 偏移量 | 最大 20¹⁰ − 1 ≈ 1.02×10¹³ |
| 地址 | 最大 10¹² + (20¹⁰ − 1)×8 ≈ 8.3×10¹³ |
| 时间复杂度 | O(n²·q)（含 stride 预计算可做到 O(n·q)） |
| 空间复杂度 | O(n) |
为什么必须用 64 位整数
n=10、每维长度都是 20 时，偏移最大是最后一个元素的行优先偏移
20^9 + 20^8 + … + 20^0 = 20^10 - 1 ≈ 1.02×10^13写成十进制是 13 位数；乘上 w = 8 再加上 base = 10^12 后，地址最大约
10^12 + 10239999999999 × 8 = 82919999999992 ≈ 8.3×10^13也是 14 位数。C++ 的 int（32 位有符号）只能表示到 2 147 483 647 ≈ 2.15×10^9，unsigned int 也只到 4.29×10^9——连一个 stride 都放不下（20^9 = 5.12×10^11 就已经溢出）。溢出后高位被截断，结果可能变成负数或完全错误的数值，而 tokens 判题是逐 token 精确比较，错一位就是 0 分。
因此本题的 b、idx、stride、偏移和地址统统用 long long（64 位，上界约 9.22×10^18，足够容纳 8.3×10^13）。注意即使最终偏移会很大，中间量 stride 也会很大，所以不能“用 int 存结果、用 long long 只算最后一步”。
样例
样例输入 1
2
3 4
2
1000
1
1 2样例输出 1
6 1012 7 1014样例输入 2
3
2 3 4
4
500
1
1 2 1样例输出 2
21 584 11 544样例解释
样例 1：二维数组 A[3][4]，查询下标 (1, 2)，w = 2 字节，base = 1000。
先求两种顺序下的 stride：
维 k | b[k] | 行优先 stride（b[k+1..n-1] 连乘） | 列优先 stride（b[0..k-1] 连乘） |
|---|---|---|---|
| 0 | 3 | b[1] = 4 | 空乘积 = 1 |
| 1 | 4 | 空乘积 = 1 | b[0] = 3 |
再逐维累加：
- 行优先偏移
= 1×4 + 2×1 = 6； - 列优先偏移
= 1×1 + 2×3 = 7。
最后换算地址：
- 行优先地址
= 1000 + 6×2 = 1012； - 列优先地址
= 1000 + 7×2 = 1014。
两个偏移只差 1，是因为这是 3×4 的小数组；把下标换成 (2, 3) 会得到 11 与 9（地址 1022 与 1018），差距仍然不大——但维数一多、各维长度拉开了，差距会迅速放大。
样例 2：三维数组 A[2][3][4]，查询下标 (1, 2, 1)，w = 4 字节，base = 500。stride 逐个列出：
维 k | b[k] | 行优先 stride | 列优先 stride |
|---|---|---|---|
| 0 | 2 | b[1]×b[2] = 3×4 = 12 | 空乘积 = 1 |
| 1 | 3 | b[2] = 4 | b[0] = 2 |
| 2 | 4 | 空乘积 = 1 | b[0]×b[1] = 2×3 = 6 |
逐维累加：
- 行优先偏移
= 1×12 + 2×4 + 1×1 = 12 + 8 + 1 = 21； - 列优先偏移
= 1×1 + 2×2 + 1×6 = 1 + 4 + 6 = 11。
地址换算：
- 行优先地址
= 500 + 21×4 = 500 + 84 = 584； - 列优先地址
= 500 + 11×4 = 500 + 44 = 544。
可以这样检查 stride 是否算对：对每一维都有 rowStride[k] × colStride[k] × b[k] = 总元素数（下标 k 之前的长度进了 colStride，k 之后的长度进了 rowStride，再乘上自己这一维就是全乘积）。代入 总元素数 = 2×3×4 = 24：12×1×2 = 24、4×2×3 = 24、1×6×4 = 24，三行全部对得上。
如何验证
先安装 Node.js、pnpm 和支持 C++17 的编译器。GNU Make 是首选入口，但不是强制依赖。
# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample-2d
make interactive
make scoreWindows 没有安装 Make 时，在仓库根目录使用完全相同的评分内核：
pnpm lab:doctor -- labs/chapter-03/exercise/E-03-19-row-col-major-addressing
pnpm lab:run -- labs/chapter-03/exercise/E-03-19-row-col-major-addressing
pnpm lab:score -- labs/chapter-03/exercise/E-03-19-row-col-major-addressing思考题
- 行优先与列优先的 stride 定义只差连乘范围。为什么
rowStride[k] × colStride[k] × b[k]恒等于数组总元素数？ - 遍历一个
b[0]×b[1]×…的大数组时，如果访问顺序与存储顺序不一致（例如列优先存储却按行优先顺序遍历），缓存命中率会发生什么变化？为什么 C 语言里的“i 在外层、j 在内层”通常更快？ - 如果各维下标从
1开始（而不是0），公式要怎样调整？设下界为l[k]，写出LOC(idx) = base + (Σ (idx[k] − l[k])·stride[k]) × w并说明理由。 - 一维偏移最大约
1.02×10¹³，为什么连中间量 stride 也必须用 64 位，而不能只在最后一步用long long兜底？
题解
点击查看题解
思路
对每一组查询，分别求两种存储顺序的偏移：
- 行优先：从最后一维往前扫，维护“后缀乘积”作为当前维的 stride。设
rowStride = 1，从k = n-1递减到0，累加idx[k] × rowStride，然后把rowStride乘上b[k]； - 列优先：从第一维往后扫，维护“前缀乘积”。设
colStride = 1，从k = 0递增到n-1，累加idx[k] × colStride，然后把colStride乘上b[k]。
两个方向的关系是互为反向遍历：行优先的 stride 序列是后缀连乘，列优先的是前缀连乘，所以同一段循环只要换个方向就得到另一种顺序，这也是本题最容易写反的地方。最后 地址 = base + 偏移 × w。
本题 n ≤ 10、q ≤ 3×10³，即使对每组查询都用两重循环现场算 stride（O(n²·q) = 3×10⁵ 次乘法）也很快；若把 stride 预先算好复用，则是 O(n·q)。
复杂度分析
- 现场算 stride：时间
O(n²·q)，空间O(n)； - 预计算 stride：时间
O(n + n·q)，空间O(n)。
两种写法都能通过。瓶颈不在算法，而在数据类型：long long 是本题唯一的硬性要求。
边界注意
n=1时rowStride[0]与colStride[0]都是空乘积1，两种偏移相等，都等于idx[0]；b[k]=1时该维下标只能是0，相当于该维不存在，两个偏移自然相等；- 全部下标为
0时偏移为0，地址恰为base；全最大下标时偏移取到Σ(b[k]−1)·stride[k] = 元素总数 − 1； base最大10¹²，本身就在 32 位之外，读入时就要用long long；- 乘法顺序无关，但每个乘数都必须是 64 位，
long long × int会先提升为long long，而int × int会先在 32 位里溢出； - 本题不涉及非法输入：下标始终保证合法。
参考代码
#include <iostream>
#include <vector>
// 参考解：行优先与列优先偏移都能达到 20^10 级别，地址最大约 8.3e13，
// 必须全程使用 64 位整数（int 会溢出）。
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
std::cin >> n;
std::vector<long long> dims(n);
for (int k = 0; k < n; ++k) std::cin >> dims[k];
long long wordSize = 0;
long long base = 0;
std::cin >> wordSize >> base;
int q = 0;
std::cin >> q;
std::vector<long long> idx(n);
while (q-- > 0) {
for (int k = 0; k < n; ++k) std::cin >> idx[k];
// 行优先：第 k 维的 stride 是 b[k+1..n-1] 的连乘（最后一维为 1）。
long long rowOffset = 0;
for (int k = 0; k < n; ++k) {
long long stride = 1;
for (int s = k + 1; s < n; ++s) stride *= dims[s];
rowOffset += idx[k] * stride;
}
// 列优先：第 k 维的 stride 是 b[0..k-1] 的连乘（第一维为 1）。
long long colOffset = 0;
for (int k = 0; k < n; ++k) {
long long stride = 1;
for (int s = 0; s < k; ++s) stride *= dims[s];
colOffset += idx[k] * stride;
}
std::cout << rowOffset << ' ' << base + rowOffset * wordSize << ' '
<< colOffset << ' ' << base + colOffset * wordSize << '\n';
}
return 0;
}