题解：魔力环

一种暴力推式子做法。

思路

由于求循环同构等价类个数，所以容易想到使用 Burnside 引理进行求解。

Burnside 引理 部分

设 \(g_i\) 表示旋转 \(i\) 次。

假设要求 \(g_i\) 的不动点的个数，则从一个点向其将要到达的点连边会获得 \(\gcd(i, n)\) 个大小为 \(\frac{n}{gcd(i, n)}\) 的小环，这些环要求单个环内颜色相同，同时满足题目限制。

由于这些环内颜色相同，所以可以缩成一个大点，并且将 \(n, m\) 除以环的大小。

缩完之后考虑怎么满足题目的限制，由于每个环其实是由模 \(\gcd(i, n)\) 意义下的一个等价类，那么一个环拿出来一个元素作为代表的话，这些元素是构成一个环的。

设 \(f(n, m, k)\) 为 \(n\) 个点 \(m\) 个黑点，不能出现 \(k\) 个以上连续黑点的环的数量（不考虑循环同构）。

所以答案是：

\[\frac{1}{n}\sum_{i = 1}^{n}{f(\gcd(i, n), \frac{m \gcd(i, n)}{n}, k)} = \frac{1}{n}\sum_{i | n}{f(\frac{n}{i}, \frac{m}{i}, k)\varphi(i)} \]

后面的式子由前面的式子枚举 \(\frac{n}{\gcd(n, i)}\) 得到。

环上计数部分

现在的问题就是如何求出 \(f(n, m, k)\) 了。

由于要求的是对连续黑点大小的限制，那我们可以将每一段连续的相同颜色缩起来，这样就是黑白交替的了。

容易发现除了颜色全部相同之外（特判即可），其他的方案都使得缩完后的点数是偶数个。

那么可以去枚举有多少个黑色连通块，此时白色连通块数量与黑色一致，假设是 \(i\) 个。

先不考虑标号的问题，也不考虑谁黑谁白，并给每个联通块标号（其实就是每个连通块是不同的）。

那么白色连通块的总方案数为 \(\binom{n - m - 1}{i - 1}\)，这个可以通过插板法得到。

此时黑色连通块总方案数就不一样了，由于白色连通块方案数是直接统计 \(x_1 + x_2 + \cdots + x_i = n - m\) 的解数，但是黑色连通块还有一个限制是 \(x \leq k\)，这东西考虑容斥掉，枚举钦定有多少满足 \(x > k\) 的得到方案数为：

\[\sum_{j = 0}^{i}{(-1)^j \binom{m - jk - 1}{i - 1} \binom{i}{j}} \]

这个上界看着很难受，其实可以直接抬升到 \(n\) 的。

先获得一个比较劣的做法，回来考虑点有标号怎么办。

其实也挺好办的，直接绕着环赋值，然后将这个环一直转圈就好了，也就是给答案乘上 \(n\)，吗？

其实在枚举了 \(i\) 时做出的假设就导致了一个合法的状态，将所有的黑白连通块转两下仍然是合法的（转一下会导致黑白颠倒，算不同方案）。

此时发现当所有的点在转圈统计答案的时候，如果跳出了当前连通块，就等价于将所有的连通块反向转一次，所以这样就导致一个方案被统计了 \(i\) 次，所以需要将其除掉。

所以可得：

\[f(n, m, k) = n\sum_{i = 1}^{\frac{n}{2}}{\sum_{j = 0}^{n}{(-1)^j \binom{m - jk - 1}{i - 1} \binom{i}{j}} \binom{n - m - 1}{i - 1} \frac{1}{i}} \]

直接做有点太劣了，考虑优化（以下推式子用到了较多组合数性质，请谨慎观看）。