CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

=====莫比乌斯反演推导Burnside引理公式=====

====说在前面====

本文将会用莫比乌斯反演推导$Burnside$引理，其适用于形似于以下的问题：

给出一个长度为$n$的环，需要用$m$种颜色对其进行染色（染色可能有若干限制），请求出有多少本质不同的染色方案，其中我们认为两种染色方案本质相同，当且仅当两种染色方案在旋转后颜色可一一对应（注意此处仅为旋转，不包含翻转）。

====解题过程====

首先我们定义以下函数：

$ans_n$表示环的长度为$n$时的答案。

$f_i$表示长度为$i$的环在不考虑翻转变换的情况下有多少种染色方案。

$g_i$表示长度为$i$且最小循环节为$i$的环在不考虑翻转变换的情况下有多少种染色方案。

根据以上定义，我们可以轻松得出它们之间有以下关系：

$$ans_n=\sum_{i|n}\frac{g_i}{i}=\frac{1}{n}\sum_{i|n}g_i\cdot\frac{n}{i}=\frac{1}{n}(g*id)(n)$$

$$f_i=\sum_{j|i}g_j⇒f=g*1⇒g=f*\mu$$

将第二个式子代入第一个式子可得：

$$ans_n=\frac{1}{n}(f*\mu*id)(n)=\frac{1}{n}(f*\phi)(n)$$

通常情况下由于$f$数组相较于$g$数组限制较少，可以在更快的时间内处理出来，而$\phi$数组可通过线性筛求得。

CVBB ACM Team

用户工具

站点工具

页面工具