题目分析

建立出小根堆性质的笛卡尔树，于是每个节点可以代表一个矩形，其宽度为子树大小，高度为该节点记录的那一列高度-父节点那一列高度。

设 $f(x,i)$表示以 $x$为跟的子树中放了 $i$个棋子的方案数。

初始值：$f(0,0)=1$

首先求出不在 $x$的矩形中放棋子的方案数：$f(x,i)=\sum_{j=0}^i f(ls(x),j)f(rs(x),i-j)$

然后处理在 $x$的矩形中放棋子的方案数：$f(x,i)+=\sum_{j=1}^{i}C_{h_x-h_{fa(x)}}^jC_{sz(x)-(i-j)}^j j! f(x,i-j)$

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=1000000007,N=505,M=1000000;
int n,K,SZ,rt;
int h[N],sz[N],s[N][2],f[N][N],fac[M+5],inv[M+5],ifac[M+5];

int qm(int x) {return x>=mod?x-mod:x;}
int C(int d,int u) {return 1LL*fac[d]*ifac[u]%mod*ifac[d-u]%mod;}
void ins(int &x,int v) {
    if(!x) {x=++SZ,h[x]=v,sz[x]=1;return;}
    if(v>=h[x]) ins(s[x][1],v);
    else ++SZ,s[SZ][0]=x,x=SZ,h[x]=v;
    sz[x]=sz[s[x][0]]+sz[s[x][1]]+1;
}
void DP(int x,int las) {
    if(s[x][0]) DP(s[x][0],x);
    if(s[x][1]) DP(s[x][1],x);
    for(RI i=0;i<=sz[s[x][0]];++i)
        for(RI j=0;j<=sz[s[x][1]];++j)
            f[x][i+j]=qm(f[x][i+j]+1LL*f[s[x][0]][i]*f[s[x][1]][j]%mod);
    for(RI i=sz[x];i>=1;--i)
        for(RI j=1;j<=i&&j<=h[x]-h[las];++j)
            f[x][i]=qm(f[x][i]+1LL*C(h[x]-h[las],j)*
                C(sz[x]-i+j,j)%mod*fac[j]%mod*f[x][i-j]%mod);
}

int main()
{
    int x;
    scanf("%d%d",&n,&K);
    fac[0]=1;for(RI i=1;i<=M;++i) fac[i]=1LL*fac[i-1]*i%mod;
    inv[0]=inv[1]=1,ifac[0]=1;
    for(RI i=2;i<=M;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    for(RI i=1;i<=M;++i) ifac[i]=1LL*ifac[i-1]*inv[i]%mod;
    for(RI i=1;i<=n;++i) scanf("%d",&x),ins(rt,x);
    f[0][0]=1,DP(rt,0);
    printf("%d\n",f[rt][K]);
    return 0;
}