ABC309G Ban Permutation 题解
前置知识
符号约定
为逻辑或，相当于 C++ 中的 | 运算符。
题意简化
求 的排列 的方案数，要求 。
分析
排列问题有点抽象，于是有套路：把一个排列看成 的棋盘上放车的方案——数字 在 的位置上，相当于棋盘的 位置放了一个车。显然 都不会重复，所以正确。
然后发现是个计数题，给出了不合法的条件，而且条件与位置相关，往二项式反演方向思考。
按照套路，设 为钦定 个数不合法，其他随便排的方案数， 为恰好 个数不合法的方案数。发现每个 包含 ，然后每次选择不同的 个数进行钦定，所以一个 要算 次。于是有：
脸上都写上二项式反演这五个字了，套一下式子，有：
答案即为：
考虑怎么求 。
回过头来看不合法的条件：，转化为 这个棋子不能放在 这些横行上。
发现 ，非常小，也许可以状压？结合上面的转化，如果要状压的话，状态可以直接表示 中不合法棋子的集合。
然后 DP 状态设计就有了（这里我们开出来一个新的 数组）： 表示棋盘前 行，放了 个不合法棋子，状态为 的方案数量。
怎么转移？假设当前是 ，然后分类讨论：
- 不放新的不合法棋子。 发现这种情况下转移到 时，新状态就是 右移一位，即 。 为了方便，我们设这个状态为 ，表示什么都不放时转移到 时的状态。 转移方程也就简单了：
- 放新的不合法棋子。 可以枚举一下这个不合法棋子能放到的位置（就是 区间的空位），直接转移即可。但是注意，当前要做的是向后转移，所以应当枚举的是 这个状态的空位。假设 是一个空位，则有转移方程：。
对于 ，由于是钦定了 个位置不合法，其他位置随便排，所以我们对 枚举 求和之后，还要乘一个 满足“剩下位置随便排列”的要求。
按照前面 的式子求和即可。
时间复杂度 。
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;
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);
}
复制 |
