题解

令正面为 $1$，反面为 $0$。Arkady 的区间不能全为 $0$，Kirill 的区间不能全为 $1$。

思路

先用末尾同色段的起点建立逐位置动态规划，再把连续若干次相同的前缀和转移合并，从而处理 $k$ 很大的情形。

做法

子任务 1：枚举朝向

当 $k\le 22$ 时枚举全部 $2^k$ 个二进制串，逐一检查所有区间。复杂度为 $O(2^k(n+m))$。

子任务 2：逐位置动态规划

扫描到位置 $i$ 时，令

• $A_i$ 为右端点不超过 $i$ 的所有 Arkady 区间左端点最大值；
• $B_i$ 为右端点不超过 $i$ 的所有 Kirill 区间左端点最大值。

设 $f_0(i)$ 是长度为 $i$、以 $0$ 结尾的合法前缀数量，$f_1(i)$ 类似。若末尾的一段 $0$ 从 $j+1$ 开始，则前 $j$ 位必须以 $1$ 结尾，并且必须有 $j\ge A_i$。因此

$$f_0(i)=\sum_{j=A_i}^{i-1}f_1(j),\qquad f_1(i)=\sum_{j=B_i}^{i-1}f_0(j).$$

把空前缀作为两种虚拟末尾，令 $f_0(0)=f_1(0)=1$。用前缀和即可在 $O(1)$ 时间完成一次转移，总复杂度 $O(k+n+m)$。

子任务 3：坐标压缩

$k$ 很大，但限制只会在区间右端点变化。把 $0,k$、每个区间的 $l-1$ 和 $r$ 加入坐标集合。$l-1$ 必须保留，因为转移会查询那里对应的前缀和。

记

$$P_0(i)=\sum_{j=0}^{i}f_0(j),\qquad P_1(i)=\sum_{j=0}^{i}f_1(j).$$

在没有新右端点的连续区间内，$A_i=A,B_i=B$ 均不变。令

$$C_1=P_1(A-1),\qquad C_0=P_0(B-1),$$

其中 $A=0$ 或 $B=0$ 时相应常数取 $0$。一步转移为

$$\begin{pmatrix}P_0'\\P_1'\end{pmatrix} = \begin{pmatrix}1&1\\1&1\end{pmatrix} \begin{pmatrix}P_0\\P_1\end{pmatrix} - \begin{pmatrix}C_1\\C_0\end{pmatrix}.$$

设连续跨过 $d\ge1$ 个位置，$q=2^{d-1}$，$S=P_0+P_1$，$C=C_0+C_1$，则

$$P_0'=qS-(q-1)C-C_1,\qquad P_1'=qS-(q-1)C-C_0.$$

于是每段只需一次快速幂。到达某个坐标时，先跨过坐标之间的空白位置，再加入该坐标右端点带来的新限制，最后处理该位置。所有需要查询的 $A-1,B-1$ 都已在更早的压缩坐标处保存。

最终答案为 $f_0(k)+f_1(k)$。总复杂度为 $O((n+m)\log(n+m)+(n+m)\log k)$，空间复杂度为 $O(n+m)$。

复杂度

三个层级的复杂度分别为 $O(2^k(n+m))$、$O(k+n+m)$ 和 $O((n+m)\log(n+m)+(n+m)\log k)$；满分算法空间复杂度为 $O(n+m)$。

正确性要点

每个合法串的最后一个同色段有唯一的起点，所以两条转移既不遗漏也不重复。$A_i$ 与 $B_i$ 分别概括了扫描至 $i$ 时全部已经结束的照片要求；满足最大左端点就等价于满足同类所有要求。压缩转移只是把相同的一步线性递推合并，因此与逐位置动态规划完全等价。