526互联

AtCoder Beginner Contest 309 G Ban Permutation

发布时间 2023-07-11 20:31:05作者: zltzlt

洛谷传送门

AtCoder 传送门

前置知识：[ARC132C] Almost Sorted

看 \(\ge X\) 不顺眼，怎么办呢！直接容斥！

钦定 \(j\) 个位置满足 \(|P_i - i| < X\)，其余任意，就转化成了 [ARC132C] Almost Sorted。

具体一点就是，你设 \(f_{i, j, S}\) 表示前 \(i\) 位有 \(j\) 个位置满足 \(|P_i - i| < X\)，然后 \(i - (X - 1) \sim i + (X - 1)\) 的覆盖情况为 \(S\)（状压），作用是你填 \(P_i\) 时知道哪些数已经被填过了。转移讨论是否钦定 \(|P_i - i| < X\) 即可，若钦定 \(|P_i - i| < X\) 还要枚举 \(P_i\)。注意一些边界的处理。

答案是 \(\sum\limits_{i = 0}^n \sum\limits_S f_{n, i, S} \times (-1)^i \times (n - i)!\)，\((-1)^i\) 是容斥系数，还要乘 \((n - i)!\) 是因为除这 \(i\) 个数以外的所有数可以随便排。

时间复杂度 \(O(n^2 4^{X} X)\)。

code 
// Problem: G - Ban Permutation
// Contest: AtCoder - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
// URL: https://atcoder.jp/contests/abc309/tasks/abc309_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 110;
const int mod = 998244353;

int n, m, f[maxn][maxn][maxn * 10];
ll fac[maxn];

inline void upd(int &x, int y) {
	x += y;
	(x >= mod) && (x -= mod);
}

void solve() {
	scanf("%d%d", &n, &m);
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	--m;
	f[0][0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			for (int S = 0; S < (1 << (m * 2 + 1)); ++S) {
				if (!f[i - 1][j][S]) {
					continue;
				}
				int T = (S >> 1);
				upd(f[i][j][T], f[i - 1][j][S]);
				for (int k = 0; k <= m * 2; ++k) {
					if ((~T) & (1 << k)) {
						if (i + k - m < 1 || i + k - m > n) {
							continue;
						}
						upd(f[i][j + 1][T | (1 << k)], f[i - 1][j][S]);
					}
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= n; ++i) {
		for (int S = 0; S < (1 << (m * 2 + 1)); ++S) {
			ll t = (i & 1) ? (mod - f[n][i][S]) : f[n][i][S];
			ans = (ans + t * fac[n - i] % mod) % mod;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}