群论和线性基

# 群论和线性基 ## 前置芝士 [置换群](https://oiwiki.org/math/permutation-group/) [Burnside引理和Polya定理](https://blog.csdn.net/liangzhaoyang1/article/details/72639208) [线性基](https://blog.csdn.net/a_forever_dream/article/details/83654397) ### 群 >对于一个集合 $S$和一种运算$\cdot$，构成的代数结构 $(S,\cdot)$ 满足封闭性，结合律，有单位元和逆元。 通俗来讲就是对于一个集合和一种运算构成的一个整体，满足： * 集合内的元素经过这个运算所得到的结果都在这个集合里（封闭性） * 类比于乘法运算的结合律，可以理解为运算满足无序性，即：$(a\cdot b)\cdot c= a\cdot(b\cdot c)$（结合律） * $\exists e\in S,\forall a\in S,a\cdot e=a$也就是说集合中存在一个数，使得所有的数经过运算都可以得到原来的数。 * $\forall a\in S,\exists b\in S,a\cdot b=e$ 那么就称 $b$ 为 $a$ 的逆元。 ### 置换和置换群 置换运算可以理解为映射，对于一个排列可以映射为另一种排列。 置换的乘法可以理解为复合函数，二次映射。 置换群就是运算为置换乘法的群。 ### Burnside引理 >每个置换的不动点个数的平均值就是不同的方案数 对于一个置换 $f$ ,若一个染色方案 $s$ 经过置换后不变，称 $s$ 为 $f$ 的不动点。将f的不动点数目记为 $C(f)$，则可以证明等价类数目为所有 $C(f)$ 的平均值。 ### Pólya 定理 假设一个置换有 $k$ 个循环，易知每个循环对应的所有位置颜色需一致，而任意两个循环之间选什么颜色互不影响。 因此，如果有 $m$ 种可选颜色，则该置换对应的不动点个数为 $m^k$。用其替换 burnside 引理中的 $C(f)$，即 $C(f)=m^k$ 令 $|F|$ 表示置换的数目，$k_i$ 表示第 $i$ 个置换包含的循环个数。 那么答案就是 $\dfrac{\sum\limits_{i=1}^{|F|}m^{k_i}}{|F|}$ ## 例题略解 ### [P4980 【模板】Pólya 定理](https://www.luogu.com.cn/problem/P4980) 真就是个板子题，由 **Pólya 定理** 定理可得： 方案数（也就是不动点数）为 $\dfrac{\sum\limits_{i=1}^{n}n^{\gcd(i,n)}}{n}$ 因为一共有 $n$ 种颜色，有 $n$ 个置换（以环的 $n$ 个位置为起点）每个置换的循环长度为 $\gcd(i,n)$ （由同余方程可得），因此就有 $\gcd(i,n)$ 个置换。 但是枚举 $1\sim n$ 显然会超时，因此我们枚举 $\gcd$ 通过 $\varphi$ 求出来最后的答案。 [$code$](https://www.luogu.com.cn/paste/rdr3vqas) ### [P1446 [HNOI2008]Cards](https://www.luogu.com.cn/problem/P1446) 果然 数论 与 DP 搭配是最妙的了。。。。 设 DP 数组 $f_{i,j,k}$ 表示 red 的有 $i$ 个，blue 的有 $j$ 个，green 有 $k$ 个。 然后计算当前序列的所有的环的长度，因为是置换，所以整个环的颜色都是相同的，做一个类似于背包的东西就好了。 注意这里原序列的顺序也算一种情况。 [$code$](https://www.luogu.com.cn/paste/htnw2wuv) ### [P4128 [SHOI2006] 有色图](https://www.luogu.com.cn/problem/P4128) 又是一道不同寻常的题，DFS+数论公式推导。 考虑将置换 $(a_1,a_2,a_3...a_n)$ 拆成若干个长度不等的置换 $(b_1,b_2,b_3...b_k)$ 的乘积的形式。 那么问题就变成了求这一系列置换的不动点，也就是边的等价类。 主要分为两种情况： 1. 端点在同一个循环中，那么此时对于两条边不在同一个等价类的条件就是长度不同，对于一个长度为 $b_i$ 的循环而言，两点之间不同长度的边一共有 $\lfloor\dfrac{b_i}{2}\rfloor$ 种。 2. 端点在两个循环之间，两个循环的共同的周期就是 $\operatorname{lcm}(b_i,b_j)$ ，然后不同等价类的个数就是$\dfrac{b_i\times b_j}{\operatorname{lcm}(b_i,b_j)}=\gcd(b_i,b_j)$ 综上所述，总的等价类个数就是 $\sum\limits_{i}\left\lfloor\frac{b_i}{2}\right\rfloor+\sum\limits_{i<j}\gcd(b_i,b_j)$ 考虑对于 1 到 $n$ 的每个点，分配它在第几个循环中。 这相当于一个多重组合数 $\dfrac{n!}{\prod b_i!}$。 而对于每一个置换，分配它内部的顺序，这相当于一个**圆排列**，即 $\prod(b_i−1)!$，结合前面是 $\dfrac{n!}{\prod b_i}$。 最后我们会发现这样其实会算重，因为每个循环的前后顺序不影响，比如不能把 1,2 和 2,1（这里表示每个点在第几个循环内）当作不同的循环分配方案。 发现只有 $b_i$ 相同的会影响，假设有 $c$ 个，正好多乘了 $c!$ 种方案，除掉就好了。这相当于$ \dfrac{n!}{\prod b_i\prod c!}$。 最终的答案就是： $$\displaystyle\sum_{b}\frac{1}{\prod b_i\prod c!}m^{\left[\sum_{i}\lfloor\frac{b_i}{2}\rfloor+\sum_{i<j}\gcd(b_i,b_j)\right]}$$ [$code$](https://www.luogu.com.cn/paste/r4nyuuw3) ### [P4570 [BJWC2011]元素](https://www.luogu.com.cn/problem/P4570) 大白板。 我们一定是选择贡献较大的优先加入，为什么这样是对的呢。 假如有 $c<a+b$ 并且 c 的加入会导致 a 和b 无法加入。 但是仔细思考后我们会发现，这样的情况 a 或者 b 任意一者的加入都会导致另外两个无法加入，因此上面的贪心是对的。 [$code$](https://www.luogu.com.cn/paste/n5angpov) ### [P4869 albus就是要第一个出场](https://www.luogu.com.cn/problem/P4869) 直接求每一个数肯定不行的，因此我们考虑先求出种类数，再根据种类数求出最后的答案。 假设我们线性基里成功插入了 $k$ 个数，那么剩下的 $n-k$ 个数字自由组合异或出来的数字就一定会在线性基中找到。 假设有一种合法的数字是 $x$ 假设随机组合出的数字异或出来是 $a$ 那么相对应的使得 $a\;xor\;b=x$ 的 $b$ 有且仅有一个。 毕竟我们的 $b$ 是可以通过 $a\;xor\;x$ 求出来的。 对于之前没有插入的数字的贡献也通过这种方式算进去了。 [$code$](https://www.luogu.com.cn/paste/4wj2daq5) ### [P3292 [SCOI2016]幸运数字](https://www.luogu.com.cn/problem/P3292) 本来是感觉自己的点分治学得不是特别牢固。 想搞一下别的算法，没想到把题解区某篇倍增的算法魔改成树链剖分之后就到 rk2 了，然后卡了一下常就 rk1 了（逃  大概是线性基上树的一个操作，从根节点开始建，然后对于之前已经有这一位的情况我们更新更大深度的。 每一次询问的话直接把一个节点的暴力插入到另一个节点中，然后直接求最大值就好了。 [$code$](https://www.luogu.com.cn/paste/wi2czic8)