SP422 TRANSP2 - Transposing is Even More Fun Solution

更好的阅读体验戳此进入

题面

给定 $a,b$$a, b$，存在 $2^a\times 2^b$$2^a \times 2^b$ 的任意矩阵，现在求其转置矩阵，但仅能用交换两个元素的操作，求最少的操作次数能够求得任意该大小矩阵的转置矩阵。特别地，我们将矩阵抽象成序列，具体地，按照第一行的元素、第二行的元素、第三行的元素……存储。

Solution

题解里都是缩点再染色的，这里提供一个更好理解一点的思路。对于前置转化和之后的推导和其他题解类似这里不再赘述，可以直接去看其它题解，也可以看我的博客 浅析群论 中例题 #6 #7 部分。

考虑将二进制数抽象为长度为 $a+b$$a + b$ 的环，对其进行 $0/1$$0/1$ 染色，置换为旋转 $a,2a,3a,\cdots ,{\displaystyle \frac{a+b}{gcd(a,b)}}a$$a, 2a, 3a, \cdots, \dfrac{a + b}{\gcd(a, b)}a$（显然最后一项等效为单位元，即旋转 $0$$0$）。发现这样设计即可满足置换群的所有要求，且符合题意。

考虑套用一下 Polya，对于旋转 $ka$$ka$，显然环的个数为 $gcd(ka,a+b)$$\gcd(ka, a + b)$，黑白染色即为 $2^{gcd(ka,a+b)}$$2^{\gcd(ka, a + b)}$，所以令 $n={\displaystyle \frac{a+b}{gcd(a,b)}}$$n = \dfrac{a + b}{\gcd(a, b)}$，答案即为：

然后进行一些转化：

接下来的步骤则与一般推导相同。

UPD

update-2023_03_14 初稿