Press "Enter" to skip to content

置换群学习小结

置换群解决的是一类计数问题
在这些问题中存在着某种变换使得方案相同,置换群就是用来求其本质不同的方案数的。

置换

置换是一个有限的集合自身到自身的双射,本质上就是两个不同排列的变换
置换的乘法符合结合律所以有些题目可以通过快速幂来加速置换比如牛客5671J

置换群

集合S上的所有置换关于置换的乘法满足封闭性,结合性,存在单位元,存在逆元,所以构成群。这个群的任意一个子群就叫置换群

循环置换

任意置换都可以看作若干的不相交的循环群的相乘,在关系图上就表现出好几个圈。

Burnside引理

Burnside引理和下面的Polya本质上并没有什么不同

先上公式

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

$|G|$就代表的操作的数量,比如说旋转,翻转

$|X^g|$就是针对某一种操作$g$,在这种操作后不变的染色方案数

$|X/G|$就是要求的本质不同的方案的数量

Polya

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}\left|B\right|^{c(g)}$$

Burnside需要我们非常仔细的数相比,Polya定理提供了一种快速计算|Xg|的方法,我们只需要记录前后两个状态所形成的置换,然后通过计算循环串数量的方法来统计操作后不变的方案数。

参考资料

  1. Wiki-OI 置换群
  2. 《应用离散数学(第二版)》[方景龙,周丽 编著]

参考例题

HDOJ1812 Count the Tetris

题目链接

参考代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNextInt())
        {
            int n=scanner.nextInt();

            BigInteger c=scanner.nextBigInteger();
            BigInteger ans;
            if (n%2==0)
            {
                ans=c.pow(n*n);
                //90
                ans =ans.add(c.pow((n*n)/4).multiply(BigInteger.valueOf(2)));
                //180
                ans =ans.add(c.pow((n*n)/2));
                //翻转
                ans =ans.add(c.pow(n*n/2).multiply(BigInteger.valueOf(2)));
            }else {
                ans=c.pow(n*n);
                //90
                ans =ans.add(c.pow((n*n+3)/4).multiply(BigInteger.valueOf(2)));
                //180
                ans =ans.add(c.pow((n*n+1)/2));
                //翻转
                ans =ans.add(c.pow((n*n+n)/2).multiply(BigInteger.valueOf(2)));
            }
            //中心对称
            ans =ans.add(c.pow((n*n+n)/2).multiply(BigInteger.valueOf(2)));
            ans =ans.divide(BigInteger.valueOf(8));
            System.out.println(ans);
        }
    }
}

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点,欢迎评论。x
()
x