题目描述
https://atcoder.jp/contests/agc005/tasks/agc005_d
简要题意：如果一个排列满足对于所有的 $i$，都有 $|P_i-i|\neq k$，则称排列 $P$ 合法，现在给定 $n$ 和 $k$，求有多少合法排列
$2\le n\le 2000,1\le k\le n - 1$
Solution
考虑容斥，我们令 $f_i$ 表示至少有 $i$ 个位置满足 $|P_i-i|=k$，$g_i$ 表示恰好有 $i$ 个位置满足 $|P_i-i|=k$，所求即为 $g_0=\sum_{i=0}^n(-1)^if_i$
我们考虑如何求 $f_i$，我们考虑原问题转化，考虑二分图左部点表示 $P$，右部点表示 $1$ 到 $n$，我们将左部点 $i$ 连向右部点 $i-k$ 和 $i+k$，容易发现，会影响的点是若干条链，根据组合数学经典式子，可以得到 $n$ 个点链，选择 $m$ 条互不相邻的边的方案数是 $\binom{n-m}{m}$，那么 $f_i$ 就是一个直接按照背包的做法合并即可
时间复杂度 $O(n^2)$，使用多项式快速幂可以做到 $O(n\log n)$
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
| #include <iostream>
#define maxn 2010
#define ll long long
using namespace std;
const int p = 924844033;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
ll fac[maxn], inv[maxn];
void init_C(int n) {
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
}
ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; }
int n, k;
ll f[maxn * 2][maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k; init_C(n); f[0][0] = 1;
for (int i = 1; i <= 2 * k; ++i) {
int t = (n - (i > k ? i - k : i) + k) / k;
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= min(j, t); ++k)
f[i][j] = (f[i][j] + f[i - 1][j - k] * C(t - k, k)) % p;
} ll ans = 0;
for (int i = 0, opt = 1; i <= n; ++i, opt = -opt)
ans = (ans + opt * fac[n - i] * f[2 * k][i]) % p;
cout << (ans + p) % p << "\n";
return 0;
}
|