题解：AT_abc431_f [ABC431F] Almost Sorted 2

· · 题解

比较巧妙的数数题。

思路

一般的有限制类数列计数都是从两种方向考虑，一种是从左往右逐一确定值，另一种是从小到大逐一确定位置。对于这道题来说，我们考虑第二种计数方式。

先假设 A 中元素没有重复的，并令其递增。设 f_i 表示将 A 的前 i 小重排后得到的满足条件的数列有多少个。考虑把 A_i 插入长为 i-1 的满足条件的数列中。显然如果长为 i-1 的数列不满足条件，则插入一个数一定不会使其变得满足条件，此时我们再来看一看限制：

B_{i+1}\ge B_i-D

由于排序后 A_i 肯定大于所有前面的数，所以我们不需要考虑 A_i 前面放的什么，只需要考虑 A_i 后面放的什么。显然能够放在 A_i 后面的数一定 \in[A_i-D,A_i]，或者干脆把 A_i 放到最后，于是我们双指针一下找到 A_i 前面有多少个这样的数，记为 x，则有：

f_i=f_{i-1}\cdot (x+1)

最后考虑去重，显然我们的算法区分了不同位置上的相同的数，对于一个出现了 k 次的数，我们对答案乘上 k!^{-1} 就结了。

时间复杂度 O(n\log n)。

Submission.