\(\text{Problem}:\)[AGC005D] ~K Perm Counting
\(\text{Solution}:\)
普通的错排问题，考虑容斥求解。
设 \(f_{i}\) 表示恰好有 \(i\) 个位置满足 \(\lvert P_{i}-i\rvert=k\)，\(g_{i}\) 表示钦定 \(i\) 个位置满足 \(\lvert P_{i}-i\rvert=k\)，有：
\[f_{i}=\sum\limits_{j=i}^{n}\binom{i}{j}(-1)^{j-i}g_{j}
\]
当 \(i=0\) 时，有 \(f_{0}=\sum\limits_{i=0}^{n}(-1)^{i}g_{i}\)。
转化 \(1\)：将 \(P_{i}\) 和 \(i\) 分开考虑，其限制关系构成一个二分图。求钦定 \(k\) 个匹配时的方案数。
转化 \(2\)：将 \(P_{i}\) 和 \(i\) 分开考虑，其限制关系对应前 \(i\) 个位置选了 \(j\) 组，求最后选择 \(k\) 组的方案数。
不难发现上面两种转化是等价的。考虑将连边关系展开，形成了总长和为 \(2n\) 的若干条链。现在变成在若干条链上选 \(k\) 个边，使得这 \(k\) 条边无交点。
设 \(f_{i,j,0/1}\) 表示前 \(i\) 个点选了 \(j\) 条边，\(i\) 位置是否为一条选择了的边的端点。总时间复杂度 \(O(n^2)\)。
\(\text{Code}:\)
#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=2010, Mod=924844033;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,K,f[N*2][N][2],book[N*2],cnt,vis[N*2],fac[N+5],ans;
signed main()
{
n=read(), K=read();
fac[0]=1;
for(ri int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%Mod;
for(ri int j=1;j<=n+n;j++)
{
int i;
if(j&1) i=(j+1)/2;
else i=j/2+n;
if(book[i]) continue;
int go=i;
while(!book[go])
{
book[go]=1, cnt++;
if(go<=n)
{
if(go+K>n) break;
else go=go+n+K;
}
else
{
if(go+K>n+n) break;
else go=go-n+K;
}
}
vis[cnt]=1;
}
f[0][0][0]=1;
for(ri int i=1;i<=n+n;i++)
{
for(ri int j=0;j<=n;j++)
{
if(!j) { f[i][j][0]=f[i-1][j][0]; continue; }
f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%Mod;
if(!vis[i]) f[i][j][1]=f[i-1][j-1][0];
}
}
for(ri int i=0;i<=n;i++)
{
int w=1ll*(f[n+n][i][0]+f[n+n][i][1])*fac[n-i]%Mod;
if(i&1) ans=(ans-w+Mod)%Mod;
else ans=(ans+w)%Mod;
}
printf("%d\n",ans);
return 0;
}