阅读了 <Pólya 计数法的应用> 一文, 对里面的例题做一下笔记. >_<

• [UVA 10601] Cubes 用 12 根有颜色的等长棍子搭立方体, 旋转后颜色相同的方案算一种, 求方案数.
• [SPOJ 419] [SPOJ 422] Transportation is fun 给一个 2^a 2^b 的矩阵, 在内存中从上往下, 从左往右连续存放. 用交换操作求它的转置矩阵, 存储方式相同, 求最小步数.
• [SGU 282] Isomorphism 染色图是边带颜色的无向完全图. 求 N 个顶点, M 种颜色 (不必用完), 两两不同构的染色图个数模质数 P. (1 ≤ N ≤ 53, 1 ≤ M ≤ 1000, N < P ≤ 10^9)

Burnside 引理

是待计数的对象的集合, 是置换群. 对于 , 如果存在 , 使得 , 则 视为相同的对象. 中不同对象的数目 . 其中 为 中满足 的 (不动点) 的数目. = 不动点数目的平均值.

考虑 是格子的染色方案这种情形. 对置换做循环分解, 那么每个循环里的格子的颜色相同. 设用 种颜色染色, 可以分解成 个循环, 则 .

[UVA 10601] Cubes

所有置换是三种基本置换的复合, 打个表, 发现共有 24 个, 按照循环的大小可分为以下 5 类:

1 1 1 1 1 1 1 1 1 1 1 1 (1 个)
1 1 2 2 2 2 2 (6 个)
2 2 2 2 2 2 (3 个)
3 3 3 3 (8 个)
4 4 4 (6 个)

除了第 2 类, 全都是相等的元素: 考察每种颜色用在哪里, 组合数计算方案数, 每种颜色的方案数相乘. 对于第 2 类, 先枚举一下哪两条边对应1.

如果没有这样的特征还不大好算......状压 DP.

[SPOJ 419] [SPOJ 422] Transportation is fun

看起来不像等价类计数问题, 但是可以往这个方向转化.

原位置到目标位置的对应关系构成一个置换. 最优交换方式是直接换......对于一个长度为l的循环, 最少用l-1次交换使其复位. 设置换可以分解为m个循环, 则ans = 2^(a+b) - m.

地址和长度为 a+b 的 01 串一一对应. (i,j) 的地址为i 2^b + j (0 <= i < 2^a, 0 <= j < 2^b), 可以看到其二进制表示就是i的二进制表示 ++ j的二进制表示, 高位用 0 补齐. 那么, (i,j) 变到 (j,i) 就是 01 串循环右移 b 位.

我们要求(i,j) -> (j,i)这个置换的循环的个数, 也就是在循环右移 b 位这个置换下等价类的数目. 可以用 Burnside 引理解决, 推导与b=1的情形类似,

[SGU 282] Isomorphism

同构问题也是等价类计数问题. 我们借助较为简单的点的置换来考虑边的置换.

设一个点的置换 分解为大小分别为 的循环. 和边的置换 一一对应. 我们关注的是 的循环的大小的构成.

一条边 , 设 在循环 中, 在循环 中, 那么 同样满足 . 所以, 我们可以分别考虑每个点置换的循环对的贡献. - 两端点都在 中的边构成的循环. 个, 每个对应一种 "边长". - 端点分别在 中的边构成的循环. 一条边经过 次变换才回到原位, 即它所在循环的大小为 . 由对称性知循环有 个.

枚举 , 现在我们可以在已知 的前提下计算 的循环的数目. 顶点数 很小, 由对称性, 不妨枚举 的拆分, 即 . 需要求出每个拆分对应多少个点的置换. 先把循环看成两两不同的. 为每个点划分它归属的循环, 这是可重集的排列问题. 枚举循环的构成: 元素两两不同, 长度为 的循环有 种构成. 如果 , 大小为 的循环在 上不同的排列方式之前被我们看成了不同的方案, 所以答案要除以 .

和 [UVA 10601] Cubes 的思想类似. 循环大小的构成相同的置换可以一起计算不动点的数目.