20260923B 灯带 笔记

你怎么只做了一个题？？

给定长度为 $n$ 的环状串，每个位置为 0、1 或 ?，? 可任意填 0/1，求所有方案中 1 的连续段个数。

$n\le 2\times {10}^6$。

可以想到拆贡献，统计每个连续段出现的次数，于是就可以破环为链枚举 $l,r$，要求 $a_{l-1}=0,a_{r+1}=0,a_{[l,r]}=1$，那么 $[l,r]$ 全为 $1$ 出现的次数与剩下位置的问号有关，发现这是一个双重循环求和的形式，因此可以用数学方法 + 前缀和优化只枚举 $l$，开始写困难的代码。

这么写就死了，并且可以说往这里想之后再无想到正解可能，事实上并不用关心 $r$ 的情况，将每个连续段的贡献放到起点，变为统计连续的 $01$ 出现的次数。

所以以后遇到这种题可以多寻找方便计数的结构。