LOJ6519 魔力环(Burnside引理,容斥原理)
你需要给 $n$ 颗珠子的项链染 $m$ 颗黑色,$n-m$ 颗白色,不能有连续的一串黑色珠子长度超过 $k$,求旋转同构下本质不同的染色方案数.
$1\le m,k\le n\le10^5$
首先套用 Burnside 引理,以及位移为 $r$ 的旋转周期为 $\gcd(r, n)$ 的结论,得到答案的式子: $$ \begin{aligned} answer&=\frac 1 n\sum\limits_{i=1}^nf\left(\frac n{\gcd(i,n)}\right)\\ &=\frac 1 n\sum\limits_{d|n}\varphi(