1 条题解

  • 0
    @ 2024-6-4 17:00:16

    太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了太典了。

    典到题目名称都叫 classical 了。

    先考虑同一个方阵的同一行,此时 Wi,j=(Ai+Bj)modmW_{i,j}=(Ai+Bj)\bmod m,当 0j<m0\le j<m0<B<m0<B<m 时显然有 Wi,jW_{i,j} 互不相同。同理,同一列的数也互不相同。

    考虑操作 1,仅对方阵平移,上述性质显然不变。操作 2,发现 f(a)f(a) 显然只能取到第一种情况:置换(你有没有发现后三题都是排列运算)。所以始终满足同行同列互不相同。

    行列都有操作有些困难。不妨考虑特殊性质 2,32,3 操作都没有。线段树维护位移量即可做到单 log\log,但我很良心放了平方过。

    考虑 subtask 4。维护每个矩阵置换了几次,最后置换环上倍增跳,复杂度 O(m2logm+q(logn+logm))O(m^2\log m+q(\log n+\log m))

    考虑正解。将一个方阵抽象成 m2m^2 个三元组:(i,j,Wi,j)(i,j,W_{i,j})。操作 11 即对前两维加减。令人兴奋的事实出现了:操作 22 为交换第二第三维的值!同理,操作 33 为交换第一第三维的值!

    维护模板 (p3,Δ1,Δ2,Δ3)(p_3,\Delta_1,\Delta_2,\Delta_3) 表示,当前第 ii 维是原来的第 pip_i 维加上 Δi\Delta_i。得到每个方阵的模板即可解出此位置的值。

    考虑维护该模板,也是最无脑最典的部分:直接用 7×77\times7 的转移矩阵加线段树更新之。再加的一维是常数 11。考虑到排列也许只需要记录两个数即可,可能可以优化成 6×66\times 6,但是我没仔细想。记矩阵维度 d=7d=7,最后的时间复杂度 O(q0d3logn+qlogn)O(q_0d^3\log n+q\log n),很松。也许需要小心取模。

    • 1

    信息

    ID
    947
    时间
    3500ms
    内存
    1024MiB
    难度
    6
    标签
    (无)
    递交数
    6
    已通过
    2
    上传者