当前位置: 首页 > news >正文

Plya 定理学习笔记 | ABC428G 题解

Pólya 定理学习笔记 | ABC428G 题解

用来对在若干置换下本质不同的方案数计数。


(这里会有一些证明,但是先咕掉((


首先是 Burnside 引理:

结论是,假设群 \(G\) 作用于集合 \(X\) 上。

\(O_x\) 表示 \(x\in X\) 的轨道,即 \(\{gx|g\in G\}\)

\(X_g\) 表示 \(g\in G\) 的所有不动点,即 \(\{x|x\in X,gx=x\}\)

Burnsize 引理指出:

\[|\{O_x|x\in X\}|=\dfrac 1{|G|}\sum_{g\in G}|X_g| \]


接下来是 Pólya 定理:

假设群 \(G\) 作用于 \(X\) 上,\(Y\) 是一个有限集,令 \(X^Y\) 是全体映射 \(X\rightarrow Y\) 构成的集合。

(可以认为 \(X\) 是元素,\(Y\) 是颜色, \(X^Y\) 表示所有的染色方案。

定义 \(c(g)\) 表示,取与 \(g\) 等价的置换 \(\sigma_g(x)=gx\),那么 \(c(x)\) 等于 \(\sigma_g\) 分解成的不相交轮换数量。

那么著名的 Pólya 定理断言:

\[|\{O_x|x\in X^Y\}|=\dfrac 1{|G|}\sum_{g\in G} |Y|^{c(g)} \]


例子:

\(n\) 种颜色给长为 \(n\) 的环染色,仅通过旋转重合的方案被认为相同,求本质不同方案数。

定义 \(Y=\{C_1,C_2,\cdots,C_n\}\) 表示所有的颜色。

\(X\) 表示环上的 \(n\) 个点表示的集合。

\(G=(\{\) 顺时针旋转 \(i\) 个单位 \(| 0\le i < n\},\)操作复合\()\)

由 Pólya 定理直接得出答案为:

\[\dfrac 1n \sum_{i=1}^nn^{\gcd(i,n)}=\dfrac 1n\sum_{d|n}n^d\varphi(\dfrac nd) \]


太厉害了!

还有点例题,后面再补((

http://www.hskmm.com/?act=detail&tid=37670

相关文章:

  • 第十八天
  • 第十七天
  • vue3+elementPlus el-date-picker 自定义禁用状态hook 建立结束时间不能小于开始时间
  • [优先队列] P3611 [USACO17JAN] Cow Dance Show S 题解
  • 搜维尔科技将携手Xsens|Haption|Tesollo|Manus亮相IROS 2025国际智能机器人与系统会议
  • 【做题记录】贪心--提高组
  • 如何炫酷地使用集合划分容斥
  • 简单云计算算法--20251023
  • 处理空输入踩的坑
  • latex输入公式
  • 【为美好CTF献上祝福】 New Star 2025 逆向笔记
  • XXL-JOB(5)
  • 蛋白表达原理与关键要素解析
  • Ramanujan Master Theorem
  • 顾雅南的声音美化课堂
  • C++案例 自定义数组
  • 【周记】2025.10.13~2025.10.19
  • 背包
  • 10.23《程序员修炼之道 从小工到专家》第二章 注重实效的途径 - GENGAR
  • 玩转单片机之智能车小露——LED闪烁实战
  • ord() 函数
  • 2025.10.23总结 - A
  • 大模型 | VLA 初识及在自动驾驶场景中的应用
  • ExPRT.AI如何预测下一个将被利用的漏洞
  • Redis中的分布式锁之SETNX底层实现
  • 攻击模拟
  • 2025家纺摄影公司推荐,南通鼎尚摄影专注产品视觉呈现
  • AI元人文构想的跨学科研究:技术实现与人文影响分析——对自由与责任的再框架化(DeepSeek基于Ai元人文系列文章研究)
  • Python---简易编程解决工作问题
  • 日总结 16