[ABC309G] - Ban Permutation 题解
题目描述
求长为 \(N(N\leq 100)\) 且满足以下条件的排列 \(P=(P_1,P_2,...,P_N)\) 的个数，模 \(998244353\)：
- \(\forall 1\leq i\leq N\)，\(|P_i-i|\geq X(X\leq 5)\)。
思路
首先拆绝对值，得到：
\[P_i\ge X+i\vee P_i\le X- i \]数数题除了排列组合就是 DP，直接统计我不会，正难则反，看一下怎么从反面推出正面的答案。
假设有若干布尔变量 \(A_1\sim A_n\)，表示第 \(i\) 个位置是否是非法的，如果把 \(A_i\) 考虑为一个集合，由并集容斥得：
\[\bigcup_{i = 1}^n A_i = \sum A_i - \sum_{i\ne j}{A_i\cap A_j}+...(-1)^k\bigcap_{i = 1}^n A_i \]每一项的值分别表示至少一个不合法、至少两个不合法 ...... 至少 \(k\) 个不合法，最后用所有的情况 \(n!\) 减去所有非法情况的并即可求出答案。
推导上文不等式，得到不合法的位置满足：
\[P_i\in[X-i+1, X+i-1] \]这个区间长度为 \(2X-1\)，最多是 \(9\)，考虑状压 DP。
\(dp[i][j][s]\) 表示当前在第 \(i\) 个位置，至少有 \(j\) 个不合法位置，区间 \([X-i+1, X+i-1]\) 中的选取情况为 \(s\)。
可以分两种情况转移：第 \(j + 1\) 个位置是否合法。
从二进制低到高位分别对应下标从小到大比较好转移。
令
\[f_i = n!, i =0 \\ f_i = \sum_s dp[n][i][s] = \bigcap_{p_1<p_2<...<p_{t}<...<p_k}A_{p_{t}}, i > 0\\ \]答案为：
\[\sum_{i = 0}^n(-1)^k f_i (n - i)! \]// Problem: G - Ban Permutation
// Contest: AtCoder - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-08-10 00:08:16
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 110, M = 11, mod = 998244353;
int n, x;
ll dp[N][N][(1 << M)], f[N];
ll fac[N], ans;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> x;
dp[0][0][0] = 1;
int base = (1 << (2 * x - 1)) - 1, k = 0;
for(int i = 0; i < n; i ++)
for(int j = 0; j <= i; j ++)
for(int s = 0; s <= base; s ++) {
(dp[i + 1][j][s >> 1] += dp[i][j][s]) %= mod;
for(int t = max(1, i - x + 2); t <= min(n, i + x); t ++) {
k = t - (i - x + 2);
if(k < 0) continue;
if(!((s >> 1) & (1 << k)))
(dp[i + 1][j + 1][(s >> 1) ^ (1 << k)] += dp[i][j][s]) %= mod;
}
}
for(int i = 0; i <= n; i ++)
for(int s = 0; s <= base; s ++) f[i] = (f[i] + dp[n][i][s]) % mod;
fac[0] = 1;
for(int i = 1; i <= n; i ++) fac[i] = fac[i - 1] * i % mod;
for(int i = 0; i <= n; i ++) ans = (ans + (((i & 1) ? -1 : 1) * fac[n - i] + mod) % mod * f[i] % mod) % mod;
cout << ans << '\n';
return 0;
}