前言 今天大概学习了一下burnside引理，下面来小结一下。
参考资料 南京外国语学校 陈瑜希 的集训队论文 polya计数法的应用
基本概念 （由于作者懒，直接截图）
文章图片
置换群 顾名思义，就是一个元素都是置换的群。对于置换群，它的二元运算就是置换之间的连接，比如说
(13213244)?(14233241)=(12243341)( 1 2 3 4 3 1 2 4 ) ? ( 1 2 3 4 4 3 2 1 ) = ( 1 2 3 4 2 4 3 1 )
含义就是先经过第一个置换，在经过第二个置换，等价于经过第三个置换。
burnside引理 
文章图片
|G|| G | 表示置换群的大小。
看不懂没关系，我们先看一道例题。
例题
SGU294 He’s Circles 【burnside引理】题意：有一个长度为 NN 的环，上面写着’X’和’E’，问本质不同的环有多少种。 (N<=200000)( N <= 200000 ) 。
分析：这就是一道运用burnside引理的裸题。在本题中，共有 NN 种置换，分别表示环转 11 个位置、 22 个位置…… NN 个位置，那么现在对于每种置换，我们需要求出有多少种情况经过这种置换后依然保持不变。那么如何求解呢？假设 N=8N = 8 ，转了 22 个位置，那么每个位置的变化情况是： 1?>3?>5?>7?>1,2?>4?>6?>8?>21 ? > 3 ? > 5 ? > 7 ? > 1 , 2 ? > 4 ? > 6 ? > 8 ? > 2 ， x?>yx ? > y 表示原来 xx 位置上的到了 yy 位置，我把这样的一个东西叫做循环节。因为我们求的是不变的情况，所以同一个循环节中的位置上的字母应该是一样的，那么我们只需要知道循环节的个数 KK ，就可以知道对于这种置换不变的方案数为 2K2 K ，有一个比较显然的结论，当转了 ii 个位置时循环节的个数即为 gcd(i,N)g c d ( i , N ) ，所以，本题的答案即为 ∑ni=12gcd(i,N)N∑ i = 1 n 2 g c d ( i , N ) N 。
先写这么多。完结撒花！
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally