[AGC005D] ~K Perm Counting 题解
题目链接：[AGC005D] ~K Perm Counting
题意：
如果一个排列 $P$ 满足对于所有的 $i$ 都有 $|P_i-i|\neq k$，则称排列 $P$ 为合法的。
现给出 $n$ 和 $k$，求有多少种合法的排列。
由于答案很大，请输出答案对 $924844033$ 取模的结果。
数据范围：
$2\leq n\leq 2\times 10^3$，$1\leq k\leq n-1$。
如果我们把每个点不能放的位置画成一行，那么可以得到下图（$n=7,k=2$ ，图来自参考文献1）
图中阴影部分是不可以放的，并且每行每列都只能有一个格子被选中（可以认为是放 $n$ 个互不攻击的车）
正难则反，考虑容斥。设 $f_i$ 为钦定 $i$ 个阴影格子放车。答案为
那么 $f_i$ 怎么求呢？根据定义，$f_i$ 的选择要求车之间互不攻击。
如果我们把每个阴影格子与其不能同时选的格子连边，可以得到下图
那么 $f_i$ 就是这张图的独立集个数。注意到这张图由多条链构成。
考虑重新设 $f(i,j)$ 为前 $i$ 个位置，选了 $j$ 个点构成独立集的方案数，边界 $f(0,0)=1$ ，那么
这里 $a_{i-1}$ 表示 $i-1$ 和 $i$ 是否不相连，这个是可以线性求出来的。
时间复杂度 $\mathcal{O}(n^2)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 924844033;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
template<typename T> void add(T &x, T y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e3 + 15))
bool a[N * 2];
int n, m, fac[N], f[N * 2][N];;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m; fac[0] = 1;
rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
int t = 0; a[0] = true;
rep(i, 1, (n - m) % m)
{
a[t += (n - m) / m + 1] = true;
a[t += (n - m) / m + 1] = true;
}
rep(i, 1, m - (n - m) % m)
{
a[t += (n - m) / m] = true;
a[t += (n - m) / m] = true;
}
int res = 0; f[0][0] = 1;
rep(i, 1, t) rep(j, 0, n)
add(f[i][j] = f[i - 1][j], j ? f[i - 1 - (!a[i - 1])][j - 1] : 0);
rep(j, 0, n)
add(res, f[t][j] * fac[n - j] % mod * ((j & 1) ? mod - 1 : 1) % mod);
cout << res << '\n';
return 0;
}这道题还可以用多项式什么的 $\mathcal{O}(n\log n)$ ，这里不讲了（因为不会）
参考文献：
