思路很是巧妙呢
最开始不难想到这题应该是用容斥去做
设$g[i]$表示至少$i$个位置是冲突的方案数
那么答案就是
$$
\sum_{i=0}^n(-1)^i g[i] (n-i)!
$$
首先可以发现一个显然的性质，每个排列里的点最多只有两个点和它冲突(根据绝对值的性质
那么一个很妙的方法就是我们把和一个点冲突的点连边
这样就形成了一张图，这张图有一些很妙的性质
首先这是一张二分图，它的两个子集里都有$n$个节点
我们尝试画出这个二分图
以样例”3 1”为例
$(A_1,B_2)$
$(A_2,B_1)$
$(A_2,B_3)$
$(A_3,B_2)$
我们发现这张二分图里的一些边连接在一起就形成了一些链，现在我们把这些链提出来
下面这个样子
$A_1->B_2->A_3$
$B_1->A_2->B_3$
接着很显然可以看出这些链是互不影响的且每条链上只能选择一条边
那么我们可以对图进行重构,将它按$\mod k$的余数重新排列(因为只在$\mod k$相同的情况下存在连边
这样的话记录边就只用记录这个点和上个点有没有连边就行
接着开始$dp$
重构图之后一共有$n*2$个点
设$dp[i][j][0]$表示前$i$个点,选择了$j$条边,$i$和$i-1$有连边的方案数
$dp[i][j][1]$表示前$i$个点,选择了$j$条边,$i$和$i-1$没有连边的方案数
接着可以推出$dp$式子
$dp[i][j][0]=dp[i-1][j-1][0]+dp[i-1][j-1][1]$
$dp[i][j][1]=dp[i-1][j-1][0]$ 如果$i$和$i-1$有连边
注意不能选择相邻的两条边因为同一个位置只能有一个数值
那么$g[i]=dp[n*2][i][0]+dp[n*2][i][1]$
最后容斥即可
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 924844033
#define ll long long
#define N 2050
ll dp[N<<1][N][2],n,k,link[2*N],tot,sum,jc[N];
int main()
{
scanf("%lld%lld",&n,&k);
jc[0]=1;dp[0][0][0]=1;
for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%MOD;
for(int i=1;i<=k;i++)
for(int t=1;t<=2;t++)
for(int j=i;j<=n;j+=k)
j!=i?link[++tot]=1:++tot;
for(int i=1;i<=tot;i++)
for(int j=0;j<=n;j++)
{
dp[i][j][0]=(dp[i-1][j][1]+dp[i-1][j][0])%MOD;
if(link[i])dp[i][j][1]=dp[i-1][j-1][0];
}
for(int i=0;i<=n;i++)
{
ll tmp=(dp[n<<1][i][0]+dp[n<<1][i][1])%MOD;
tmp=tmp*jc[n-i]%MOD;
i%2==1?sum=((sum-tmp)%MOD+MOD)%MOD:sum=(sum+tmp)%MOD;
}
printf("%lld",sum);
return 0;
}
