[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\) 个阴影格子放车。答案为 \[ \sum_{i=0}^n(-1)^if_i\cdot (n-i)! \] 那么 \(f_i\) 怎么求呢？根据定义，\(f_i\) 的选择要求车之间互不攻击。
如果我们把每个阴影格子与其不能同时选的格子连边，可以得到下图
那么 \(f_i\) 就是这张图的独立集个数。注意到这张图由多条链构成。
考虑重新设 \(f(i,j)\) 为前 \(i\) 个位置，选了 \(j\) 个点构成独立集的方案数，边界 \(f(0,0)=1\) ，那么 \[ f(i,0) = f(i-1,0) \\[6pt]f(i,j) = f(i-1,j) + f(i-1-[\lnot a_{i-1}],\, j-1)\quad (j > 0) \] 这里 \(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)\)
，这里不讲了（因为不会）
参考文献：
