等价类计数（Polya定理/Burnside引理）学习笔记
2024-08-24 21:06:45
参考：刘汝佳《算法竞赛入门经典训练指南》
感觉是非常远古的东西了，几乎从来没有看到过需要用这个的题，还是学一发以防翻车。
置换：排列的一一映射。置换乘法相当于函数复合。满足结合律，不满足交换律。
置换的循环分解：即将置换看成一张有向图，分解成若干循环。循环的数量称为循环节。
以置换集合来描述等价关系。如果存在一个置换将一个方案映射到另一个方案，则这两个方案等价。置换集合应当构成置换群。
不动点：方案s经过置换f不变，则s为f的不动点。
Burnside引理：等价类数量=所有置换的不动点数量的平均值。
Polya定理：对于某置换的不动点，显然每个循环内颜色相同，于是不动点数量即为颜色数循环节数。将其代入Burnside引理即得Polya定理。（为什么这是定理上面是引理啊）
没了。
最新文章
- Qt for Mac 安装(包括PyQt)
- Java中随机数的产生方式与原理
- rsync快速删除海量文件
- hdu 1251:统计难题（字典树，经典题）
- 【Cocos2d-x游戏开发】浅谈游戏中的坐标系
- 解决javax.imageio.IIOException: Can't create output stream!
- session处理超时的三种方式
- C 中数组和指针的区别
- 精妙SQL语句 基础
- protected访问修饰符
- js获取浮动(float)元素的style.left值为空的解决办法
- SQL-ROW_NUMBER() OVER函数的基本用法(源码案例)
- flex词法解析
- C#编写一款qq消息群发器
- Android几种视频播放方式，VideoView、SurfaceView+MediaPlayer、TextureView+MediaPlayer,以及主流视频播放器开源项目
- ansible的模块使用说明
- golang自定义struct字段标签
- PB程序调用C++ COM生成对象发回-2问题
- 【HDU5909】Tree Cutting（FWT）
- postman发送post数据到node.js中