今天上数学课时比较清闲（主要是感觉逻辑用语没什么好学的），于是缓缓打开了大白书…
本来想看矩阵的…发现前面的内容就只有置换没看了，一时兴起就把置换解决掉…

定义

简单来说，置换是一个在正整数[1,n]到正整数[1,n]上的一一映射，将1,2,3…n变为a1,a2,a3…an，记为

(123...na1a2a3...an)\begin{pmatrix} 1 & 2 & 3 & ... & n \\ a_1 & a_2 & a_3 & ... & a_n \end{pmatrix}

也可用函数表示，记为f={a1,a2,a3,…,an}f=\{a_1,a_2,a_3,…,a_n\}
为了表示方便，常常将一个置换表示成几个循环乘积的形式。循环即为几个元素交替，例如(1,3,2)表示1→3,3→2,2→1.下面是一个用循环分解置换的例子。

(1234535142)=(13)(25)(4)\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 3 \end{pmatrix} \begin{pmatrix} 2 & 5 \end{pmatrix} \begin{pmatrix} 4 \end{pmatrix}

应该很好理解。显而易见，循环的计算满足交换律。
我们称循环的个数为循环节，如上图置换的循环节为3.

计算

置换间可定义乘法，如f={1,3,2},g={2,1,3} → fg={2,3,1}.
置换的乘法满足结合律，但不满足交换律。

应用：等价类计数问题

以下面问题为例，介绍两个定理。
给2×2的方格黑白染色，共有几种方法？答案显而易见，是如下图的16种。

但如果考虑“旋转同构”，将逆时针旋转90°，180°，或270°都相同的方案看做一种，答案就只有如下6种了

这就是等价类计数问题，也就是，题目中会定义一种等价关系，满足等价关系的所有元素被分为同一个等价类，他们共同为答案贡献1。
我们发现，等价关系满足自反性，对称性和传递性。

我们把F定义为一个置换集合，集合里元素乘积也在集合里，用它来描述等价关系。
如上面例子中，我们有F={①逆时针旋转0°,②逆时针旋转90°,③逆时针旋转180°,④逆时针旋转270°}，这样我们就可以用这个集合表示所有等价关系了。
需要注意的是，①②③并不能构成一个“置换群”，因为②×③=④并不在集合里。

对一个置换f,若一个元素经过置换后不变。则称它为f的不动点。

Burnside 引理
计f的不动点数目为C(f),等价类集合数目为所有C(f)的平均值。

如上面的例子，C(①)的不动点有1-16，C(②)的不动点有1,16,10,7，C(③)的不动点有1,16，C(④)的不动点有1,16，故根据Burnside 引理，等价的方案有(16+4+2+2)/4=6个。是不是很神奇呢？

而已知一个置换，怎么快速求C(f)C(f)呢？
回想用循环表示置换，我们发现，若一个循环中所有元素状态相同，则一定有置换后不变。
设ff分解为m⋅(f)m\cdot (f)个循环的乘积，每单个元素有kk种状态（如黑白染色是两种），有C(f)=km⋅(f)C(f)=k^{m\cdot (f)}，这就是Polya定理。
基础的知识就告一段落辣…

例题

[UVa 10294] Arif in Dhaka

  • [Description]
    t种颜色的珠子中选n个串成间距相等的圆形项链。问若旋转后项链相同算一种，问有几种项链；旋转或翻转后（形态和位置）相同算一种，问有几种项链。
  • [Solution]
    第一种较为简单。共有n种旋转的置换(旋转0~n-1个位置)，旋转i个位置的循环节为gcd(i,n)，所以ans1=(∑i=0n−1tgcd(i,n))nans_1=(\sum^{n−1}_{i=0}\frac{t^{gcd(i,n)})}{n}
    第二种除了旋转，还有翻转。翻转需分类讨论，若n为奇数，共有n条对称轴，每条对称轴的循环节为n/2+1，所以总不动点数x=n×tn/2+1x=n×t^{n/2+1}；若n为偶数，有n/2条对称轴串过珠子，每条对称轴的循环节为n/2-1，有n/2条对称轴不串过珠子，每条对称轴的循环节为n/2，总不动点数x=n/2×(tn/2−1+tn/2)x=n/2×(t^{n/2−1}+t^{n/2})，得出ans2=(ans1∗n+x)/2nans2=(ans1∗n+x)/2n.

[LA 3641] Leonardo’s Notebook

  • [Description]
    给出26个字母的一个置换B，问是否存在一个置换A，满足A2=B.
  • [Solution]
    给出B后我们可以分循环来讨论。
    对于某一个循环a，若元素数n为奇数，我们不难找到一种方案：ai->ai+n/2+1，两次置换后得到ai->ai+1，这就是B.
    而若n为偶数，我们同一个循环肯定不能“开根号”，但是我们发现，若有两个长度均为n的循环a,b，它们的乘积却可以。a={a1,a2…an},b={b1,b2…bn}，ab=(a1,a2…an)(b1,b2…bn)=(a1,b1,a2,b2…an,bn)×(a1,b1,a2,b2…an,bn).这样也有解。
    这样，将B拆成循环进行判断即可。

[UVa 11077] Find the Permutations

  • [Description]
    给定n,k(k≤n≤21)，问有多少个n的全排列至少进行两个元素的互换操作才能变成{1,2…n}.
  • [Solution]
    观察发现，全排列的一个循环交换有序需要循环元素个数-1次交换。
    设f[i][j]表示i的全排列进行两个元素的互换操作才能变成{1,2…i}的个数，容易得到递推式

f[i][j]=f[i−1][j]+f[i−1][j−1]∗(i−1)f[i][j]=f[i−1][j]+f[i−1][j−1]∗(i−1)

f[i-1][j]表示直接把i放在最后，自成一个循环；f[i-1][j-1]表示把i插入任意一个循环，使这个循环得交换次数+1，因为可以插入任何一个位置，共有i-1种插法。边界为f[1][0]=1,其他f[1]={0}.
很善意地不要打高精度。

[LA 3510] Pixel Suhffle

  • [Description]
    给n*n矩阵的矩阵定义8×2种操作（具体见题），给定一串命令，有多个操作组成，求至少经过多少次命令后矩阵才能恢复。
  • [Solution]
    以前似乎做过一道一维简化版的…
    就是直接模拟一遍操作，记录所有方格移动到的位置，然后找到所有循环。
    设每个循环有x个元素，所以循环内的元素要恢复，就必须完成x的倍数次操作。
    所以所有循环元素个数的最小公倍数即是问题的答案。
    AC此题需要耐心。