UVa10294

Lyccrius · 2023-06-01 18:31:45 · 题解

• 对于一个置换 f，若一个着色方案 s 经过置换后不变，称 s 为 f 的不动点。
• Burnside 引理：将 f 的不动点数目计为 C(f)，则可以证明等价类数目为所有 C(f) 的平均值。
• Polya 引理：等价类的个数等于所有置换 f 的 k^{m(f)} 的平均数，其中 m(f) 为置换 f 分解后的循环个数。

旋转

旋转间距为 g 时，0, g, 2g, \cdots 构成一个循环。

设该循环元素个数为 x，则 xg = \text{lcm} (g, n) = \frac{gn}{\gcd(g, n)}，故 x = \frac{n}{\gcd(g, n)}。

这样的循环有 \gcd(g, n) 个。

这些置换的不动点数为 a = \sum_{i = 1}^{n - 1} t^{\gcd(i, n)}。

翻转

按 n 的奇偶性讨论。

奇数

对称轴有 n 条，每条对称轴形成 \frac{n - 1}{2} 个长度为 2 的循环和 1 个长度为 1 的循环，即 \frac{n + 1}{2} 个循环，这些循环的不动点数为 b = n t^{\frac{n + 1}{2}}。

偶数

对称轴有 2 种。

• 穿过珠子的对称轴有 \frac{n}{2} 条，分别形成 \frac{n - 2}{2} 个长度为 2 的循环和 2 个长度为 1 的循环。
• 不穿过珠子的对称轴有 \frac{n}{2} 条，分别形成 \frac{n}{2} 个长度为 2 的循环。

这些置换的不动点数为 b = \frac{n}{2 (t^{\frac{n}{2} + 1} + t^{\frac{n}{2}})}。

项链总数为 \frac{a}{n}。

手镯总数为 \frac{a + b}{2n}。