暴力建图,每次枚举起点 bfs,时间复杂度 $O(n^3m2^m)$,过不了。因为 add 操作会让图有 $O(n^2m2^m)$ 条边。
正难则反,考虑枚举终点倒过来走这个过程,这样之前 add 操作在倒过来的时候就是要从集合中删掉一个数,并跳到前面某个位置。设当前是 $S$,位于 $p$,删掉一个筛选条件 $x$ 之后的集合是 $T=S\setminus \{x\}$。如果当前执行一次 left 操作会到达 $p'$(不妨设 $p'< p$,另一种情况改一下就行了),那么就可以一直往前跳,每次跳到前一个能令集合 $T$ 合法的位置,直到跳到 $< p'+1$。因为 bfs 中每个点只关心第一次到达,所以当前跳到这个点之后,就不会再跳到这个点。开 $2^m$ 个并查集对每个 mask 维护第 $i$ 个位置要跳到的能满足限制 $\{(x,y)|x\in mask,y=a_{i,x}\}$ 且没有被跳到的位置即可,这样直接在 $T$ 对应的 mask 对应的并查集上往前跳,跳后就合并。这样 bfs 复杂度就是 $O(V)$ 而不是 $O(V+E)$,总复杂度 $O(n^2m2^m\log n)$。