[ABC309G] Ban Permutation

· · 题解

/bx 龟神

题意

给定 n,x，求有多少排列 \{P_n\} 满足对于 \forall 1\le i\le n,|P_i-i|\ge x。

### 分析 你发现 $x$ 很小，小到可以状压；但是条件是大于等于，这很蠢，蠢到你想容斥。于是你考虑钦定若干个点违规，剩下随便去的方案数。 因为要考虑容斥系数，所以设计 $f_{i,j,s}$ 表示考虑到第 $i$ 个点，已经钦定了 $j$ 个，当前值域上 $[i-x+1,i+x-1]$ 有没有被选的状态为 $s$。转移直接考虑枚举当前点钦不钦定，如果钦定的话它的值选什么，转移就是 $\mathcal O(x)$ 的。 注意一下细节，$[i-x+1,i+x-1]$ 是可能超出 $[1,n]$ 的限定的，要判掉。 复杂度 $\mathcal O(n^22^{2x-1}x)$。 ### Code 提交记录：<https://atcoder.jp/contests/abc309/submissions/43416632>。