常见的套路是考察一个序列合法的条件。首先显然是 $1,2,\dots,n$ 的一个子序列。

对于一个合法的子序列考虑拓展。如果结尾是 $i$，且 $i,i+1$ 之间是 + 那么可以在结尾加一个 $i+1$，如果 $i+1<j$，那么可以在结尾加一个 $j$ 当且仅当 $j$ 左侧/$i$ 右侧的运算符有一个是 | 且中间有 +。由于拓展的条件只和结尾以及下一个数有关，所以可以 DP，$dp_i$ 表示 $i$ 结尾的方案数，容易记几个量表示几个不同转移的 DP 值之和做到 $\mathcal{O}(n)$。