CF1458C 题解

以后可能随机发一点小题解，不再执着于完美整理一整份大题解了。

1. 状态表示

先把所有量转成0∼n−10 \sim n-10∼n−1（行、列、值都减一），并在模nnn意义下计算。
对一个元素，用四维向量表示：

X=(i, j, t, 1)X=(i,\ j,\ t,\ 1)X=(i,j,t,1)

• iii：当前行
• jjj：当前列
• ttt：当前值
• 最后一维常数111用来处理平移（如+1/−1+1/-1+1/−1）

这样每个操作都能写成一个4×44\times 44×4矩阵乘法。

2. 六种操作如何作用在(i,j,t)(i,j,t)(i,j,t)

• R/LR/LR/L：只改列jjj
• D/UD/UD/U：只改行iii
• III（行取逆）：(i,j,t)→(i,t,j)(i,j,t)\to(i,t,j)(i,j,t)→(i,t,j)
• CCC（列取逆）：(i,j,t)→(t,j,i)(i,j,t)\to(t,j,i)(i,j,t)→(t,j,i)

可以看到，I/CI/CI/C本质是维度交换，R/L/U/DR/L/U/DR/L/U/D是某一维加减常数。因此它们都属于线性（仿射）变换，可统一成矩阵。

另外矩阵写法稍重了一些；也可以直接维护(i,j,t)(i,j,t)(i,j,t)三个分量的“对应关系 + 偏移量”，因为最终一定是(i+x, j+y, t+z)(i+x,\ j+y,\ t+z)(i+x,j+y,t+z)的某种重排，会更简洁。

3. 合并所有操作

设每一步操作矩阵为MkM_kMk​，把它们按顺序相乘得到总矩阵AAA：

A=MmMm−1⋯M1 A=M_mM_{m-1}\cdots M_1A=Mm​Mm−1​⋯M1​

随后对初始矩阵中每个元素只做一次：

Y=A⋅(i,j,t,1)T Y=A\cdot(i,j,t,1)^TY=A⋅(i,j,t,1)T

得到最终(行,列,值)(\text{行},\text{列},\text{值})(行,列,值)，填入答案矩阵即可。

4. 正确性要点

• 每步操作都是双射（循环位移或逆排列），组合后仍是双射；
• 所以每个初始元素会映射到唯一终态，不会冲突也不会丢失；
• 用矩阵连乘只是把这组双射“打包”起来一次应用。

5. 复杂度

• 预处理总变换：O(m)O(m)O(m)（矩阵是固定4×44\times44×4，常数很小）
• 枚举所有元素映射：O(n2)O(n^2)O(n2)
• 总复杂度：O(m+n2)O(m+n^2)O(m+n2)