题解

思路

一个二进制串由首字符和相邻位置是否发生变化唯一确定。处理到右端点 $r$ 时，只需记录最近一次变化发生在哪个相邻位置。

做法

令状态 $c\in[0,r-1]$ 表示前缀 $[1,r]$ 最近一次变化位于 $c,c+1$ 之间，$c=0$ 表示尚未变化。追加第 $r$ 位时，不变化会保留 $c$；发生变化会把新状态设为 $r-1$，其方案数是上一层全部状态之和。

对所有右端点为 $r$ 的约束：若 $a_{i,r}=1$，区间内不能有变化，故 $c<i$；若 $a_{i,r}=2$，区间内必须有变化，故 $c\ge i$。这些条件把合法状态限制为一个区间，清零区间外状态即可。首字符有两种选择，所以初始状态计数为二。

子任务一枚举所有 $2^n$ 个字符串。子任务二只有相等约束，用并查集合并必须相同的相邻位置，答案为二的连通块数次方。

复杂度

满分算法时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。