2022-2023:teams:fire_and_blood:mobius_to_burnside
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:fire_and_blood:mobius_to_burnside [2022/07/29 15:41] bflstiger 创建 |
2022-2023:teams:fire_and_blood:mobius_to_burnside [2022/07/29 15:52] (当前版本) bflstiger [说在前面] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 本文将会用莫比乌斯反演推导$Burnside$引理，其适用于形似于以下的问题： | 本文将会用莫比乌斯反演推导$Burnside$引理，其适用于形似于以下的问题： | ||
| + | |||
| 给出一个长度为$n$的环，需要用$m$种颜色对其进行染色（染色可能有若干限制），请求出有多少本质不同的染色方案，其中我们认为两种染色方案本质相同，当且仅当两种染色方案在旋转后颜色可一一对应（注意此处仅为旋转，不包含翻转）。 | 给出一个长度为$n$的环，需要用$m$种颜色对其进行染色（染色可能有若干限制），请求出有多少本质不同的染色方案，其中我们认为两种染色方案本质相同，当且仅当两种染色方案在旋转后颜色可一一对应（注意此处仅为旋转，不包含翻转）。 | ||
| 行 18: | 行 19: | ||
| 根据以上定义，我们可以轻松得出它们之间有以下关系： | 根据以上定义，我们可以轻松得出它们之间有以下关系： | ||
| - | $$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$$ | + | $$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$$ | $$f_i=\sum_{j|i}g_j⇒f=g*1⇒g=f*\mu$$ | ||
| 行 24: | 行 25: | ||
| 将第二个式子代入第一个式子可得： | 将第二个式子代入第一个式子可得： | ||
| - | $$ans_n=\frac{1}{n}(f*\mu*id)_n=\frac{1}{n}(f*\phi)_n$$ | + | $$ans_n=\frac{1}{n}(f*\mu*id)(n)=\frac{1}{n}(f*\phi)(n)$$ |
| 通常情况下由于$f$数组相较于$g$数组限制较少，可以在更快的时间内处理出来，而$\phi$数组可通过线性筛求得。 | 通常情况下由于$f$数组相较于$g$数组限制较少，可以在更快的时间内处理出来，而$\phi$数组可通过线性筛求得。 | ||
2022-2023/teams/fire_and_blood/mobius_to_burnside.1659080510.txt.gz · 最后更改: 2022/07/29 15:41 由 bflstiger
