Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

题解 [SDOI 2013] 项链

posted on 2021-07-09 22:23:16 | under 组合数学 |

Decription

如题。

Analysis

设 $f(n)$ 表示用 $m$ 种颜色对长度为 $n$ 的环排列染色,相邻两个位置颜色不同的染色数。

则根据 Polya 定理,本题的答案可表示为$$\frac{1}{n}\sum_{d|n}f(d)\varphi\left(\frac{n}{d}\right)$$ 接下来考虑求 $f(n)$。

易知 $f(1)=0,f(2)=m(m-1)$,当 $n\ge 2$ 时,存在递推关系$$f(n)=(m-2)f(n-1)+(m-1)f(n-2)$$ 解出特征根方程的两个解为 $x_1=m-1,x_2=-1$。

令 $f(n)=c_1(m-1)^n+c_2(-1)^n$,将 $f(1),f(2)$ 的值代入可解得 $c_1=1,c_2=m-1$。

所以 $f(n)=(m-1)^n+(m-1)(-1)^n$。

唯一的问题就是计算不同的“颜色数”(即本质不同的珠子数)了。

手玩一下置换群可以发现,正三棱柱一共有 6 种置换,其中有 2 个轨道数为 1 的置换,3 个轨道数为 2 的置换,1 个轨道数为 3 的置换,我们仅需求出互质的 2 元组和 3 元组的个数即可,而这个可以莫比乌斯反演。

题目不难,主要是处理 4 个条件比较繁琐。