ABC309G 题解

EuphoricStar · 2023-07-11 20:19:22 · 题解

前置知识：[ARC132C] Almost Sorted

看 \ge X 不顺眼，怎么办呢！直接容斥！

钦定 j 个位置满足 |P_i - i| < X，其余任意，就转化成了 [ARC132C] Almost Sorted。

具体一点就是，你设 f_{i, j, S} 表示前 i 位有 j 个位置满足 |P_i - i| < X，然后 i - (X - 1) \sim i + (X - 1) 的覆盖情况为 S（状压），作用是你填 P_i 时知道哪些数已经被填过了。转移讨论是否钦定 |P_i - i| < X 即可，若钦定 |P_i - i| < X 还要枚举 P_i。注意一些边界的处理。

答案是 \sum\limits_{i = 0}^n \sum\limits_S f_{n, i, S} \times (-1)^i \times (n - i)!，(-1)^i 是容斥系数，还要乘 (n - i)! 是因为除这 i 个数以外的所有数可以随便排。

时间复杂度 O(n^2 4^{X} X)。

code