题目分析

考虑 $K=1$的情况。

设 $g(i,j)$表示由 $1$到 $i$组成的排列，有 $j$对形如 $(t,t+1)$的连续数对的，有多少个。

每次将 $i+1$加入进排列时，可以选择：

1. 加到 $i$后面，使 $g(i+1,j+1)+=g(i,j)$
2. 加到一对 $(t,t+1)$中间，使 $g(i+1,j-1)+=g(i,j)*j$
3. 加到其他位置上，$g(i+1,j)+=g(i,j)*(i-j-1)$

答案就是 $g(n,0)$。

接下来考虑 $K>1$的情况，可以将排列划成若干最大连续段，如 4 5 1 2 3 7 6 鸠可以划分为 4 5/1 2 3/7/6。

现在考虑有几个划分段，设 $f(i,j)$表示 $j$个数划 $i$段（每段都不长于 $K$）的方案数，则：

$f(i,j)=\sum_{t=1}^K f(i-1,j-t)$，可以用前缀和优化到 $O(n^2)$。

答案就是 $\sum_{i=1}^n f(i,n)g(i,0)$

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=1e9+7,N=5005;
int n,K,ans,f[N][N],sf[N][N],g[N][N],fac[N],ifac[N];

int qm(int x) {return x>=mod?x-mod:x;}
int qpow(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
int C(int d,int u) {
    if(d<u) return 0;
    return 1LL*fac[d]*ifac[u]%mod*ifac[d-u]%mod;
}
void work1() {
    f[0][0]=1;
    for(RI i=0;i<=n;++i) sf[0][i]=1;
    for(RI i=1;i<=n;++i) {
        f[i][0]=sf[i][0]=0;
        for(RI j=1;j<=n;++j) {
            f[i][j]=qm(sf[i-1][j-1]-(j-K-1<0?0:sf[i-1][j-K-1])+mod);
            sf[i][j]=qm(sf[i][j-1]+f[i][j]);
        }
    }
}
void work2() {
    g[1][0]=1;
    for(RI i=2;i<=n;++i)
        for(RI j=0;j<=i-1;++j) {
            if(!g[i-1][j]) continue;
            g[i][j+1]=qm(g[i][j+1]+g[i-1][j]);
            if(j) g[i][j-1]=qm(g[i][j-1]+1LL*g[i-1][j]*j%mod);
            g[i][j]=qm(g[i][j]+1LL*g[i-1][j]*(i-j-1)%mod);
        }
}

int main()
{
    scanf("%d%d",&n,&K);
    fac[0]=1;for(RI i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for(RI i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
    work1(),work2();
    for(RI i=1;i<=n;++i) ans=qm(ans+1LL*f[i][n]*g[i][0]%mod);
    printf("%d\n",ans);
    return 0;
}