题解

思路

各二进制位互不影响，因此可以分别计算每一位的合法二进制串数，再把 $k$ 个结果相乘。

固定一位。若某个限制的该位为 $1$，区间内所有位置都被强制为 $1$；用差分数组标出这些位置。若该位为 $0$，区间 $[l,r]$ 内必须至少出现一个 $0$。

扫描到位置 $i$ 时，用“最后一个零的位置”描述前缀。对所有右端点不超过 $i$ 的零限制，最后一个零必须不小于相应左端点；只需维护这些左端点的最大值 $L$。

做法

令 $f_j$ 表示最后一个零恰在位置 $j$ 的前缀方案数，并额外用 $f_0=1$ 表示尚未出现零。若位置 $i$ 未被强制为 $1$，把它设为零的方案数等于上一步所有仍合法方案之和，因此产生新的 $f_i$。

处理完右端点为 $i$ 的限制后，只保留 $j\ge L$ 的状态。对 $f$ 维护前缀和，就能在 $O(1)$ 时间求出保留状态之和。每一位线性扫描一次。

子任务 1 可枚举每一位的全部 $2^n$ 个二进制串；子任务 2 可显式维护所有最后零位置并逐项求和。

复杂度

时间复杂度为 $O(k(n+m))$，空间复杂度为 $O(n+m)$。