膜 zzz 赛考了 F，先占个坑，剩下的等我做到这再补。
F - Prefix Median
给定长为 \(2n-1\) 的序列 \(a\)，你可以重新排列 \(a\)，设重拍后的排列为 \(c\)，然后构造一个新的序列 \(b\)，使得 \(b_1\) 是 \(\{c_1\}\) 的中位数，\(b_2\) 是 \(\{c_1,c_2,c_3\}\) 的中位数，以此类推 \(b_n\) 是 \(\{c_1,\dots ,c_{2n-1}\}\) 的中位数，求能够得到的本质不同的 \(b\) 序列的数量。\(n\leqslant 50\)。
不妨先把 \(a\) 排序，我们先需要发现两个性质：
- \(a_i\leqslant b_i\leqslant a_{2n-i}\)。
- 不存在 \(i<j\)，使得 \(b_j<b_i<b_{j+1}\) 或 \(b_{j+1}<b_i<b_j\)。
我们发现，每当我们向 \(c\) 中添加两个数，考虑 \(c\) 中位数的变化只可能有三种情况（假设我们现在正在填 \(c_{2i-1}\) 和 \(c_{2i}\)）：
- 这两个数都比 \(b_i\) 小，则 \(b_{i+1}\) 相较 \(b_i\) 在新的 \(c\) 中的排名减小了 \(1\)（我们认为相等的数之间可以任意比较大小）。
- 这两个数都比 \(b_i\) 大，则 \(b_{i+1}\) 的排名增加了 \(1\)。
- 这两个数一个比 \(b_i\) 小一个比 \(b_i\) 大，这样 \(b_{i+1}=b_i\)。
所以性质二就显然了（\(b_j+1\) 应该移动到 \(b_i\)），由于一定有 \(b_n=a_n\)，所以也可以推出性质一。
同时，我们有结论，满足上面两条性质的 \(b\) 序列一定可以由某个 \(c\) 生成得到，下面给出构造过程：
我们倒着考虑 \(b\) 的生成过程对其归纳，我们只需要确定 \(c_{2n-2}\) 和 \(c_{2n-1}\) 的值，然后我们就递归到了子问题。
- 若 \(b_{n-1}=a_{n-1}\)，考虑 \(a_{n-1},a_{n},\dots,a_{2n-1}\) 中一共有 \(n+1\) 个数，一定至少有两个数不在 \(b_1,b_2,\dots,b_{n-1}\) 中存在（如果多个数相等只要不全部选就可以，因为我们只需要保证在之后 \(b\) 中的每个数在 \(a\) 中至少出现过一次，所以有多个数相等并不影响构造），于是令 \(c_{2n-2},c_{2n-1}\) 为最小的这样的两个数。
- 若 \(b_{n-1}=a_{n+1}\)，类似上面的情况处理。
- 若 \(b_{n-1}=a_{n}\)，则 \(a_1,\dots,a_{n-1}\) 和 \(a_{n+1},\dots,a_{2n-1}\) 中一定各存在至少一个不在 \(b_1,\dots,b_{n-1}\) 中的数，分别令 \(c_{2n-2}\) 和 \(c_{2n-1}\) 为前半部分不在 \(b\) 中的最大的数和后半部分不在 \(b\) 中的最小的数。
然后我们把 \(c_{2n-2},c_{2n-1}\) 从 \(a\) 中删去，不难发现新的 \(b_n\) 也是删去这两个数后的 \(a\) 的中位数，所以依旧满足条件。
现在我们考虑 dp，由于靠后的 \(b\) 的限制是包含靠前的 \(b\) 的，我们考虑从后向前确定 \(b\)。
我们设 \(f(i+1,j,k)\) 表示我们现在确定了 \(b_{i+1},\dots,b_n\) 的值，正在确定 \(b_i\)，且当前候选集合（\(b_i\) 可以等于的数）中有 \(j\) 个不同的小于等于 \(b_{i+1}\) 的数，\(k\) 个不同的大于 \(b_{i+1}\) 的数。
首先由于第一条限制变松了，所以我们要把 \(a_i\) 和 \(a_{2n-i}\) 加入，然后我们考虑枚举 \(b_i\) 在候选集合中的排名，然后考虑在 \(b_i\) 和 \(b_{i+1}\) 之间的数都要被删去，则有转移：
- 若 \(b_i\leqslant b_{i+1}\)，设 \(id\) 表示把小于等于 \(b_{i+1}\) 的数排序后 \(b_i\) 的排名，则转移到 \(f(i-1,j-id+1+[a_i\not=a_{i-1}],k+[a_{2n-i}\not=a_{2n-i+1}]+[id>1])\)。注意三个 \([]\) 符号（我忘了它叫什么了 qaq），两个 \([a_i\not= a_{i-1}]\) 和 \([a_{2n-i}\not=a_{2n-i+1}]\) 是因为如果相等，则候选集合已经有过这个元素了，不能算上，\([id>1]\) 是因为如果 \(b_i<b_{i+1}\)，则 \(b_{i+1}\) 会进到候选集合中比 \(b_i\) 大的部分，而如果相等，则还在小于等于 \(b_i\) 的那部分。
- 若 \(b_i>b_{i+1}\)，类似的，转移到 \(f(i-1,j+[a_i\not=a_{i-1}]),k-id+[a_{2n-i}\not=a_{2n-i+1}])\) 注意有一些变化，因为 \(b_{i+1}\) 不在大于 \(b_{i+1}\) 的集合中。
所以总复杂度 \(O(n^4)\)。