题目描述
即给出(n)个(1*h_i)的矩阵，在一条直线上对齐下表面，求放置(k)个互不攻击的车的方案数。
答案有可能很大，所以输出答案对(1000000007)取模。
Input
第(1)行包括两个正整数(N，K)，表示了棋盘的列数和放的车数。
第(2)行包含(N)个正整数，表示了棋盘每列的高度。
对于(100\%)的数据，有 (N≤500，K≤500，h[i] ≤1000000)。
Output
包括一个非负整数，表示有多少种放置的方案.
Sample Input
5 2
2 3 1 2 4
Sample Output
43
题意：即给出(n)个(1*h_i)的矩阵，在一条直线上对齐下表面，求放置(k)个互不攻击的车的方案数。
显然是先建出小根笛卡尔树，考虑每个矩形内部的答案。
不会笛卡尔树请转到笛卡尔树学习笔记
设 (dp[u][i]) 表示 (u) 子树内放 (i) 个数的方案数， (dp1[i]) 表示 当前子树(u)内不考虑当前矩形，放 (i) 个数的方案数，设(H[i])为当前矩阵可行高度（即(A[u]-A[fa[u]])）。
显然有 (dp1[] = f[ls]*f[rs])，即左右子树的卷积。
接下来就是背包的转移了，枚举当前矩形内有多少列还是空的进行转移。
设当前子树放置(i)个棋子，有(j)个在当前矩阵放置。
则(dp[u][i]+=sum_{j=0}^idp1[i-j]*C(Sz[u]-(i-j),j)*C(H[x],j)*j!)
第一个组合数是枚举矩阵所剩的行，第二个组合数是枚举矩阵所剩的列。
最后乘上 j! 是因为横纵坐标是两两组合的，因此匹配的方案数为 j!。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
#define Raed Read
#define clr(a,b) memset(a,b,sizeof a)
#define Mod(x) (x>=mod)&&(x-=mod)
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define debug2(x,y) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,G,x) for(int i=(G).Head[x]; i; i=(G).Nxt[i])
inline int Read(void) {
int res=0,f=1;
char c;
while(c=getchar(),c<48||c>57)if(c=='-')f=0;
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>=48&&c<=57);
return f?res:-res;
}
template<class T>inline bool Min(T &a, T const&b) {
return a>b?a=b,1:0;
}
template<class T>inline bool Max(T &a, T const&b) {
return a<b?a=b,1:0;
}
const int N=505,M=1e6+5,mod=1e9+7;
bool MOP1;
int Ans,n,K,stk[N],A[N],son[N][2];
int Fac[M],Inv[M],V[M];
int C(int a,int b) {
if(a<b)return 0;
return Fac[a]*(Inv[a-b]*Inv[b]%mod)%mod;
}
int Sz[N],dp1[N],dp[N][N],H[N];
void dfs(int x) {
Sz[x]=dp[x][0]=1;
rep(i,0,1)if(son[x][i]) {
int y=son[x][i];
dfs(y);
clr(dp1,0);
rep(j,0,min(Sz[y],K))rep(k,0,min(Sz[x],K))if(j+k<=K) {
dp1[j+k]+=dp[x][k]*dp[y][j]%mod,Mod(dp1[j+k]);
}
Sz[x]+=Sz[y];
rep(j,0,min(Sz[x],K))dp[x][j]=dp1[j];
}
rep(j,0,min(Sz[x],K))dp1[j]=dp[x][j];
rep(i,0,min(Sz[x],K)) {
int temp=0;
rep(j,0,i) {
temp+=dp1[i-j]*Fac[j]%mod*C(Sz[x]-(i-j),j)%mod*C(H[x],j)%mod;
Mod(temp);
}
dp[x][i]=temp;
}
}
bool MOP2;
void _main(void) {
Fac[0]=Inv[0]=Fac[1]=V[1]=Inv[1]=1;
ret(i,2,M) {
Fac[i]=Fac[i-1]*i%mod;
V[i]=(mod-mod/i)*V[mod%i]%mod;
Inv[i]=Inv[i-1]*V[i]%mod;
}
n=Read(),K=Read();
rep(i,1,n)A[i]=Read(),son[i][0]=son[i][1]=0;
int top=0;
rep(i,1,n) {
while(top&&A[stk[top]]>A[i])son[i][0]=stk[top--];
if(top)son[stk[top]][1]=i;
stk[++top]=i;
}
rep(i,0,1)rep(j,1,n)if(son[j][i])H[son[j][i]]=A[son[j][i]]-A[j];
H[stk[1]]=A[stk[1]];
dfs(stk[1]);
printf("%d
",dp[stk[1]][K]);
}
signed main() {
_main();
return 0;
}