本文共 2071 字，大约阅读时间需要 6 分钟。

题目链接

题意简述

求长度为$n$的排列中$\forall i,|a_i-i|̸=k$的排列总数。

题解

假设满足$|a_i-i|=k$的位置的数量至少有$j$个的排列总数为$g_j$。那么答案就是

• 分别在二分图的两侧
• 假设编号为$i,j$，满足$|i-j|=k$

那么就连一条边。这张图上匹配为$i$的方法的总数就是$g_i$。

那么$g_i$？容易发现，这张图是由多条链构成的，将这几条链拼在一起，然后在钦定一些地方不能有匹配的边，这张二分图的匹配数量为$i$的方案数可以很方便的dp求出。

代码

#include 
   
    int read(){     int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {         if(ch=='-')        {             f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {         x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=2000;const int mod=924844033;int n,k,t,vis[maxn+10][2],a[maxn*2+10],f[maxn*2+10][maxn+10][2],g[maxn+10],ans,fac[maxn+10];int main(){     n=read();  k=read();  for(int i=1; i<=n; ++i)    {         for(int j=0; j<2; ++j)        {             if(!vis[i][j])            {                 int len=0;              for(int x=i,y=j; x<=n; x+=k,y^=1)                {                     vis[x][y]=1;                  ++len;                }              t+=len;              a[t+1]=1;            }        }    }  f[1][0][0]=1;  for(int i=2; i<=t; ++i)    {         f[i][0][0]=f[i-1][0][0]+f[i-1][0][1];      if(f[i][0][0]>=mod)        {             f[i][0][0]-=mod;        }      for(int j=1; j<=n; ++j)        {             f[i][j][0]=f[i-1][j][0]+f[i-1][j][1];          if(f[i][j][0]>=mod)            {                 f[i][j][0]-=mod;            }          if(!a[i])            {                 f[i][j][1]=f[i-1][j-1][0];            }        }    }  for(int i=0; i<=n; ++i)    {         g[i]=f[t][i][0]+f[t][i][1];      if(g[i]>=mod)        {             g[i]-=mod;        }    }  fac[0]=1;  for(int i=1; i<=n; ++i)    {         fac[i]=1ll*fac[i-1]*i%mod;    }  for(int i=0; i<=n; ++i)    {         ans=(ans+1ll*((i&1)?(mod-1):1)*g[i]%mod*fac[n-i])%mod;    }  printf("%d\n",ans);  return 0;}
   

转载地址：http://bcwo.baihongyu.com/