发布于 ，更新于 

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);
}
许可协议

本文采用 GNU 自由文档许可证 许可协议，转载请注明出处。

分享文章