题解

思路

从左到右决定 $A$。

做法

用一个集合 $S$ 表示下一项当前允许选择的数：起初所有 $1$ 到 $M$ 都可选。若本次选择 $a\in S$，那么在出现 $X_a$ 以前不能再次选 $a$，所以先从 $S$ 删除 $a$；另一方面，本次出现的 $a$ 已满足所有 $X_b=a$ 的等待条件，因此把这些 $b$ 全部重新加入 $S$。只要求相邻两次出现同一个 $b$ 之间含有 $X_b$ 就足以保证任意两次出现之间也满足条件，故这个状态完整描述了前缀。

用二进制掩码表示 $S$，预处理每个值 $a$ 对应的集合 $\{b\mid X_b=a\}$。令 dp[mask] 为当前前缀形成该允许集合的方案数，枚举 mask 中每个可选的 $a$，转移到 (mask 去掉 a) 并上 preimage[a]。完成 $N$ 次选择后把所有状态的方案数相加。

复杂度

时间复杂度为 $O(NM2^M)$，空间复杂度为 $O(2^M)$。