自动搬运

查看原文

来自洛谷，原作者为

	览遍千秋 将伤与泪汇成力化作拳

搬运于2025-08-24 21:17:23，当前版本为作者最后更新于2025-02-16 21:48:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Source and Knowledge

2025 年 2 月语言月赛，由洛谷网校提供。

考察高维数组，及高维数组向一维数组的映射。

---

文字题解

首先，我们考察题目给出的高维数组求和公式。

$$S[w_0][w_1]\cdots[w_{x-1}][w_{x+1}]\cdots[w_{n-1}]=\sum\limits_{i=0}^{d_x-1}{a[w_0][w_1]\cdots[w_{x-1}][i][w_{x+1}]\cdots[w_{n-1}]} $$

符号释义。$\sum\limits_{i=1}^n{a_i}$ 表示 $a_1+a_2+\cdots+a_n$。$\prod\limits_{i=1}^n{a_i}$ 表示 $a_1\times a_2\times \cdots \times a_n$。

简而言之，$n$ 维数组沿 $x$ 号轴求和，会得到一个 $n-1$ 维的数组。第 $x$ 号轴上的下标内容无关紧要，是其他 $n-1$ 维的轴决定了，这个数会被加在答案数组的哪一个位置上。例如，$5$ 维数组沿 $2$ 号轴求和。对于 $a[1][2][?][4][5]$，我们并不需要关心 $?$ 的值具体是多少，只需要知道其他 $4$ 维的值，就知道这个数应该被加到 $S[1][2][4][5]$ 中。

部分分 1：$n=2$

对于 $60\%$ 的测试数据，$n=2$，即输入是一个二维数组。因此，答案应该是一个一维数组。

直接将输入存储到一个二维数组中。考虑到数据范围中 $1\le d_i \le 10^3$ 的限制，定义一个 $1000\times 1000$ 的二维数组 $a$ 即可。同时，定义一个一维数组 $S$ 用来求和。

对于 $x=0$，即将 $a[?][w_1]$ 加到 $S[w_1]$ 中（按列求和）。对于 $x=1$，即将 $a[w_0][?]$ 加到 $S[w_0]$ 中（按行求和）。

for(int i = 0; i < d[0]; i++) {
    for(int j = 0; j < d[1]; j++) {
        if(x == 0) S[j] += a[i][j];
        else S[i] += a[i][j];
    }
}

正解

但是，对于全部的数据，数组的维度 $n$ 是不确定的。虽然题目保证了 $\prod d_i$ 的值不超过 $2^{16}$，这个大小的数组是可以开下的，但是由于数组维度的不确定性，我们没有办法按照部分分的做法，去开好存储数组和答案数组，循环计算。而本题的难点就在于，如何把一个高维数组，映射到低维度的数组中。

我们回顾一个 $N\times M$ 的二维数组（从 $0$ 开始存储），如果我们想要给 $(i,j)$ 一个编号，一般采用 $i\times M+j$。这样，就实现了二维数组向一维的映射。

这样的结论，是否可以从二维数组，推广到 $N$ 维数组呢？

$N$ 维数组 $D_0 \times D_1 \times \cdots \times D_{n-1}$ 中，记 $M(i)=\prod\limits_{p=i}^{n-1}{D_p}=D_i\times D_{i+1}\times \cdots \times D_{n-1}$，特别的，对于 $i\ge n$，$M(i)=1$，$A[W_0][W_1]\cdots[W_n]$ 可以映射到 $\sum\limits_{i=1}^{n-1}{W_{i}\cdot M(i+1)}$。

上面的结论可以在二维数组中得到验证。

回顾题目，我们需要一个 $n-1$ 维数组 $S$，用于存储和。每一维的大小依次为 $d_1,d_2,\cdots,d_{x-1},d_{x+1},d_{x+2},\cdots,d_{n-1}$（没有 $d_x$）。对于输入的 $a[w_0][w_1]\cdots[w_{x-1}][?][w_{x+1}][w_{x+2}]\cdots[w_{n-1}]$，加到 $S[w_0][w_1]\cdots[w_{x-1}][w_{x+1}][w_{x+2}]\cdots[w_{n-1}]$ 中。应用上面的映射方法，可以将这个 $S$ 数组映射到一维，便于求和。

但是，输出的时候，需要输出 $n-1$ 维数组的下标，但是这些下标被映射到了一维，这怎么办呢？一维数组的下标可以还原出 $n-1$ 维数组的下标。我们假设要还原的下标为 $id$，$W_i=\lfloor \dfrac{id \bmod M(i)}{M(i+1)} \rfloor$。

$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。例如，$\lfloor 1.1 \rfloor=1$，$\lfloor 1 \rfloor=1$，$\lfloor -1.1 \rfloor=-2$。

这个公式也可以在二维数组中得到验证。例如，一个 $5\times 4$ 的二维数组，$(2,3)$ 的编号是 $2\times 4+3=11$，$D_0=5,D_1=4,M(1)=4,M(0)=20$。计算上面的公式，$W_0=\lfloor \dfrac{11\bmod 20}{5} \rfloor=2$，$W_1=\lfloor \dfrac{11\bmod 4}{1}\rfloor =3$。

综上，我们已经解决了本题，总结如下：

• 将高维的 $S$ 数组，通过 $S[w_0][w_1]\cdots[w_{x-1}][w_{x+1}][w_{x+2}]\cdots[w_{n-1}]\to \sum\limits_{i=1}^{n-1}{W_{i}\cdot M(i+1)}$ 映射为一维
• 通过 $W_i=\lfloor \dfrac{id \bmod M(i)}{M(i+1)} \rfloor$。 还原一维到 $n-1$ 维。

---

命题后记

在语言月赛中，这样一道 F 题是非常难的了。对于刚完成语言学习的同学来说，难以完成是非常正常的。

本题的操作实际上，是要求选手实现 numpy 中，nparray 的 sum 函数。因此，使用 Python 可以更加容易的完成本题。

当然，C++ 中 map 等 STL 容器，可以非常便捷的完成高维向低维的映射，但是考虑到语言月赛的定位，不再提及。

这题评分为普及-的原因，主要在于不考虑语言月赛限定的考察范围，使用 STL 后，本题极为简单。