题意
求长度为(n)，不存在(leftvert a_i-i
ightvert=k)的排列个数
(n le 2000)
传送门
思路
正着来并不是很好做，于是考虑反着做。
发现如果把限制条件连起来，会变成多条链
例如=考虑(n=7,k=2)会有这样(4)条链：
((1,
otoperatorname{3},5,
otoperatorname{7}))
((2,
otoperatorname{4},6))
((
otoperatorname{1},3,
otoperatorname{5},7))
((
otoperatorname{2},4,
otoperatorname{6}))
只要链前后的两个数连在一起，就会产生不合法的数对
容斥(f[i][j][0/1])表示在第(i)位，有(j)个数满足(leftvert a_i-i
ightvert=k)，当前数与前面的有没有连
对于单条的链，(dp)方程还是很显然的：
- 这个数与后面的连起来（必须保证前面和它没连）：(f[i][j][1]+=f[i-1][j-1][0])
- 不连：(f[i][j][0]+=f[i-1][j][1]+f[i-1][j][0])
那么考虑多条链怎么合并，其实就是链末端往后面连不会有贡献，所以就可以把所有链拼成一条链，(f[链末][j][1])是不可能存在的。只要刚开始做好标记，按照一条链的来做就完成了。
最后容斥即可。
#include <bits/stdc++.h>
const int mu=924844033;
int n,k,f[2][4005][2],cnt,p[2005],a[4005],now,ans;
int main(){
scanf("%d%d",&n,&k);
p[0]=1;
for(int i=1;i<=n;i++) p[i]=p[i-1]*1ll*i%mu;
for (int i=1;i<=k;i++){
a[cnt]=-1;
for(int j=i;j<=n;j+=k) cnt++;
a[cnt]=-1;
for(int j=i;j<=n;j+=k) cnt++;
}
now=1,f[now][0][0]=1;
for (int i=1;i<cnt;i++){
now=now^1;
memset(f[now],0,sizeof(f[now]));
for (int j=0;j<=i;j++){
f[now][j][0]=(f[now][j][0]+f[now^1][j][1]+f[now^1][j][0])%mu;
if (j && !a[i]) f[now][j][1]=(f[now][j][1]+f[now^1][j-1][0])%mu;
}
}
ans=p[n];
for (int i=1;i<=n;i++){
ans=(ans+(f[now][i][0]+f[now][i][1])*(i&1?-1:1)*1ll*p[n-i]%mu+mu)%mu;
}
printf("%d
",ans);
}
后记
想不到的神仙(dp)，好短啊。我好菜啊