题解：AT_agc045_c [AGC045C] Range Set

不错的性质观察题。

先考虑判定。将过程反过来。本质等价于，对于目前串 $s$，选择一个长度 $\geq a$ 的不含 $1$ 的段，将段内的字符都变为 $\texttt{?}$，或者选择一个长度 $\geq b$ 的不含 $0$ 的段，将段内的字符都变为 $\texttt{?}$。问最终是否可能得到全 $\texttt{?}$ 的串。

注意到，$a,b$ 的地位对等。不妨假设 $a\leq b$。若存在一个长度 $=b$ 的全 $1$ 子段则立即判定为合法。进一步，将所有 $\geq a$ 的全 $0$ 段变为 $1$ 后，若存在一个长度 $=b$ 的全 $1$ 子段则判定为合法。不难说明这是充分必要的条件。

对于计数，考察问题的反面。不符合条件当且仅当将所有 $<a$ 的 $0$ 子段划分序列后每个段长度严格小于 $b$。至此已经不难 $O(n^2)$ DP 了。