题解

思路

先把可达性转化为环上连续 1 段条件，再用 Burnside 引理统计循环等价类。三个子任务依次用直接枚举、逐周期有界组成 DP、统一短段预处理完成固定点计数。

1. 等价条件

一个结果串可由初始串得到，当且仅当它满足：

1. 1 的总数不超过 $c+k$；
2. 在环上至少存在连续 $c$ 个 1。

第二条保证把这段连续的 1 旋转到开头后，能够保留初始串的前 $c$ 个 1。因此问题等价于统计满足这两个条件的二进制项链。

2. 子任务 1：枚举所有二进制串

当 $n\le18$ 时，枚举全部 $2^n$ 个二进制串。检查 1 的数量和环上最长连续 1，再把所有循环移位中的字典序最小者作为等价类代表，插入集合即可。

时间复杂度为 $O(2^n n^2)$，空间复杂度为 $O(2^n n)$。

3. Burnside 引理

考虑旋转 $x$ 个位置，令 $g=\gcd(n,x)$，$q=n/g$。被该旋转保持不变的字符串由一个长度为 $g$ 的块重复 $q$ 次得到。

若基础块有 $w$ 个 1，原串就有 $qw$ 个 1，因此

$$w\le \left\lfloor\frac{c+k}{q}\right\rfloor.$$

设被这次旋转保持且满足条件的字符串数为 $F(g)$。答案为

$$\frac1n\sum_{x=0}^{n-1}F(\gcd(n,x)).$$

除法在模 $10^9+7$ 意义下用逆元完成。

4. 子任务 2：逐个周期做有界组成 DP

当 $g\le c$ 时，若周期串含有连续 $c$ 个 1，它只能是全 1，故 $F(g)=[c+k\ge n]$。

以下设 $g>c$。先用二项式系数求出基础块中 1 数不超过上界的全部方案，再减去环上所有 1 段长度都小于 $c$ 的坏方案。

若基础块有 $z$ 个 0、$w=g-z$ 个 1，从一个被标记的 0 出发，依次记录相邻两个 0 之间的 1 数，得到一个长度为 $z$、每项位于 $[0,c-1]$、总和为 $w$ 的有界组成。用普通背包 DP 求其数量。每个环形标号串有 $z$ 个可标记的 0，而标记位置有 $g$ 种，因此坏串数为

$$\frac gz\,[x^w](1+x+\cdots+x^{c-1})^z.$$

对所有 $g,w$ 分别做 DP 即可通过 $n\le60$。

5. 满分算法：统一预处理短 1 段

满分算法不再为每个 $g$ 重做 DP。定义

$$d[z][\ell]$$

为含 $z$ 个 0、总长度为 $\ell$，且每个 1 段长度都小于 $c$ 的线性结构数量。加入一个新 0 时，其后可接 $0$ 到 $c-1$ 个 1，用差分转移即可在 $O(1)$ 均摊时间完成：

$$d[z+1][\ell+1\ldots\ell+c]\mathrel{+}=d[z][\ell].$$

再对每一行建立前缀和。枚举环形串开头的 1 段长度 $p<c$，固定紧随其后的一个 0，余下部分便可由 $d$ 的区间和计数；同时约束末尾 1 段与开头拼接后仍短于 $c$。这样每个 $F(g)$ 可在线性时间内求出，全部预处理与统计总复杂度为 $O(n^2)$。

也可以用容斥式独立核验有界组成：

$$[x^w](1+x+\cdots+x^{c-1})^z =\sum_{j=0}^{\lfloor w/c\rfloor}(-1)^j\binom zj\binom{w-cj+z-1}{z-1}.$$

最终时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

6. 正确性要点

• 可达性等价于“1 总数不超过 $c+k$ 且环上存在长度至少 $c$ 的 1 段”。
• Burnside 引理把循环等价类计数转化为每个旋转的固定点计数。
• 固定点必为长度 $g$ 的基础块重复 $n/g$ 次，故总 1 数约束按重复次数缩放。
• 坏方案恰好是所有环形 1 段长度均小于 $c$ 的字符串；线性 DP 对它们无重无漏计数。
• 从全部固定点中减去坏方案并对旋转取平均，得到且仅得到所求等价类。

做法

预处理组合数、短 1 段 DP 及其行前缀和；枚举所有旋转的最大公因数 $g$，求该旋转的合法固定点数，累加后乘以 $n$ 的模逆元。

复杂度

满分算法时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。