Solution ARC187C 1 Loop Bubble Sort

· · 题解

Solution ARC187C 1 Loop Bubble Sort

鲜花：这题赛后花两天时间才调出来。

题意

对于一个长度为 n 的排列 a，定义一次操作为依次对于 i\in[1,n)，若 a_i>a_{i+1} 则 swap 它们（即对于序列 a 执行单次冒泡排序的操作）。
现在给你一个序列 ans，其中钦定了一些位置。你要求出有多少个排列 a 使得对 a 进行单次操作后满足 a 和 ans 在钦定的这些位置相等。

先分析题目所说的单次冒泡排序的操作。我们发现假设处理到 a_i，其会跟随 swap 操作一直往后移到第一个大于 a_i 的位置前。即将 a 划分成若干个段，每个段的最大值均为这个段的第一个数，且每一段的第一个数依次递增。然后对于每个段循环向左移位。如下图：

考虑知道了 ans 如何倒着推出 a，此时变成了选出一些段，每个段的最大值必须在其末尾，且若从左往右对段编号，编号小的段的最大值小于编号大的段。每种划分 ans 的方案数都对应着一种合法的 a，我们只需对前者计数即可。

此时我们发现就变成了较为经典的 dp 形式，记 f_{i,j} 表示钦定 i 是当前段的最后一个元素，且值为 j 的方案数。那么它可以从 f_{k,l}\ (0\le k<i,0\le l<j) 转移过来，表示选了 (k,i] 这个段。

考虑朴素的 dp 方式，记 sum_i 表示值域在 [1,i] 内被钦定的数的个数，cnt_i 表示下标在 [1,i] 内未被钦定的个数。

式子略繁杂但是不难推，建议自己先去推一下。这里直接给出：

f_{i,j}=\sum_{k=0}^{i-1}\sum_{l=0}^{j-1}f_{k,l}\frac{(j-sum_j-[ans_i\neq j]-cnt_k)!}{(j-sum_j-cnt_i)!}

后面的代表乘上的排列数，[ans_i\neq j] 意思是如果最后一个是 -1 那么其值必须为 j，直接钦定了。

然后需要判掉 f_{i,j} 不合法的情况，细节较多。

考虑优化。首先发现 l 这维后面乘上的系数都一样，所以前缀和一下，记 g_k 表示当前的 \sum f_{k,l}，此时时间复杂度变成了 O(n^3)。

然后发现优化后的式子调换 i,j 的枚举顺序，仍然可以前缀和。f_{i,j} 涉及到的 g 的下标是一个区间，因为需要满足 (k,i] 这个区间的最大值不能超过 j 所以 k 不能过小。这个伴随 i 的增大是具有单调性的，所以可以双指针。

时间复杂度 O(n^2)，code