【题解】P4128 [SHOI2006] 有色图

TallBanana · 2025-05-17 14:08:17 · 题解

我们使用 Burnside 引理，那么我们只需要对于确定的置换环大小数组进行算答案即可了。若置换环大小数组为 a_1,a_2,a_3,\cdots,a_t，那么令 X=\sum_{i=1}^t (\left\lfloor \frac{a_i}{2} \right\rfloor+\sum_{j=i+1}^t \gcd(a_i,a_j))，不动点个数为 m^X。

你发现这个 a 不多，在 n=53 时最多只有 329931，那么直接对于每个暴力算即可。