[Agc005D]K Perm Counting

2022-09-30 15:47:47

[Agc005D] K Perm Counting

Description

糟糕爷特别喜爱排列。他正在构造一个长度为N的排列。但是他特别讨厌正整数K。因此他认为一个排列很糟糕，当且仅当存在至少一个i（1≤i≤N），使得|ai-i|=K

他想知道，对于N!个排列，有多少个是不糟糕的？由于答案很大，他只想知道答案对924844033取模后的结果。

Input

第一行两个正整数N和K（2≤N≤2000，1≤K≤N-1）

Output

输出有多少个排列是不糟糕的（对924844033取模）

Sample Input

Sample Input 1

3 1

Sample Input 2

4 1

Sample Input 3

4 2

Sample Input 4

4 3

Sample Input 5

425 48

Sample Output

Sample Output 1

Sample Output 2

Sample Output 3

Sample Output 4

Sample Output 5

756765083

HINT

对于第一组样例，有2个排列 (1,2,3), (3,2,1) 是不糟糕的。对于第二组样例，有5个排列 (1,2,3,4), (1,4,3,2), (3,2,1,4), (3,4,1,2), (4,2,3,1) 是不糟糕的。本题采用subtask。存在10%的数据，满足n≤5；存在50%的数据，满足n≤300。

试题分析

我们发现一个数可否放在一个位置上只与这个数和位置有关，那么我们考虑哪些关系不能摆放，显然是：$$(pos_1)\rightarrow (num_{K+1}) \rightarrow (pos_{2K+1}) \ldots$$

然后我们会发现，这些2N个点组成了$(K-1)\times 2$条链，所以考虑去计算这些链。

我们显然不能选链上的边，但是剩下的情况又不好考虑，所以我们考虑容斥。

设$g_i$表示选链上至少i条边的情况数，那么最后$g_i=g_i\times (n-k)!$，然后普通容斥。

到这里，我们就可以设$f_{i,j,0/1}$表示前i个元素，选了j条边，当前边有没有选。

然后容斥一下，将所有连强行拼起来并且标记拼的那条边不可以选然后dp即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

#define LL long long

inline LL read(){

    LL x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const LL INF = 2147483600;

const LL MAXN = 2010;

const LL Mod = 924844033;

LL f[MAXN*2][MAXN*2][2];

LL g[MAXN*2]; LL N,K; bool fg[MAXN*2];

LL ans; LL cnt; LL fac[MAXN*2];

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    N=read(),K=read();

    for(LL i=1;i<=K;i++){

        for(LL j=i;j<=N;j+=K) fg[++cnt]=(j==i);

        for(LL j=i;j<=N;j+=K) fg[++cnt]=(j==i);

    }

    f[0][0][0]=1;

    for(LL i=0;i<2*N;i++){

        for(LL j=0;j<=i;j++){

            f[i+1][j][0]=(f[i][j][0]+f[i][j][1])%Mod;

            if(!fg[i+1]) f[i+1][j+1][1]=f[i][j][0];

        }

    } fac[0]=1;

    for(LL i=1;i<=N;i++) fac[i]=fac[i-1]*i%Mod;

    for(LL i=0;i<=N;i++){

        LL ret=(f[2*N][i][0]+f[2*N][i][1])%Mod;

        ans+=(i&1?-1:1)*ret*fac[N-i]%Mod; ans=(ans%Mod+Mod)%Mod;

    } printf("%lld\n",ans);

    return 0;

}

码农公寓