题面
题解
将这个排列放到一个\(n\times n\)的棋盘上，那么一个排列问题可以转化为每行每列只填一个数的放置方法问题。
对于这题的限制，我们将一列不能放的位置涂黑，那么每一列就会有\(1\)至\(2\)个地方不能填（涂黑）。
考虑容斥这个东西，那么就是用至少\(i\)列涂黑格来容斥：
\[ Ans=\sum _{i=0}^n (-1)^i(n-i)!f_i \]
因为这里主要是\(f_i\)，也就是\(i\)列涂黑格的总方案数不好算，所以我们考虑怎么算这个\(f\)。
发现如果两个黑格在同一行或同一列他们就会冲突，我们将每一个点和与他同行、同列的点连起来，就会得到\(K+1\)条链，
而这\(K+1\)条链中相邻的点不能同时选，那么你把放置的方案数dp出来即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int Mod = 924844033;
const int MAX_N = 4e3 + 5;
int N = 4e3, K, fac[MAX_N];
int len[MAX_N], tot, cnt;
int f[MAX_N][MAX_N][2];
int main () {
fac[0] = 1; for (int i = 1; i <= N; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;
cin >> N >> K;
for (int i = 1; i <= N; i++) {
int l = i + K, r = i - K;
if (l <= N && r >= 1) len[l] = len[r] + 2, len[r] = 0;
else if (l <= N && l >= 1) len[l]++;
else if (r <= N && r >= 1) len[r]++;
}
for (int i = 1; i <= N; i++) cnt += len[i], tot += (len[i] + 1) / 2;
f[0][0][0] = 1;
for (int i = 1, cur = 0; i <= N; i++) {
for (int j = cur + 1; j <= cur + len[i]; j++) {
for (int k = 0; k <= tot; k++) {
f[j][k][0] = (f[j - 1][k][1] + f[j - 1][k][0]) % Mod;
if (k) f[j][k][1] = f[j - 1][k - 1][0];
if (j == cur + 1 && k) f[j][k][1] = (f[j - 1][k - 1][1] + f[j][k][1]) % Mod;
}
}
cur += len[i];
}
int ans = 0;
for (int i = 0, op = 1; i <= tot; i++, op = Mod - op) {
int res = (f[cnt][i][0] + f[cnt][i][1]) % Mod;
ans = (ans + 1ll * op * res % Mod * fac[N - i]) % Mod;
}
printf("%d\n", ans);
return 0;
}