【SHOI 2006】有色图

题意

假设有一张 \(n\) 阶完全图，每条边有一个颜色，那么叫它有色图。定义两个有色图本质相同，当且仅当存在一种点的置换，使得置换以后两张图每条边颜色对应相同。计数若颜色有 \(m\) 种，有多少本质不同的 \(n\) 阶有色图。

数据范围：\(1\le n\le 53, 1\le m\le 1000\)。

题解

Polya 定理好题，不是太过困难，但是很具有启发性。

考虑 Polya 定理，需要确定边置换的环个数。然而题目中的置换是点置换，所以探究两者之间的关系。点置换还是拆成环来考虑，考虑这个视角下边的变换是怎样的。如果两个端点在一个置换环上，那么每一次会让两个端点同时平移一下，于是两个边在同一个边置换环里当且仅当它们环上长度一样，总共有 \(\lfloor\frac{|C|}{2}\rfloor\) 个边置换环。然后再考虑端点在两个不同环里的，那么这种情况下每条边在一条大小为 \(\operatorname{lcm}\{|C_1|, |C_2|\}\) 的边置换环中，于是置换环个数为 \(\gcd\{|C_1|, |C_2|\}\)。

所以只需要知道每个点置换环的大小的可重集。拆分数枚举一下这个集合，贡献的系数也很好计算。