一、题目描述
1. 问题背景
阿坤老师带来了一个特殊的魔方，其每个面都是一个 N×N 的整数方阵。学生可以对魔方的任意一面进行如下操作：将矩阵的任意一行或任意一列的所有元素，沿该行（或该列）循环移动任意整数个位置。目标是经过若干次（包括零次）这样的操作后，使得方阵主对角线（从左上角到右下角，即位置 (0,0), (1,1), …, (N-1, N-1)）上所有元素之和达到最大。你的任务是计算出这个可能的最大和。
2. 输入输出格式
- 输入格式：
- 第一行包含一个整数 N (1 ≤ N ≤ 1000)，表示方阵的尺寸。
- 接下来 N 行，每行包含 N 个整数，表示方阵的元素。方阵元素均为整数，范围在常规 32 位有符号整数可表示的范围内。
- 输出格式：
- 输出一个整数，表示通过循环移动操作后，能够获得的主对角线元素之和的最大值。
理解这道题背后的数学原理非常重要。这道题的核心不在于复杂的计算，而在于坐标变换的规律。
我们可以把这道题的数学原理拆解为三个步骤：坐标定义、移动规律、以及等效性分析。
1. 坐标与主对角线的定义
在一个 $N \times N$ 的方阵中，每一个小格子都有一个坐标 $(i, j)$，其中 $i$ 代表行号，$j$ 代表列号（通常从 $0$ 到 $N-1$）。
- 主对角线的特征是：行号等于列号。
- 数学表达式：$i = j$。
- 例如，在一个 $3 \times 3$ 的矩阵中，主对角线的坐标是：$(0,0), (1,1), (2,2)$。
2. “循环移动”在数学上做了什么？
当我们对所有的行进行循环移动时，实际上是改变了每一行相对于列的“起始位置”。
假设我们将所有行向下循环移动了 $k$ 个位置：
- 原来的第 $0$ 行变成了现在的第 $k$ 行。
- 原来的第 $i$ 行变成了现在的第 $(i+k) \pmod N$ 行。
此时，新的主对角线对应的元素，在原始矩阵中满足：
$$新行号 = 新列号$$
$$(i + k) \pmod N = j$$
这里的 $\pmod N$ 是取模运算，保证坐标在 $0$ 到 $N-1$ 之间循环。
3. 核心发现：循环对角线
你会发现，无论 $k$ 取什么值，最终落在对角线上的 $N$ 个元素，在原矩阵中始终满足一个固定的关系：
$$j – i \equiv k \pmod N$$
这里的 $k$ 就是偏移量。对于每一个确定的 $k$，都会对应一组互不重复的 $N$ 个元素。
- 当 $k=0$ 时，就是原矩阵的主对角线。
- 当 $k=1$ 时，就是原矩阵主对角线向右平移一格的那条线（溢出的部分会从左边绕回来）。
结论： 题目要求的“最大主对角线之和”，本质上就是让我们在 $N$ 条“循环对角线”中，找到元素之和最大的那一条。
4. 为什么“移动列”和“移动行”是一样的？
你可能会问：“阿坤老师说可以移位行，也可以移位列，这两种操作会有不同结果吗？”
数学上的等效性：
- 将所有行向下移动 1 位，等效于将所有列向上移动 1 位。
- 这就像你在拨动一个密码锁，拨动外圈和拨动内圈，产生的“相对位移”是一样的。
因此，我们只需要考虑一种方向的偏移（比如固定行，只考虑列的偏移 $k$），就能涵盖所有可能产生的情况。
5. 算法实现逻辑
既然知道了原理，代码的逻辑就变成了：
从这 $N$ 个和中挑出最大的那一个。
计算 $k=0$ 时的对角线之和：$A[0][0] + A[1][1] + \dots$
计算 $k=1$ 时的对角线之和：$A[0][1] + A[1][2] + \dots + A[N-1][0]$
…
计算 $k=N-1$ 时的对角线之和。