题意:

询问有多少中1-n的排列使所有|a_i-i|!=k

分析:

我们思考一下,如果我们给所有匹配的点之间连上边,那么我们就得到了一个类似二分图的东西,然后我们反过来求,我们先求f_i表示我们找出的序列里面正好有i条边的方案数,然后我们再容斥一下就好了…
问题是怎么求f_i,我们假设我们把边连好以后得到了很多链,我们把这些了链方程一排,然后dp,dp[i][j][1/0]表示到了第i个点,然后前面一共取了j条边,然后1/0表示当前点取或者不取…
然后我们考虑转移,首先易得dp[i+1][j][0]=dp[i][j][1]+dp[i][j][0],然后我们考虑如果当前的点不是链的结尾,那么我们可以向下一个点连边,就有dp[i+1][j+1][1]=dp[i][j][0]
最后f_i就是dp[2 * n][i][1]+dp[2 * n][i][0]然后就是简单的容斥了…

代码:

#include<bits/stdc++.h>
 using namespace std;
#define LL long long
#define P pair<LL,LL>
 const LL inf = 0x3f3f3f3f;
 const LL mod = 924844033;
 const LL N = 4e3+10;
 template <typename tp> inline void read(tp &x)
{
    x=0;char c=getchar();int f=0;
    for(;c>'9'||c<'0';f|=(c=='-'),c=getchar());
    for(;c<='9'&&c>='0';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    if(f) x=-x;
}
int n,k,ans;
int vis[N][2],tot,en[N];
LL dp[N][N][2],f[N],fac[N];
signed main()
{
    read(n),read(k);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=1;j++)
            if(!vis[i][j])
            {
                for(int x=i,y=j;x<=n;x+=k,y^=1)
                    vis[x][y]=1,tot++;
                en[tot]=1;
            }
    en[0]=dp[0][0][0]=1;
    for(int i=0;i<2*n;i++)
        for(int j=0;j<=n;j++)
        {
            dp[i+1][j][0]=(dp[i][j][0]+dp[i][j][1])%mod;
            if(!en[i]) dp[i+1][j+1][1]=dp[i][j][0];
        }
    for(int i=0;i<=n;i++) f[i]=(dp[2*n][i][0]+dp[2*n][i][1])%mod;
    fac[0]=1;for(int i=1;i<=n;i++) fac[i]=(1ll*fac[i-1]*i)%mod;
    for(int i=0,j=1;i<=n;i++,j=-j)
        ans=((1ll*ans+1ll*j*fac[n-i]*f[i])%mod+mod)%mod;
    printf("%d\n",ans);
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注