按列高建立笛卡尔树，转成树上问题......
笛卡尔树是什么？
它一般是针对序列建立的，是下标的BST和权值的堆(即中序遍历是原序列连续区间，节点权值满足堆性质)，这里不讲具体怎么建树(放在知识总结里了)。我们想一想对于一个序列建出来的树长啥样(灵魂画师上线辣)
也就是说树上一个节点对应原图上一个矩形区域，这样我们就把原序列转成了一个组合问题。设$dp[i][j]$表示以$i$为根的子树的区域里放了$j$个车的方案数，那么先是子树里的放法。呃，这不就是树形背包吗。。。转移不写了
然后考虑在自己的矩形里的放法，我们枚举放了$k$个车，那么$dp[i][j]$可以从$dp[i][j-k]$转移过来，过程是这$k$个车排列($k!$)+行上组合($h[i]-h[fa[i]]$里选$k$个)+列上组合($siz[i]-j+k$)
注意：上下两个转移都不要啥也不放就转移，这时候显然是假的=。=
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=550,M=1e6+60,mod=1e9+7; 6 int fac[M],inv[M],fth[N],son[N][2]; 7 int a[N],stk[N],siz[N],dp[N][N]; 8 int n,k,top,root; 9 void Add(int &x,int y) 10 { 11 x+=y; 12 if(x>=mod) x-=mod; 13 } 14 int Qpow(int x,int k) 15 { 16 if(k==1) return x; 17 int tmp=Qpow(x,k/2); 18 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 19 } 20 int C(int a,int b) 21 { 22 return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod; 23 } 24 void Pre() 25 { 26 fac[0]=inv[0]=1; 27 for(int i=1;i<=1000000;i++) fac[i]=1ll*fac[i-1]*i%mod; 28 inv[1000000]=Qpow(fac[1000000],mod-2); 29 for(int i=999999;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; 30 } 31 void DFS(int nde) 32 { 33 siz[nde]=dp[nde][0]=1; 34 for(int i=0,g;i<=1;i++) 35 if(g=son[nde][i]) 36 { 37 DFS(g); 38 for(int j=min(siz[nde],k);~j;j--) 39 for(int h=min(siz[g],k-j);h;h--) 40 Add(dp[nde][j+h],1ll*dp[nde][j]*dp[g][h]%mod); 41 siz[nde]+=siz[g]; 42 } 43 int col=a[nde]-a[fth[nde]]; 44 for(int i=min(siz[nde],k);~i;i--) 45 { 46 int tmp=0; 47 for(int j=min(i,col);j;j--) 48 Add(tmp,1ll*dp[nde][i-j]*fac[j]%mod*C(col,j)%mod*C(siz[nde]-i+j,j)%mod); 49 Add(dp[nde][i],tmp); 50 } 51 } 52 int main() 53 { 54 scanf("%d%d",&n,&k),Pre(); 55 for(int i=1;i<=n;i++) 56 scanf("%d",&a[i]); 57 for(int i=1;i<=n;i++) 58 { 59 while(top&&a[stk[top]]>a[i]) 60 { 61 int nde=stk[top]; top--; 62 if(top&&a[stk[top]]>a[i]) 63 son[stk[top]][1]=nde,fth[nde]=stk[top]; 64 else 65 son[i][0]=nde,fth[nde]=i; 66 } 67 stk[++top]=i; 68 } 69 while(top>1) 70 { 71 son[stk[top-1]][1]=stk[top]; 72 fth[stk[top]]=stk[top-1],top--; 73 } 74 // for(int i=1;i<=n;i++) printf("%d %d ",son[i][0],son[i][1]); 75 root=stk[1],DFS(root); 76 printf("%d",dp[root][k]); 77 return 0; 78 }