POJ2888 Magic Bracelet()

POJ2888 Magic Bracelet

Problem

用 \(m\) 种颜色串 \(n\) 个珠子,其中有 \(k\) 个限制,每个限制需要满足 \(a\) 颜色的珠子不能与 \(b\) 颜色的珠子相串。

\(1\le n\le 10^9,1\le m \le 10\)。

Solution

考虑 Burnside 引理,\(ans=\frac{1}{n}\sum\limits_{g\in G}|X^g|\)。

本题 \(G=\{e,e^2,e^3,…,e^n \}\),即转 \(1\) 圈到转 \(n\) 圈。

由于有限制,我们不能很直接地表示出答案。

记 \(F(k)\) 为循环节长为 \(k\) 的满足条件的方案数,则有:

\(ans=\frac{1}{n}\sum\limits_{k=1}^{n}F(\gcd(n,k))\)。

由数论基础知识推得:\(ans=\frac{1}{n}\sum\limits_{d|n}F(d)\varphi(\frac{n}{d})\)。

\(F(d)\) 可以矩阵快速幂求出,但要注意 \((n,1)\) “相邻” 的细节。

————————

POJ2888 Magic Bracelet

Problem

用 \(m\) 种颜色串 \(n\) 个珠子,其中有 \(k\) 个限制,每个限制需要满足 \(a\) 颜色的珠子不能与 \(b\) 颜色的珠子相串。

\(1\le n\le 10^9,1\le m \le 10\)。

Solution

考虑 Burnside 引理,\(ans=\frac{1}{n}\sum\limits_{g\in G}|X^g|\)。

本题 \(G=\{e,e^2,e^3,…,e^n \}\),即转 \(1\) 圈到转 \(n\) 圈。

由于有限制,我们不能很直接地表示出答案。

记 \(F(k)\) 为循环节长为 \(k\) 的满足条件的方案数,则有:

\(ans=\frac{1}{n}\sum\limits_{k=1}^{n}F(\gcd(n,k))\)。

由数论基础知识推得:\(ans=\frac{1}{n}\sum\limits_{d|n}F(d)\varphi(\frac{n}{d})\)。

\(F(d)\) 可以矩阵快速幂求出,但要注意 \((n,1)\) “相邻” 的细节。