题解

问题分析

我们有一个 $n \times n$ 的拉丁方阵，每行每列都是 $1,2,\dots,n$ 的一个排列。有六种操作：

• R/L：所有列循环右移/左移
• D/U：所有行循环下移/上移
• I：每一行求逆（将行视为排列，替换为其逆排列）
• C：每一列求逆（将列视为排列，替换为其逆排列）

需要处理 $m$ 次操作后输出最终的矩阵。

核心思想

这个问题的关键在于：我们不需要真的模拟每次操作对矩阵的修改，因为操作只是在重新排列元素的位置或者改变元素的值，本质上是在变换 $(行, 列, 值)$ 这三个坐标之间的对应关系。

每个矩阵元素可以表示为一个三元组 $(r, c, v)$，其中：

• $r$ 是行号 $(1 \le r \le n)$
• $c$ 是列号 $(1 \le c \le n)$
• $v$ 是元素的值 $(1 \le v \le n)$

初始时，位置 $(i, j)$ 上的元素就是 $(i, j, a_{i,j})$。

操作的三元组解释

我们可以定义三个“维度”：

• 维度 0：行坐标
• 维度 1：列坐标
• 维度 2：值

用一个数组 $pos[3]$ 记录当前矩阵中“行”对应哪个原始维度，“列”对应哪个原始维度，“值”对应哪个原始维度。

初始状态：

$$pos[0] = 0, \quad pos[1] = 1, \quad pos[2] = 2$$

移位操作

• U（上移一行）：每行的行号减 $1$ 这等价于：维度 $0$（当前对应的原始维度）的坐标减少 $1$

  $$offset[pos[0]] \leftarrow offset[pos[0]] - 1$$

• D（下移一行）：每行的行号加 $1$

  $$offset[pos[0]] \leftarrow offset[pos[0]] + 1$$

• L（左移一列）：每列的列号减 $1$

  $$offset[pos[1]] \leftarrow offset[pos[1]] - 1$$

• R（右移一列）：每列的列号加 $1$

  $$offset[pos[1]] \leftarrow offset[pos[1]] + 1$$

这里 $offset[k]$ 表示原始维度 $k$ 上的累计位移。

求逆操作

• I（行内求逆）： 对于每一行，将行内的排列替换为其逆排列。
  在排列 $p$ 中，逆排列 $q$ 满足 $p_{q_i} = i$。
  理解成三元组：原来元素在 $(行, 列, 值)$，求逆后变为 $(行, 值, 列)$。
  即行不变，列和值交换：

  $$swap(pos[1], pos[2])$$

• C（列内求逆）： 对于每一列，将列内的排列替换为其逆排列。
  原来元素在 $(行, 列, 值)$，求逆后变为 $(值, 列, 行)$。
  即列不变，行和值交换：

  $$swap(pos[0], pos[2])$$

算法步骤

1. 读入初始矩阵，将每个元素存储为三元组 $(i, j, a_{i,j})$。

2. 初始化：

   $$pos = [0, 1, 2], \quad offset = [0, 0, 0]$$

3. 处理操作序列： 遍历每个操作字符，根据上述规则更新 $pos$ 和 $offset$。

4. 生成最终矩阵： 对于每个原始三元组 $(r_0, c_0, v_0)$：

   • 最终行号：$r = ((r_0 + offset[pos[0]] - 1) \bmod n) + 1$
   • 最终列号：$c = ((c_0 + offset[pos[1]] - 1) \bmod n) + 1$
   • 最终值：$v = ((v_0 + offset[pos[2]] - 1) \bmod n) + 1$

   将 $v$ 填入答案矩阵的 $(r, c)$ 位置。

复杂度分析

• 时间复杂度：$O(n^2 + m)$

  • 读入矩阵：$O(n^2)$
  • 处理操作：$O(m)$
  • 生成最终矩阵：$O(n^2)$

• 空间复杂度：$O(n^2)$

由于所有测试用例的 $n$ 之和不超过 $1000$，$m$ 之和不超过 $10^5$，这个复杂度完全可行。

正确性证明

引理 1：六种操作都可以表示为对三元组 $(r, c, v)$ 的坐标变换。

证明：

• 行移位：只改变 $r$，加上一个偏移量
• 列移位：只改变 $c$，加上一个偏移量
• 行求逆：交换 $c$ 和 $v$ 的角色
• 列求逆：交换 $r$ 和 $v$ 的角色

引理 2：$pos$ 数组和 $offset$ 数组可以累积所有操作的效果。

证明：由于操作都是可交换的（除了求逆操作需要记录顺序），我们可以通过维护当前映射关系来复合所有操作。求逆操作本质上是交换维度，而移位操作是在当前映射下的坐标偏移。

结论：经过所有操作后，每个原始元素的新位置和新值可以由上述公式唯一确定，且拉丁方阵的性质保持不变。

示例验证

以第一个样例为例：

$$n=3,\ m=2,\ \text{操作序列}=\text{"DR"}$$

初始矩阵：

$$\begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{bmatrix}$$

处理过程：

• 初始：$pos=[0,1,2],\ offset=[0,0,0]$
• 操作 D：$offset[pos[0]]=offset[0]=1$，$offset=[1,0,0]$
• 操作 R：$offset[pos[1]]=offset[1]=1$，$offset=[1,1,0]$

最终，对于原始元素 $(1,1,1)$：

• 新行：$(1+1-1)\bmod 3+1=2$
• 新列：$(1+1-1)\bmod 3+1=2$
• 新值：$(1+0-1)\bmod 3+1=1$

所以 $ans[2][2]=1$，与输出一致。

注意事项

1. 模运算处理：C++ 的 % 对负数结果可能为负，需要调整为 $[0, n-1]$ 范围。
2. 坐标转换：存储时使用 $0$-based 或 $1$-based 要统一，最后输出时转换回 $1$-based。
3. 多测试用例：注意重置数组和变量。

这个解法的精妙之处在于将复杂的矩阵变换转化为简单的坐标映射和偏移计算，避免了直接模拟操作的高复杂度。