Counting Stars

· · 题解

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-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 后，本题极为简单。