粉福：见操作后相同算重考虑Burnside引理

OtterZ · 2025-01-10 10:26:26 · 算法·理论

1. Burnside 引理

结论：对于集合 X 和置换群 G，若 X 对于 G 中置换封闭，有 X 轨道数为 \frac{\sum_{g\in G}\sum_{x\in X}[x\circ g = x]}{|G|}，比较官方的说法是 \frac{\sum_{g\in G}|X ^ g|}{|G|},X^g = \{x\in X|x \circ g = x\}。

这里给出来自百科的证明方法。

这个引理适应于题目中指出经过若干次操作后相同算一种情况。

2. 基于 Burnside 引理的解题思路

1. 构造和验证置换群

我们要保证计算时用的置换操作与合并运算能组成群，也就是说，这个组合符合群的判定定理，一般采用定义法。我们需要验证：

• 封闭性：集合内任意两个元素合并后的结果也在集合内。
• 运算结合律：我们随意改变合并运算的操作顺序是不会改变结果的。

符合这两个条件的属于半群，接下来验证：

• 存在单位元：即一个元素，任意一个元素与之合并不会改变。

我们保证是幺半群，最后验证：

• 逆元：对于任意一个元素，存在另一个元素，两元素合并产生单位元，且这样的元素对一一对应。注意，一个元素可以和自己互为逆元，及操作两次形成单位元。

验证到这里才会保证是群。这是不少题解不会提供但需要自行验证的内容。

另外要保证 X 对于 G 中置换封闭。

2. 每种集合的计算方法

按操作后相同的条件进行计算即可。有时可以整体处理进行优化。

3. 例题

1. CF2040F，题解写的比较详细，注意里面的思路，复现一下过程；
2. CF1065E，注意群其实是操作集 \{(b_{i - 1},b_i]\}(b_0 = 0) 的所有子集中所有元素的操作合并得到的操作集合与合并操作组成的群，需要整体处理；
3. P1446直接给置换群是有一点绝了；
4. CF1954F。