[AGC005D] ~K Perm Counting
智慧转化，但不是很难想到。首先考虑容斥，设\(f_i\)表示强制\(i\)个位置\(|P_i - i| = k\)的方案数，那么答案就为\(\sum_{i = 0}^n f_i(n - i)!\)，那么如何求\(f_i\)呢？
我们考虑位置之间的限制，可以将问题转化成一个\(n * n\)的矩形， 每行每列只能选一个位置，而有些位置不能选（标为灰色）。
那我们就相当于选不在同一行用一列的灰色节点，观察发现它们为几条链，链上相邻的不能选，这个问题就很经典了，最后做个背包就可以处理出\(f_i\)。
时间复杂度\(O(n^2)\)，可以用多项式乘法优化背包合并到\(O(n \log n)\)。
Code
#include<cstdio>
#include<iostream>
#define LL long long
#define IN inline
using namespace std;
const int P = 924844033, N = 2e3 + 5;
int n, K, cnt[N], lit; LL f[N][N], g[N][N], fac[N];
IN int read() {
int t = 0,res = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) t |= (ch == '-');
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return t ? -res : res;
}
int main() {
n = read(), K = read();
for (int i = 1, j = 1 - K; j <= K && i <= n; i++, j++) {
cnt[i] = (j <= 0 ? -1 : 0); int x = j, y = i;
for (int k = 1; x <= n && y <= n; k++)
cnt[i]++, x += (k & 1 ? (K << 1) : 0), y += (k & 1 ? 0 : (K << 1));
lit = i;
}
g[1][1] = g[1][0] = g[0][0] = 1;
for (int i = 2; i <= n; i++) {
g[i][0] = 1;
for (int j = 1; j <= i + 1 >> 1; j++) g[i][j] = (g[i - 1][j] + g[i - 2][j - 1]) % P;
}
f[0][0] = fac[0] = 1;
for (int i = 1; i <= lit; i++)
for (int j = 0; j <= cnt[i] + 1 >> 1; j++)
for (int k = j; k <= n; k++)
(f[i][k] += f[i - 1][k - j] * g[cnt[i]][j] % P) %= P;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * (LL)i % P;
LL ans = 0;
for (int i = 0; i <= n; i++) (ans += P + (i & 1 ? -1 : 1) * f[lit][i] * fac[n - i] % P) %= P;
printf("%lld\n", ans);
}