题解：CF1186C Vus the Cossack and Strings

· · 题解

结论题。

要求 a 所有子区间与 b 的汉明距离为偶数的数量。

这里先给出结论：设 a 中 1 的个数为 x，b 中 1 的个数为 y，a 和 b 的汉明距离为偶数当且仅当 x \equiv y \pmod 2。

::::info[证明]{open}

不妨令 x > y，假设 y = y' + k，钦定 a 中有 y' 个 1 与 b 中的匹配，这一部分贡献为 0。

剩余部分的贡献为 x - y' + y -y' = x + y -2y'。可以证明出 x + y-2y' \equiv 0 \pmod 2。

上面的证明反之亦然，所以这是充要条件。

::::

然后直接算每个区间 1 的个数即可，时间复杂度 \Theta(n+m)。

代码很简单，不给了。