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

Solution ARC187C 1 Loop Bubble Sort

文章操作

Solution ARC187C 1 Loop Bubble Sort

题意

相关推荐

评论

Solution ARC187C 1 Loop Bubble Sort