所有子串的贡献和（简单版）题解

思路

对固定模式 $p$，可以证明 $f(p)$ 等于覆盖所有 1 位置所需的最少长度不超过 3 的区间数。一次选择对应在 $q$ 中放置一个 1，它最多使连续三个位置中的 1 要求得到满足；反之，任何包含更远位置的众数区间都至少需要相应数量的 1，可以拆成这些局部覆盖而不增加数量。

于是从左到右扫描 $p$：找到第一个尚未覆盖的 1 后，用一次选择覆盖它和后面两个位置；继续寻找下一个尚未覆盖的 1。等价地，记录上一个触发选择的 1 的位置，当前 1 与它相距至少 3 时才增加答案。

做法

子任务 1 直接枚举每个子串对应的所有二进制串 $q$，再按定义枚举包含每个位置的区间，检验众数条件并取 1 数量最小值。

子任务 2 枚举子串左右端点，并对每个子串从头运行上述覆盖贪心。

完整做法固定左端点后逐步扩展右端点。维护最近一次触发选择的 1 位置和当前子串的 $f$ 值；每加入一个字符即可 $O(1)$ 更新，并立即累加贡献。

复杂度

子任务 1 的时间复杂度为 $O(n^5 2^n)$，空间复杂度为 $O(n)$。

子任务 2 的时间复杂度为 $O(n^3)$，空间复杂度为 $O(1)$。

完整做法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。