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/−11/-11/−1这样每个操作都能写成一个4×44\times 44×4矩阵乘法。2. 六种操作如何作用在(i,j,t)(i,j,t)(i,j,t)R/LR/LR/L只改列jjjD/UD/UD/U只改行iiiIII行取逆(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)三个分量的“对应关系 偏移量”因为最终一定是(ix, jy, tz)(ix,\ jy,\ tz)(ix,jy,tz)的某种重排会更简洁。3. 合并所有操作设每一步操作矩阵为MkM_kMk​把它们按顺序相乘得到总矩阵AAAAMmMm−1⋯M1 AM_mM_{m-1}\cdots M_1AMm​Mm−1​⋯M1​随后对初始矩阵中每个元素只做一次YA⋅(i,j,t,1)T YA\cdot(i,j,t,1)^TYA⋅(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(mn2)O(mn^2)O(mn2)