题解：AT_abc431_f [ABC431F] Almost Sorted 2

· · 题解

ABC431F 题解

给出一个长度为 n 的序列 A 和一个整数 D，求满足序列 B 是序列 A 的排列且对于 1 \le i \le n-1 都有 B_{i} \le B_{i+1} + D 的序列 B 的数量，对 998244353 取模。

思考

先对 A 排序。

我们先考虑预处理对于每个 i 的 c_i，表示 A_{i} 的前一个数一定在 1 \le j \le c_i 对应的 A_j 中，即 c_i 就是最大满足 A_i + D \ge A_j 的下标 j。

容易发现 c_i 单调不降，可以用双指针求出，这一部分的时间复杂度为 O(n)。

之后再观察一下。不妨令 p 序列为 A 序列排列的下标，即 B_i = A_{p_i}。

我们猜测：如果一个 p 序列合法，那么当且仅当 c_{p_i} \ge i。

首先是必要性的证明。如果存在一个 i，使得 c_{p_i} \lt i 且这个 p 序列合法，那么由 c 序列的定义可知，一定有 p_{i-1} \le c_{p_i} \lt i,由于 c 序列不降且 p_{i-1} \lt i，则 c_{p_{i-1}} \le c_{p_{i}} \lt i