题目链接

传送门
CF的题面是真的没法粘hhh

题解

Michael_Bryant打了这场的CF 然后感觉ABCD四题拼手速
然后EF都是神仙题 先改了E
放一个原版作者题解吧 传送门
这个题说的是对一个每行每列都是$1-n$全排列的矩阵进行变换
行变换是向上或向下移动每行 列变换是向左或向右移动每列
还有一个行和列的排列变换 排列变换的定义是
对于一个排列$p_1,p_2,...,p_n$ 我们令一个新的排列满足$ \forall i , p _ { q _ i } = i $ 则该排列$q$为排列$p$的排列变换
观察数据范围 发现我们不能针对每次变换都暴力更新矩阵(废话
考虑该题的简化版 即我们取消排列变换这种操作
我们发现我们锁定这个矩阵左上角点的位置即可 然后根据它最后的位置即可推算出每个元素的位置
此时我们发现这样的操作存在于一个二维的平面
那我们此时回过头来看排列变换的操作
此时我们将矩阵的行列编号变为$0,1,...,n-1$
相应地 矩阵中数也每个都$-1$
(是为了方便进行矩阵的行数取模操作 其实不换也无所谓)
以行变换为例 现在给出一个排列$2,1,3,0$ 笔者给出其排列变换是$3,1,0,2$
我们规定三元组$(i,j,k)$中对应的原题信息为$a[i][j]=k$
这样的话我们对应到上述排列变换 四个三元组分别是
$(0,0,2),(0,1,1),(0,2,3),(0,3,0)$
变换后的四个三元组是
$(0,0,3),(0,1,1),(0,2,0),(0,3,2)$
我们发现每个三元组的第二维与第三维交换后的三元组出现在了第二行
所以我们认为这种排列变换是交换两维的
同理 对于列向量的排列变换的是一,三维
所以我们就可以通过上述两类思路 预处理排列变换后每个单位向量$v_x = (1,0,0) , v_y = (0,1,0) , v_z = (0,0,1)$现在所在的方向 以及原点$(0,0,0)$现在所在的位置
我们可以开始统计答案了
对于原点在$(i,j,k)$的情况下 一个原来的点$P(x_0 , y_0 ,z_0)$现在所在的坐标是 $P'(i + x _ 0 * v _ x , j + y _ 0 * v _ y, k + z _ 0 * v _ z )$
这样就可以了
这样的话是在三维空间去进行的
当然我们也不非要从原点的位置去推现在每个点的位置 再进行坐标的对应
我们也可以像处理二维空间一样 记录三个维度都进行了什么样的变换
将每一维的坐标进行变换后再相对应的放到现在应在的维度 这样相对写起来更容易
值得注意的是我们需要维护一个数组
去找变换后的$i$维是变换之前的哪一维
细节看代码吧
真是一道很神的思维题

代码