考虑给你 \(h\), 怎么整体得到最后的\(a\)
这里感觉不能去想让一个位置 \(x\) 留下来的冲要条件，不然可能就做不出来了。
自然的想法： 从 $2n $ 到 \(1\) 遍历每个\(h_i\), 然后从\(h_i\)到\(1\)找第一个没有标记的值\(x\), 此时\(i\)能留下来， 如果找不到\(x\)， 那么\(i\)无法留下来。
到这个地方其实已经可以 \(dp\) 做了， 很神奇。
\(dp\)的时候我们把两个相同的值看成不同的东西， 这样最后答案要除上\(2^n\)。
设\(f_{i, j}\) 表示考虑了倒着的 \(i\) 个， 然后\(1\)到 \(j\) 都已经被标记了， 而且 \(j + 1\) 没有被标记的方案数。
设\(c0\) 表示前 \(i - 1\) 个不要留下来的个数， \(c1\)表示前 \(i-1\)个要留下来的个数。
- 第\(i\)个点不能留下来， 那么贡献 f[i-1][j]*(j - c0)
- 第\(i\)个点能留下来，假设从 \(j'\)转移过来。
- \(j = j'\), 贡献以后再算, 直接加上 f[i-1][j']
- \(j \neq j'\), 第\(i\)个数有\(j - j' + 1\)种， 然后乘上\(c1-j'\)个贡献延迟计算的里面选出\(j - j' - 1\)个最后乘上这\(j - j' - 1\)个数的取值数量。 最后一个东西不是很好算， 考虑设这个东西为\(g_{j - j' - 1}\)
最后我们只需要求出\(g\)即可
计算\(g_i\), 考虑枚举最后一个数最后放在那个位置上设为\(j\), 那么这个数有\(i - j + 2\)种方案， 然后后面最后放在\(j\)后面的,和放在\(j\)前面的显然是独立的。 所以有
\[g_i = \sum_{j = 1}^{i} (i - j + 2) \times * C(i - 1, j - 1) * g_{j - 1} * g_{i -j}
\]