同步发表于博客园。

翻译：给定两个长度为 $N$ 的排列 $P,Q$ 和一个空数组 $R$，每次选择 $P,Q$ 中一个非空的数组，弹出左侧元素并将其加入 $R$ 的右侧，求这样能得到的不同的 $R$ 的数量，对 $10^9+7$ 取模。$N\le 2000$。

看起来就应该 dp。我们设 $dp_{i,j}$ 为 $P$ 的前 $i$ 位和 $Q$ 的前 $j$ 位能合并出多少个本质不同的数组。如果不需要去重，就有 $dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}=C(i+j,j)$。

然后考虑什么时候会算重。当 $P_{1\sim i}$ 和 $Q_{1\sim j}$ 有一个长度为 $k$ 的公共后缀时，从 $dp_{i-k,j-k}$ 到 $dp_{i,j}$ 的转移就会被算两次，因为两个序列是可以对调的。

但是如果直接这么写会发现还是多了。原因是只要 $LCS(P_{1\sim i},Q_{1\sim j})>1$，转移的时候就会有一条路径从 $dp_{i-k,j-k}$ 转移到 $dp_{i-l,j-l}$。

我们发现如果不出现这种情况，从 $dp_{i-k,j-k}$ 转移到 $dp_{i,j}$ 时的中间状态 $dp_{i-x,i-y}$ 一定同时满足 $xy$。发现这是一个明显的卡特兰数！所以我们得到了新的转移式：$dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}-\sum_{k=1}^{LCS(P_{1\sim i},Q_{1\sim j})}dp_{i-k,j-k}C_{k-1}$，其中 $C_x$ 是第 $x$ 个卡特兰数。

然后考虑时间复杂度。看上去这个东西是 $O(n^3)$ 的，但是由于 $P$ 和 $Q$ 都是排列，所以对于每个 $i$ 有且仅有一个 $j$ 满足 $LCS(P_{1\sim i},Q_{1\sim j})>0$，因此复杂度其实是 $O(n^2)$ 的。