AT_arc018_3 [ARC018C] 席替え

我所在的学校每个班级的人数特别多，甚至有多达 $1,000,000$ 人的班级。我的班级也不例外。教室的座位排成 $N$ 行 $M$ 列的矩形，共有 $N \times M$ 名学生，每人拥有一张自己的桌子。 学校非常重视防灾意识，如果发生意外，教室后面的墙壁可以打开，让学生从这里避难。最近，学校决定让成绩好的学生优先撤离，所以我们班决定重新安排座位，让成绩好的学生坐得更靠后。具体来说，把最前面的一行称为第 $0$ 行，最左边的一列称为第 $0$ 列。位于第 $i$ 行第 $j$ 列的座位用 $(i, j)$ 表示，坐在这个位置的学生成绩用 $G[i][j]$ 表示。对于任意两个座位 $(a, b)$ 和 $(c, d)$，如果 $a > c$，则无论 $b, d$ 的值如何，必须满足 $G[a][b] \geq G[c][d]$。 学生可以自由移动到任意座位，但是不能有两个或更多学生坐在同一座位，也不能有空位。同时，桌子数量不能改变，仍保持 $N$ 行 $M$ 列的布局。 重新安排座位是好事，但由于人数众多，我们希望尽量减少所有学生移动的总距离。这里的移动距离是指从原座位到新座位的曼哈顿距离，即如果一个学生从 $(a, b)$ 移动到 $(c, d)$，则移动距离为 $|a - c| + |b - d|$。 给定所有学生在重新安排前的成绩数据，请计算所有学生的最小移动距离总和。 ### 输入格式 - 第一行包含两个整数 $N$ 和 $M$，分别表示教室的行数和列数（$1 \le N, M \le 1,000$）。 - 第二行包含三个整数 $x_0$、$a$ 和 $p$，用来生成每位学生的初始成绩（$0 \le x_0, a \le 10^9$，$N \times M \le p \le 10^9$，$p$ 必为素数）。初始成绩通过递归式 $x_i = (x_{i-1} + a) \mod p$ 生成。在位置 $(i, j)$ 的学生成绩为 $x_{i \times M + j}$。 ### 输出格式 输出所有学生移动距离最小总和。最后包括一个换行符。 ### 数据范围和提示 - $1 \le N, M \le 1,000$ - $0 \le x_0, a \le 10^9$ - $N \times M \le p \le 10^9$ 且 $p$ 为素数 ### 示例 #### 输入 ``` 2 3 1 2 59 ``` #### 输出 ``` 0 ``` #### 解释 重新安排座位前，学生的成绩如下： ``` 1 3 5 7 9 11 ``` 各座位在自己后面（屏幕下方）没有比自己成绩更差的学生，因此无需重新安排。 #### 输入 ``` 2 3 6 55 59 ``` #### 输出 ``` 2 ``` #### 解释 重新安排座位前，学生的成绩如下： ``` 6 2 57 53 49 45 ``` 交换座位 $(0, 2)$ 和 $(1, 2)$ 的学生即可。两者分别移动 1 个单位，总移动距离为 2。 #### 输入 ``` 4 5 15 25 79 ``` #### 输出 ``` 26 ``` #### 解释 重新安排座位前，学生的成绩如下： ``` 15 40 65 11 36 61 7 32 57 3 28 53 78 24 49 74 20 45 70 16 ``` 符合条件的重新安排如： ``` 15 7 16 11 3 28 20 32 24 36 53 40 45 57 49 74 61 65 70 78 ``` **本翻译由 AI 自动生成**

无

无