发布于 ,更新于 

ABC309G Ban Permutation 题解

前置知识

  • 二项式反演(以后会补上笔记的!)
  • 状压 DP

符号约定

\(\lor\) 为逻辑或,相当于 C++ 中的 | 运算符。

题意简化

\(n\) 的排列 \(P\) 的方案数,要求 \(\lvert P_i - i \rvert \geqslant X\)

分析

排列问题有点抽象,于是有套路:把一个排列看成 \(n\times n\) 的棋盘上放车的方案——数字 \(p_i\)\(i\) 的位置上,相当于棋盘的 \((i,p_i)\) 位置放了一个车。显然 \(i,p_i\) 都不会重复,所以正确。

然后发现是个计数题,给出了不合法的条件,而且条件与位置相关,往二项式反演方向思考。

按照套路,设 \(g_i\) 为钦定 \(i\) 个数不合法,其他随便排的方案数,\(f_i\) 为恰好 \(i\) 个数不合法的方案数。发现每个 \(g_i\) 包含 \(f_j,j\in[i,n]\),然后每次选择不同的 \(i\) 个数进行钦定,所以一个 \(f_j\) 要算 \(\binom ji\) 次。于是有:

\[ g_i=\sum_{j=i}^n f_i \binom ji \]

脸上都写上二项式反演这五个字了,套一下式子,有:

\[ f_i = \sum_{j=i}^n(-1)^{j-i}\binom ji g_j \]

答案即为:

\[ \begin{aligned} ans &= f_0 \newline &= \sum_{j=0}^n(-1)^{j-0}\binom j0 g_j \newline &= \sum_{j=0}^n(-1)^j g_j \end{aligned} \]

考虑怎么求 \(g_i\)

回过头来看不合法的条件:\(\lvert P_i - i \rvert < X\),转化为 \(P_i\) 这个棋子不能放在 \([i-X+1,i+X-1]\) 这些横行上。

发现 \(X\leqslant 5\),非常小,也许可以状压?结合上面的转化,如果要状压的话,状态可以直接表示 \([i-X+1,i+X-1]\) 中不合法棋子的集合。

然后 DP 状态设计就有了(这里我们开出来一个新的 \(f\) 数组):\(f_{i,j,s}\) 表示棋盘前 \(i\) 行,放了 \(j\) 个不合法棋子,状态为 \(s\) 的方案数量。

怎么转移?假设当前是 \(f_{i,j,s}\),然后分类讨论:

  • 不放新的不合法棋子。 发现这种情况下转移到 \(i+1\) 时,新状态就是 \(s\) 右移一位,即 \(2^{-1}s\)。 为了方便,我们设这个状态为 \(ns\),表示什么都不放时转移到 \(i+1\) 时的状态。 转移方程也就简单了:\(f_{i,j,ns} \gets (f_{i,j,ns}+f_{i,j,s})\)
  • 放新的不合法棋子。 可以枚举一下这个不合法棋子能放到的位置(就是 \([i-X+1,i+X-1]\) 区间的空位),直接转移即可。但是注意,当前要做的是向后转移,所以应当枚举的是 \(ns\) 这个状态的空位。假设 \(p\) 是一个空位,则有转移方程:\(f_{i,j,(ns\lor 2^p)} \gets (f_{i,j,(ns\lor 2^p)}+f_{i,j,s})\)

对于 \(g_i\),由于是钦定了 \(i\) 个位置不合法,其他位置随便排,所以我们对 \(f_{n,i,s}\) 枚举 \(s\) 求和之后,还要乘一个 \((n-i)!\) 满足“剩下位置随便排列”的要求。

按照前面 \(ans\) 的式子求和即可。

时间复杂度 \(\operatorname\Theta(4^Xn^2)\)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
use std::io;

fn valid(pos: usize, i: usize, n: usize, x: usize) -> bool {
((i + pos + 1 - x) <= n && (i + pos + 1 - x) > 0) as bool
}

fn main() {
const MD: usize = 998244353;
const N: usize = 205;
const ST: usize = 600;
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let mut s = input.trim().split(' ');

let n: usize = s.next().unwrap().parse().unwrap();
let x: usize = s.next().unwrap().parse().unwrap();

let mut f = [[[0; ST]; N]; N];

let mxst: usize = (1 << ((x << 1) - 2 + 1)) - 1; // 区间长度本来是 (x << 1) - 2,但是还要包含 i 本身,所以 + 1

f[0][0][0] = 1;
for i in 1..=n {
for j in 0..=i - 1 {
for s in 0..=mxst {
let ns: usize = s >> 1;
f[i][j][ns] = (f[i][j][ns] + f[i - 1][j][s]) % MD;
for p in 0..=(x << 1) - 2 {
if ((1 << p) & ns) == 0 && valid(p, i, n, x) {
f[i][j + 1][ns | (1 << p)] =
(f[i][j + 1][ns | (1 << p)] + f[i - 1][j][s]) % MD
}
}
}
}
}

let mut fact = [0; N];
fact[0] = 1;
for i in 1..=n {
fact[i] = fact[i - 1] * i % MD;
}

let mut ans: i64 = 0;
for i in 0..=n {
for s in 0..=mxst {
if i & 1 == 1 {
ans -= (f[n][i][s] * fact[n - i] % MD) as i64;
} else {
ans += (f[n][i][s] * fact[n - i] % MD) as i64;
}
ans %= MD as i64;
}
}
ans = (ans % MD as i64 + MD as i64) % MD as i64;
println!("{}", ans);
}