Polya定理学习总结

2024-01-25 00:38
文章标签 学习 总结 定理 polya

本文主要是介绍Polya定理学习总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Burnside引理

设G是N={1,2,……,n}上的置换群,G在N上可引出不同的等价类,其中不同的等价类的个数为 1|G|gG c1(g),其中,c1(g)是置换g中不边缘的个数,即g中1阶循环的个数。

理解

后续补更……

polya定理

设G={a1,a2,a3,……,ag}是n个对象的置换群,用m种颜色给这n个对象染色,不同的着色方案为: 1|G|{mc(a1)+mc(a2)+...+mc(ag)} ,其中c(ai)为置换ai的循环节数(i=1····g)。

理解

后续补更……(话说已经挖了很多坑了……米亚内)

polya染色主要类型

问题模型:假如用 m 种颜色对具有 n 个珠子的项链进行染色,问最终项链有多少种不同的组成方式。

1、旋转相同忽略不计

(1)基本理解

题意要求忽略旋转后颜色组成相同的情况。
可以考虑在旋转情况下,共有旋转0个位置、旋转1个位置、旋转2个位置……旋转n-1个位置等n种转发。
先用一种情况进行讨论,假设我们现在计算旋转k个位置之后和原来染色相同的种类数,那么间距为k的两个位置的染色情况是相同的,即第 i 个位置与 (i+k)%n 个位置的染色相同 ,同样可得第 i 个位置与第 (i+k*t)%n 个位置的染色情况相同,而 t 即是在旋转k个位置的情况下一个珠子所能旋转的次数,则 t 需满足 k*t%n=0,为排除掉所有的相同情况,t需要取得最小值,很显然,t=n/gcd(k,n)。
对于旋转k个位置的情况下,则构成了 i —>(i+k)%n —> (i+2*k)%n —>··· —>i 这样一个轨迹,在这个轨迹中珠子的颜色必须是相同的,那么我们只需要得到在旋转 k 个位置的情况下有多少个互不相交的轨迹,就是在 k 的置换下循环节的个数。由已经推知每个轨迹中珠子的个数是 t=n/gcd(k,n),可得轨迹的个数就是 n/t=gcd(k,n) 了,即置换k下的循环节数,带入公式求解即可。

(2)优化

由(1)可得,在旋转 k 个位置下的循环节个数是 gcd(k,n),则最终结果可化为 1nnk=1mgcd(k,n) ,但是当 n 的数量级很大时,将无法在规定时间内依次枚举求解。但是我们可以通过把相同的gcd值合并起来进行一起计算。
假设我们现在要统计gcd(k,n)=d 的个数,显然 d 是 k 和 n 的约数,设 k=d*t(t即是我们所求的gcd(k,n)=d的个数),则 d=gcd(k,n)=gcd(d*t,n)=d*gcd(t,n/d)。所以gcd(t,n/d)=1,所以 t 的值即是与n/d互质的数,即欧拉函数 φ(n/d)。
由此原公式便可以转化为: 1nd|nmdφ(n/d)

对应题目

POJ 2154 Color

2、对称相同忽略不计

(1)在珠子个数是奇数的情况下,对称轴是一个珠子到圆心的连线,共有n条,对任一对称轴下的情况而言,对称轴上的一个珠子形成一个循环,其他的 n-1个珠子分别以对称轴对称形成(n-1)/2个循环,循环节的个数是 1+(n-1)/2=(n+1)/2;
(2)在珠子个数是偶数的情况下,对称轴有两种情况:
<1>对称轴是两个珠子的连线,共有n/2条对称轴,对任一对称轴而言,对称轴上的两个珠子分别形成一个循环,剩余n-2个珠子形成(n-2)/2个循环,则共有2+(n-2)/2 =(n+2)/2个循环节;
<2>对称轴是两个珠子中点与中心的连线,共有n/2条对称轴,关于对称轴对称的两个珠子形成一个循环节,共n/2个循环节。
对应带入公式即可。

对应题目

POJ 2409 Let it Bead

POJ 1286 Necklace of Beads

这篇关于Polya定理学习总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/641565

相关文章

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

Python中连接不同数据库的方法总结

《Python中连接不同数据库的方法总结》在数据驱动的现代应用开发中,Python凭借其丰富的库和强大的生态系统,成为连接各种数据库的理想编程语言,下面我们就来看看如何使用Python实现连接常用的几... 目录一、连接mysql数据库二、连接PostgreSQL数据库三、连接SQLite数据库四、连接Mo

Git提交代码详细流程及问题总结

《Git提交代码详细流程及问题总结》:本文主要介绍Git的三大分区,分别是工作区、暂存区和版本库,并详细描述了提交、推送、拉取代码和合并分支的流程,文中通过代码介绍的非常详解,需要的朋友可以参考下... 目录1.git 三大分区2.Git提交、推送、拉取代码、合并分支详细流程3.问题总结4.git push

Kubernetes常用命令大全近期总结

《Kubernetes常用命令大全近期总结》Kubernetes是用于大规模部署和管理这些容器的开源软件-在希腊语中,这个词还有“舵手”或“飞行员”的意思,使用Kubernetes(有时被称为“... 目录前言Kubernetes 的工作原理为什么要使用 Kubernetes?Kubernetes常用命令总

Python中实现进度条的多种方法总结

《Python中实现进度条的多种方法总结》在Python编程中,进度条是一个非常有用的功能,它能让用户直观地了解任务的进度,提升用户体验,本文将介绍几种在Python中实现进度条的常用方法,并通过代码... 目录一、简单的打印方式二、使用tqdm库三、使用alive-progress库四、使用progres