题面
给定 ,存在 的任意矩阵,现在求其转置矩阵,但仅能用交换两个元素的操作,求最少的操作次数能够求得任意该大小矩阵的转置矩阵。特别地,我们将矩阵抽象成序列,具体地,按照第一行的元素、第二行的元素、第三行的元素……存储。
Solution
题解里都是缩点再染色的,这里提供一个更好理解一点的思路。对于前置转化和之后的推导和其他题解类似这里不再赘述,可以直接去看其它题解,也可以看我的博客 浅析群论 中例题 #6 #7 部分。
考虑将二进制数抽象为长度为 的环,对其进行 染色,置换为旋转 (显然最后一项等效为单位元,即旋转 )。发现这样设计即可满足置换群的所有要求,且符合题意。
考虑套用一下 Polya,对于旋转 ,显然环的个数为 ,黑白染色即为 ,所以令 ,答案即为:
然后进行一些转化:
接下来的步骤则与一般推导相同。
UPD
update-2023_03_14 初稿