题解

思路

条件说明每个同色连续块长度恰为 $2$。因此一次涂色可以看成在相邻格子 $(k-1,k)$ 上放置一块颜色为 $c$ 的骨牌。颜色 $c$ 可放在这里当且仅当

$$L_c<k\le R_c.$$

两块骨牌不能重叠。如果两块骨牌首尾相接，它们还不能使用同一种颜色，否则会形成长度为 $4$ 的同色连续块。隔着至少一个空格时，同一种颜色可以再次使用。

做法

令 $S_k$ 表示只考虑前 $k$ 个格子的合法方案数，空方案计入其中；令 $dp_{k,c}$ 表示最右侧骨牌结束于 $k$ 且颜色为 $c$ 的方案数。

设

$$C_k=\{c\mid L_c<k\le R_c\}.$$

要在 $(k-1,k)$ 放颜色 $c$ 的骨牌，可以从前 $k-2$ 个格子的任意方案接上，但要排除恰好在 $k-2$ 结束、颜色也是 $c$ 的方案。因此

$$dp_{k,c}=\begin{cases} S_{k-2}-dp_{k-2,c},&c\in C_k,\\ 0,&c\notin C_k. \end{cases}$$

不在 $k$ 结束骨牌的方案有 $S_{k-1}$ 种，所以

$$S_k=S_{k-1}+\sum_{c\in C_k}dp_{k,c}.$$

初值为 $S_0=S_1=1$。直接枚举颜色的复杂度为 $O(NM)$。

3. 各部分分做法

子任务 1：状态搜索

当 $N,M\le8$ 时，从左到右搜索。每一步可以把当前格留空，或选择一个能覆盖当前两个格子的颜色放骨牌；若上一块骨牌与当前骨牌相邻，则禁止使用相同颜色。复杂度上界为 $O((M+1)^N)$，在本档范围内足够。

子任务 2 与 3：显式维护每种颜色

使用上面的基础 DP，对每个 $k$ 枚举全部 $M$ 种颜色，复杂度 $O(NM)$，空间复杂度 $O(M+N)$。它既能通过 $N,M\le2000$，也能通过 $M\le20$ 的大 $N$ 分支。

子任务 4：短区间转化为加权匹配

若 $R_i-L_i\le1$，每种颜色至多能放在一个位置，不会出现相邻骨牌重复使用同色的问题。令 $w_k=|C_k|$，则

$$S_k=S_{k-1}+w_kS_{k-2}.$$

用差分或直接统计每个长度为 $2$ 的颜色区间即可做到 $O(N+M)$。

子任务 5：两类结构分支

程序先判断属于哪一类结构。若区间两两不交，每个骨牌结束位置至多有一种可用颜色；记录当前位置的颜色，并分别维护奇数、偶数结束位置上一次的 $dp$ 值，即可线性计算。

若所有区间相同，所有颜色在同一时刻进入或离开 $C_k$，并且它们的 $dp$ 值始终相同。只需为奇偶位置各维护一个公共值 $x$，用 $M\cdot x$ 代替对颜色求和。

两类结构均为 $O(N+M)$，组合后可完整通过该档。

4. 满分做法：奇偶链上的整体仿射变换

$dp_{k,c}$ 只依赖 $dp_{k-2,c}$，所以奇数 $k$ 与偶数 $k$ 可以分成两条独立链处理。

对固定奇偶性，从上一个结束位置移动到当前 $k$ 时，仍然活跃的每个颜色值都执行同一个变换

$$x\leftarrow S_{k-2}-x.$$

这是形如 $x\mapsto ax+b$ 的仿射变换，其中 $a\in\{1,-1\}$。为每条奇偶链维护：

• 当前全局系数 sign 与常数 add，使颜色 $c$ 的真实值为 sign * base[c] + add；
• 活跃颜色数量 count；
• 所有活跃颜色真实值之和 sum。

整体执行 $x\leftarrow S_{k-2}-x$ 时，更新为

$$\begin{aligned} sign&\leftarrow-sign,\\ add&\leftarrow S_{k-2}-add,\\ sum&\leftarrow count\cdot S_{k-2}-sum. \end{aligned}$$

颜色 $c$ 对结束位置 $k$ 的有效区间是 $[L_c+1,R_c]$。把这个区间按奇偶性拆成至多两条连续事件链，预先记录进入和离开事件。每种颜色在每条链上只进入、离开各一次。

处理位置 $k$ 时依次：

1. 对该奇偶链的全部旧活跃值执行仿射变换；
2. 删除已经离开的颜色；
3. 加入新进入的颜色，其当前值为 $S_{k-2}$；
4. 令 $S_k=S_{k-1}+sum$。

加入颜色时，通过仿射变换的逆式求出它的 base；因为 sign 只可能是 $1$ 或 $-1$，其逆仍是自身。

正确性证明

由同色块长度必须为 $2$，任意合法方案都唯一对应若干互不重叠的带色骨牌，并且相邻骨牌颜色不同；反之这样的骨牌集合显然满足题目条件。

对结束于 $k$、颜色为 $c$ 的骨牌，删除最后一块骨牌后得到前 $k-2$ 个格子的方案。唯一不合法的前驱是其最右骨牌结束于 $k-2$ 且同为颜色 $c$，因此基础转移 $dp_{k,c}=S_{k-2}-dp_{k-2,c}$ 完全且不重不漏。再按最后一个格子是否结束骨牌划分，即得 $S_k$ 的转移。

满分算法只把同一奇偶链上所有颜色共同执行的转移合并为一次仿射更新，并用进入、离开事件精确维护集合 $C_k$；每个颜色的值与基础 DP 始终一致。因此每一步得到的 $S_k$ 与基础 DP 相同，最终输出 $S_N$ 正确。

复杂度

每个位置处理一次，每种颜色在两条奇偶链上至多各产生一次进入和离开事件，故时间复杂度为 $O(N+M)$，空间复杂度为 $O(N+M)$。