题解：AT_abc431_f [ABC431F] Almost Sorted 2

比较巧妙的数数题。

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

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

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

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

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