题解：CF1954F Unique Strings
SegTree
·
·
题解
会了 Burnside Lemma 就是水题。
快进到枚举环的个数。我们要统计满足如下条件的串 S：
- 将 S 视作环时，最长 1 连续段长度至少为 \min(c,|S|)；
-
满足条件 $2$ 的串个数容易计算，考虑不满足条件 $1$ 且满足条件 $2$ 的串个数。然而环上仍然不好计算，因此我们可以枚举极长前缀 $1$ 和后缀 $1$。更近一步的，只需要枚举极长前缀 $1$ 和后缀 $1$ 长度之和，然后限制两个 $0$ 中间的串。
已经断环为链，考虑设计 dp 处理链上问题，令 $dp_{i,j}$ 表示已经填了前 $i$ 个字符，且第 $i$ 个字符为 $0$，用了 $j$ 个 $1$ 的方案数。转移可用差分优化至 $O(n^2)$。
至此，时间复杂度 $O(n^2)$。
<https://codeforces.com/contest/1954/submission/346763522>。