传送门

当1之前的$K-1$确定后,后面的$N-K$个数有$2^{N-K-1}$中排列方法(因为前$K$个数确定时队列也确定了,每次可以取队首或队尾,最后一个取两边都一样),所以就可以不用管1后面那些数了。

考虑1前面的那些数组成的序列,一个序列合法当且仅当这个序列能分成两个下降序列合在一起。由偏序集的Dilworth定理,我们知道这等价于这个序列的最长上升序列长度小于等于2。于是我们可以DP了,设$f_{i,j}$表示长度为$i$的排列中,有多少个排列的最长上升序列长度小于等于2,并且能在后$j$个数中的任意一个前面插入一个0后依然能满足性质。

考虑1前面的数,如果表示成2个下降序列$x,y$合在一起,则$y$只能等于$2$~$n$的数中去掉$x$后靠较大端的一段数。我们可以枚举$x,y$合在一起后靠最大端的连续段的长度(如果没有包含$n$,则长度为0),然后就可以根据上面的dp值,再乘一些组合数统计答案了。细节比较多,写的时候得注意一下。

#include <cstdio>
#include <cstring>
#define MAXN 4010
#define LL long long

const LL P=1000000007;

int n,k;
LL f[MAXN][MAXN],c[MAXN][MAXN],g[MAXN];

void update(LL &x,LL y){ x=(x+y)%P; }

void pre_gao(){
    for(int i=0;i<MAXN;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
    }
}

LL gay(int x,int y){
    return c[x+y-1][y];
}

LL gao(){
    f[1][1]=1;
    for(int i=2;i<=k;i++){
        for(int j=1;j<i;j++)
            update(f[i][j+1],f[i-1][j]);
        LL temp=0;
        for(int j=i-1;j>=1;j--){
            update(temp,f[i-1][j]);
            update(f[i][j],temp);
        }
        g[i-1]=temp;
    }
    g[0]=1;
    LL ans=g[k-1];
    for(int i=1;i<=k-1;i++){
        int j=k-1-i;
        if(n-2-j>=i){
            LL temp=c[n-2-j][i];
            if(!j) update(ans,temp);
            else{
                for(int l=1;l<=j;l++)
                    update(ans,temp*f[j][l]%P*gay(l+1,i));
            }
        }
    }
    for(int i=1;i<n-k;i++) ans=ans*2%P;
    return ans;
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d",&n,&k);
    pre_gao();
    printf("%lld\n",gao());
}