题解 AT2062 【[AGC005D] ~K Perm Counting】

ez_lcw

2020-10-04 21:44:36

Solution

首先正面做不太好做,考虑容斥。 设 $f(m)$ 表示排列中至少有 $m$ 处 $|P_i-i|=k$ 的方案数。 那么答案就是 $\sum\limits_{i=0}^n(-1)^if(i)$。 原题可以看成一个二分图的形式:($n=5$ 时) ![](https://cdn.luogu.com.cn/upload/image_hosting/opabe72v.png) 左边是排列的编号,右边是权值,那么现在要做的就是连 $n$ 条边,补全这个二分图,使得每个点的度数都是 $1$。 那么考虑什么时候会出现 $|P_i-i|=k$ 的情况。 ![](https://cdn.luogu.com.cn/upload/image_hosting/5s8onaw1.png) 如图,当 $k=1$ 时,连出上图中的任意一条边都会使得 $|P_i-i|=k$。 我们考虑选出一些边,而且任意两条边都不能接在同一个端点上(因为每个点的度数要为 $1$)。 发现图中的边构成了若干条链且互不影响,于是把他们拿出来铺平: ![](https://cdn.luogu.com.cn/upload/image_hosting/86viqgbi.png) 此时如果要使得 $|P_i-i|=k$,只有相邻两个点之间才会连边,而且 $a_5$ 和 $1$ (第 $5$ 个点和第 $6$ 个点)之间不会连边。 设 $dp(i,j,01/0)$ 表示已经考虑了前 $i$ 个点,其中连了 $j$ 条边,第 $i-1$ 个点和第 $i$ 个点之间是/否连边的方案数。 那么容易得到: $$ \begin{cases} dp(i,j,0)=dp(i-1,j,0)+dp(i-1,j,1)\\ dp(i,j,1)=dp(i-1,j-1,0) \end{cases} $$ 但是还有一种特殊情况,那就是 $i=6$ 时,第 $5$ 个点和第 $6$ 个点之间不能连边,所以此时 $dp(i,j,1)$ 不存在。 所以我们需要开一个数组判断一下某一个点是否是链的开头。 按着这个 dp,那么有 $f(m)=(n-m)!\times dp(2n,m)$。 意思就是先把满足有 $m$ 个 $|P_i-i|=k$ 的方案数算出来,剩下的数随便排列。 代码如下: ```cpp #include<bits/stdc++.h> #define N 2010 #define ll long long #define mod 924844033 using namespace std; int n,k,tot,a[N]; ll fac[N],dp[N<<1][N][2]; bool vis[N<<1]; int main() { scanf("%d%d",&n,&k); fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; for(int i=1;i<=k;i++) { for(int t=0;t<2;t++) { for(int j=i;j<=n;j+=k) { tot++; if(i!=j) vis[tot]=1; } } } dp[0][0][0]=1; for(int i=1;i<=(n<<1);i++) { for(int j=0;j<=n;j++) { dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%mod; if(vis[i]&&j) dp[i][j][1]=dp[i-1][j-1][0]; } } ll ans=0; for(int i=0;i<=n;i++) { if(i&1) ans=(ans-(dp[n<<1][i][0]+dp[n<<1][i][1])*fac[n-i]%mod+mod)%mod; else ans=(ans+(dp[n<<1][i][0]+dp[n<<1][i][1])*fac[n-i]%mod)%mod; } printf("%lld\n",ans); return 0; } ```