AGC012F Prefix Median

题意：给定一个长为 的序列 ，定义中位数序列 如下 ：

• 的中位数。

给出序列 ，可以将其任意打乱，问能产生多少个本质不同的 。

答案对 取模，，时限 。

---

AGC 的计数日常：这也能数？？？

• 先考虑 中没有重复元素的情况，即 。

先来考察怎样的 是可能被生成的。

生成 的方法可以理解为，先令 ，然后每插入两个 就将 重新设置为当前的中位数。

在求解 时，若插入的两个数字都比 大，则中位数会变为 的后继，若都比 小，则变为其前驱，一大一小则不变。

最终， 会等于整个 序列的中位数。

• 是 中 的前驱或后继，或等于 。

  等价于：对于任意的 都不满足 或 。

然而，某些时候并不能找出“两个比 大/小” 的数字。因此，无法总是做到向 前驱/后继 移动。

根据这个限制，可以发现 。

这两个条件配合在一起，正是 序列能被生成的充要条件。

• 充分性（简略）证明

  对于在 中没有出现的 中元素，记为集合 。

  构造时，若 ，则从 中拿出最小值 和最大值 。

  若 ，则加入 ，并从 中拿出最小值 。

  若 ，则加入 ，并从 中拿出最大值 。

  根据 这里能保证总是有 。

• 于是，我们将问题转化为：

  统计满足下列条件的 序列的个数。

  • （将序列 排序） 。

  • 对于任意的 都不满足 或

---

考虑 。

若按照 的顺序考虑，第二条限制将会难以处理。不妨以 的顺序考虑。

对于 ，他们对 产生的约束是：对于每一组 ，区间 （或区间 ）中不能再选择数。

（这些开区间的并集会形成一个中间有些断点的区间）

于是，记 表示考虑了 ， 左侧还剩 个数可选，右侧还剩 个数可选的方案数。

转移时，暴力枚举 即可。复杂度为 。

---

现在考虑 中有重复数的情况。若将它们按照出现顺序比较大小，序列的合法判据不变，但序列的等价判据改变。

因此， 要改成“去重后”还有 或 个数。