题目链接：AGC 005D

给出 $n$ 和 $k$，求有多少个长度为 $n$ 的排列 $a$ 使得对于任意的 $1 \le i \le n$，都满足 $|a_i - i| \ne k$。

数据范围：$2 \le n \le 2000$，$1 \le k < n$。

Solution

很显然本题正着做很麻烦，于是我们考虑容斥的方法。

记 $f(i)$ 表示至少有 $i$ 个位置不满足条件的方案数，则答案为

$$ \sum_{i = 0} ^ n (-1) ^ i \cdot f(i) $$

注意到对于每个数，与它的差的绝对值为 $k$ 的数不超过 $2$ 个，也就是说如果在 $x$ 和 $x + k$ 之间连边，那么会形成 $k$ 条链，每个点只能和与它有相连的边配对（如果要不满足条件，$x$ 要放在下标为 $x \pm k$ 的位置）。

考虑对每条链 $\text{DP}$，设 $f(i, j)$ 表示前 $i$ 个点选了 $j$ 个不满足条件的数的方案数。

但是注意到一点：每个数 $x$ 可以和 $x \pm k$ 配对，所以我们需要记录下当前点和下一个点是否被配对。

考虑对于每条链 $\text{DP}$，我们记 $f(i, j, p, q)$ 表示前 $i$ 个点选了 $j$ 个不满足条件的数，当前数字 $x$ 和下一个 $x + k$ 是否被选上的方案。

具体 $\text{DP}$ 转移详见代码（注意有些转移要求差为 $k$）。

时间复杂度：$\mathcal O(n ^ 2)$。

Code

#include <cstdio>

const int N = 2e3 + 5;
const int P = 924844033, INF = 0x3f3f3f3f;

int n, k, a[N], fac[N];
long long f[N][N][2][2];
bool vis[N];

void init() {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = 1LL * fac[i - 1] * i % P;
    }
}
int main() {
    scanf("%d%d", &n, &k);
    init();
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        for (int j = i; j <= n; j += k) {
            vis[j] = 1;
            a[++tot] = j;
        }
    }
    f[0][0][0][0] = 1;
    a[0] = -INF;
    for (int i = 1; i <= n; i++) {
        f[i][0][0][0] = 1;
        for (int j = 1; j <= i; j++) {
            f[i][j][0][0] = (f[i - 1][j][1][0] + f[i - 1][j][0][0] + (a[i] - a[i-1] == k) * f[i - 1][j - 1][0][0]) % P;
            f[i][j][1][0] = (f[i - 1][j][0][1] + f[i - 1][j][1][1] + (a[i] - a[i-1] == k) * f[i - 1][j - 1][0][1]) % P;
            f[i][j][0][1] = (a[i + 1] - a[i] == k) * (f[i - 1][j - 1][1][0] + f[i - 1][j - 1][0][0]) % P;
            f[i][j][1][1] = (a[i + 1] - a[i] == k) * (f[i - 1][j - 1][0][1] + f[i - 1][j - 1][1][1]) % P;
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        int sum = (f[n][i][0][0] + f[n][i][0][1] + f[n][i][1][0] + f[n][i][1][1]) % P;
        if (i & 1) sum = P - sum;
        ans += 1LL * sum * fac[n - i] % P;
        if (ans >= P) ans -= P;
    }
    printf("%d\n", ans);
    return 0;
}