等价类计数(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中
热门文章
- day05-列表类型
- WWDC 2015 苹果发布会 笔记
- 2017-2018-2 20155333 《网络对抗技术》 Exp1 PC平台逆向破解
- LoRa---官方例程移植
- 【转载】VS中的路径宏 vc++中OutDir、ProjectDir、SolutionDir各种路径
- 定制 input[type=";radio";] 和 input[type=";checkbox";] 样式
- linux下如何解除被占用的端口号
- 算法(JAVA)----两道小小课后题
- EVA索赔系统JAVA拦截例外站点
- 关于Map迭代循环,key和value的顺序问题