CF2154F sol

aaaaaaqqqqqq · 2025-10-21 21:08:11 · 题解

CF上把官解爆了的神奇做法。

F1

性质：除了排列 1, 2, \dots, n，其余排列最多找到一个 k， 使得这个集合可以被划分成题目所述的 Rifle Shuffle。

这个性质是比较显然的，因为但凡排列中存在逆序对，就意味着分割位置被唯一确定，可以自行思考。

我们按照题面，设分割点为 k，则我们将所有 p_i \le k 染成红色，其余染成蓝色。

容易注意到一个值为 x 的红色元素，它的左边必然恰好有 x - 1 个同色元素；对于蓝色元素，它的左边恰有 x - k - 1 个蓝色元素。

因为范围支持 O(n^2)，所以我们先枚举 k 然后从左往右 dp，对于每个已确定的元素计算它相比于上一个同色元素需要多填多少元素，一个组合数草上去就做完了。

F2

怎么有这么牛的爆标做法。赞美荷兰老哥。

注意到对于每个已经确定的元素 p_i = x ，若 p_i - x < 0 则 p_i 一定在小的集合；反之若 p_i - x > 0 则 p_i 一定在大的集合。只有 p_i = i 的时候我们没办法确定这货是哪边的。

• 我们先来考虑数列中全是 p_i = i 的情况。（但凡有一个 p_i \ne i，则所有的 p_i = i 也能够被确定在哪边，所以不用这样特别考虑。）

  对于分割点所在的前面一个 p_i = i，显然最后的集合会存在一段 1, 2, \dots, p_i 的前缀，否则不合法；对于后面一个也是一样的，存在一段后缀。因此我们只需要考虑每个区间内的分割方案。

  更进一步地，我们能发现对于 a_i = i, a_j = j (i < j)，夹在它们中间的 j - i - 1 个元素必然是 i + 1, \dots, j - 1 。自证不难。那么我们考虑若我们在这两个元素之间断开，中间这些东西怎么分。显然就是选一些位置分给左边，选一些位置分给右边，然后按一定顺序填数。

  对于中间有 m 个元素的 gap，方案数显然是 2^m 。然后对于单调上升的序列我们要特判，所以减去单调划分的方案数 m + 1。

• 然后考虑存在 p_i \ne i 的情况。

  如前文所述，只要存在一个 p_i \ne i 就必然能够确定所有的 p_i = i 的颜色。比较简单，不妨自己推理一下。

  我们考虑按所有确定的值将序列划分为若干段，对于每一段单独计算贡献。

  考虑 O(n^2) (?) 的递推怎么做。可以设计状态 f_{i, j} 表示红的现在放到了 i ，蓝的现在放到了 j 。每次转移相当于是下标偏移+权值乘上某个数。我们直接显式暴力维护初始的 O(n) 个状态，然后对于每段考虑。

  • 对于这段两端颜色相同的：

  我们可以直接得到这段里面两个颜色中间各需要加的个数（下标的偏移量以及下标取 max），以及最后走到了哪里（乘数）。注意到对于任何状态这些东西是一样的，不妨直接打 tag。

  • 对于这段两端颜色不同的：

  我们可以得到右边的那个颜色走到了哪里，但是转移的系数现在和左边那个颜色的数量有关了，我们不能直接打 tag。所以其实可以直接对于目前我们存储的状态暴力转移。

  为什么这样做的复杂度是对的呢？很容易注意到对于长度（中间不确定的个数）为 m 的区间，每次转移保留的有效状态只有 O(m) 个，即下一次处理的复杂度与这个区间的长度线性相关。所以整个复杂度事实上是 O(n + \sum m) = O(n) 的。

  最后枚举剩下来的每个状态即可。

  注意序列的两端需要额外添加两个哨兵节点，以处理最开始和最末尾一段未确定元素的贡献。