群论

【9】群的基本概念
【9】置换群与循环群

群

在数学中，群是由一个集合以及一个二元运算所组成的，符合下述四个性质（称为“群公理”）的代数结构。这四个性质是封闭性、结合律、单位元和对于集合中所有元素存在逆元素。
首先我们有一个集合$S$。

1. 封闭性：对于所有$G$中的$a, b$，运算$a \times b$的结果也在$G$中。
2. 结合律：对于所有$G$中的$a, b,$和$c$，等式$(a \times b) \times c = a \times (b \times c)$成立.
3. 单位元：存在$G$中的一个元素$e$，使得对于所有$G$中的元素$a$，总有等式$e \times a = a \times e = a$成立
4. 逆元：对于每个$G$中的$a$，存在$G$中的一个元素$b$使得总有$a \times b = b \times a = e$，此处$e$为单位元。

群运算的次序很重要，把元素$a$与元素$b$结合，所得到的结果不一定与把元素$b$与元素$a$结合相同；亦即$a \times b = b \times a$（交换律）不一定恒成立。满足交换律成立的群称为交换群（阿贝尔群，以尼尔斯·阿贝尔命名），不满足交换律的群称为非交换群（非阿贝尔群）。

置换群

Burnside引理

$$|X / G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$$

Polya定理

Polya定理是Burnside引理在染色情况下的一个特例。

我们可以把排列，写成若干个轮换的形式，其中轮换的个数叫做

一维的情况

答案是
$$\frac{1}{n} \sum_{i=1}^{n} c^{\gcd(i, n)}$$
如果有对称的话，需要根据$n$的奇偶进行讨论。
如果$n$是奇数
$$\frac{1}{2n} (n c^{(n+1)/2} + \sum_{i=1}^{n} c^{\gcd(i, n)})$$
如果$n$是偶数
$$\frac{1}{2n} (n/2 c^{n/2} + n/2 c^{n/2 + 1} + \sum_{i=1}^{n} c^{\gcd(i, n)})$$

其中$\sum_{i=1}^{n} c^{\gcd(i, n)}$部分可以进一步优化为先枚举最大公约数。
$$\sum_{i=1}^{n} c^{\gcd(i, n)} = \sum_{i | n} c^i \varphi(n/i) = \sum_{i | n} c^{n/i} \varphi(i)$$

所以只需要预处理$n$的所有约数$x$和对应的欧拉函数值$\varphi(x)$即可。

二维的情况

答案是
$$\frac{1}{nm} \sum_{i=1}^{n} \sum_{j=1}^{m} c^{nm / \mathrm{lcm}(n/\gcd(i,n),m/\gcd(i,m))}$$
同样可以进一步优化为先枚举最大公约数，设
$a = n / \gcd(i, n), b = m / \gcd(j, m)$
原式可以化为
$$\frac{1}{nm} \sum_{a|n} \sum_{a|m} \varphi(a) \varphi(b) c^{nm / \mathrm{lcm}(a, b)}$$

所以只需要预处理$n, m$的所有约数$x$和对应的欧拉函数值$\varphi(x)$即可。

生成数据

https://gist.github.com/dario2994/fb4713f252ca86c1254d
在int范围内比较大的高合成数（任何比它小的自然数的约数个数均比这个数的约数个数少）
735134400 = 2^6 * 3^3 * 5^2 * 7 * 11 * 13 * 17，1344个约数
1102701600 = 2^5 * 3^4 * 5^2 * 7 * 11 * 13 * 17，1440个约数
1396755360 = 2^5 * 3^3 * 5 * 7 * 11 * 13 * 17 * 19，1536个约数
2095133040 = 2^4 * 3^4 * 5 * 7 * 11 * 13 * 17 * 19，1600个约数

参考题目

poj 2409

poj 2888

hdu 5868

sgu 282

bzoj 1004

bzoj 1488

参考资料

Group