题解：CF1245F Daniel and Spring Cleaning

2huk · 2024-05-19 16:59:06 · 题解

观察到：

• 令 f(l, r) = \sum_{a=1}^l \sum_{b=1}^r [a \operatorname{and} b = 0]，那么答案为 f(r, r) - f(l - 1, r) - f(r, l - 1) + f(l - 1, l - 1)。

所以我们可以只求解 f(l, r)。显然设计数位 DP 状态 g(u, 0/1, 0/1) 表示考虑第 u 个二进制位且 a, b 是否填满。