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

ez_lcw · 2020-10-04 21:44:36 · 题解

首先正面做不太好做，考虑容斥。

设 f(m) 表示排列中至少有 m 处 |P_i-i|=k 的方案数。

那么答案就是 \sum\limits_{i=0}^n(-1)^if(i)。

原题可以看成一个二分图的形式：（n=5 时）

左边是排列的编号，右边是权值，那么现在要做的就是连 n 条边，补全这个二分图，使得每个点的度数都是 1。

那么考虑什么时候会出现 |P_i-i|=k 的情况。

如图，当 k=1 时，连出上图中的任意一条边都会使得 |P_i-i|=k。

我们考虑选出一些边，而且任意两条边都不能接在同一个端点上（因为每个点的度数要为 1）。

发现图中的边构成了若干条链且互不影响，于是把他们拿出来铺平：

此时如果要使得 |P_i-i|=k，只有相邻两个点之间才会连边，而且 a_5 和 1 （第 5 个点和第 6 个点）之间不会连边。

设 dp(i,j,01/0) 表示已经考虑了前 i 个点，其中连了 j 条边，第 i-1 个点和第 i 个点之间是/否连边的方案数。

那么容易得到：

但是还有一种特殊情况，那就是 i=6 时，第 5 个点和第 6 个点之间不能连边，所以此时 dp(i,j,1) 不存在。

所以我们需要开一个数组判断一下某一个点是否是链的开头。

按着这个 dp，那么有 f(m)=(n-m)!\times dp(2n,m)。

意思就是先把满足有 m 个 |P_i-i|=k 的方案数算出来，剩下的数随便排列。

代码如下：

#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;
}