【BZOJ2616】SPOJ PERIODNI
Description
Input
第1行包括两个正整数N，K，表示了棋盘的列数和放的车数。
第2行包含N个正整数，表示了棋盘每列的高度。
Output
包括一个非负整数，表示有多少种放置的方案，输出答案mod
1000000007后的结果即可。
Sample Input
5 2
2 3 1 2 4
2 3 1 2 4
Sample Output
43
HINT
对于100%的数据，有 N≤500，K≤500，h[i] ≤1000000。
题解：一看题就感觉应该是单调栈什么的。。。具体地说，是笛卡尔树。于是学了一发笛卡尔树的建树方法，感觉跟建虚树差不多。
我们用一个栈来维护笛卡尔树上当前的一条链（向右的链），然后对于第i个点，我们看一下它会被插入到链的哪个位置，这个位置下面的点都连接到i的左儿子处，然后将i入栈。
本题的笛卡尔树要满足每个父亲的高度都比儿子小。
然后考虑树形DP，我们将笛卡尔树上的每个节点看成原图的一个矩形，它的上界是它自己的深度，下界是它父亲的深度，左右边界是它的子树范围。用f[x][y]表示在x的子树中放y个车使其互不影响的方案数。我们只需要考虑x对应的矩形中放多少点以及如何放即可。
用一点组合知识便可得到转移方程，设矩形的长为n，宽为m，当前儿子是a，则：
$f[x][y]=\sum\limits_{b}{f[a][y-b]*f[x][b]}$
再乘上矩形中如何放：
$f[x][z]=\sum\limits_{y}f[x][z-y]*y!C_{n-z+y}^yC_m^y$
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll P=1000000007;
int n,m,tot,top,rt;
ll f[510][510],jc[1000010],ine[1000010],jcc[1000010],g[510];
int st[510],fa[510],v[510],ch[510][2];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
inline ll c(int a,int b)
{
if(a<b) return 0;
return jc[a]*jcc[a-b]%P*jcc[b]%P;
}
int dfs(int x)
{
int a=1,b=v[x]-v[fa[x]],i,j,k,y,aa;
f[x][0]=1;
for(i=0;i<=1;i++) if(ch[x][i])
{
y=ch[x][i],aa=dfs(y);
memset(g,0,sizeof(g));
for(j=0;j<=a;j++) for(k=0;k<=aa&&j+k<=m;k++) g[j+k]=(g[j+k]+f[x][j]*f[y][k])%P;
a+=aa;
for(j=0;j<=a;j++) f[x][j]=g[j];
}
for(i=min(m,a);i>=0;i--)
{
ll tmp=0;
for(j=0;j<=i;j++) tmp=(tmp+f[x][i-j]*jc[j]%P*c(a-i+j,j)%P*c(b,j)%P)%P;
f[x][i]=tmp;
}
return a;
}
int main()
{
n=rd(),m=rd();
int i,a;
for(i=1;i<=n;i++) v[i]=rd();
ine[0]=ine[1]=jc[0]=jc[1]=jcc[0]=jcc[1]=1;
for(i=2;i<=1000000;i++) jc[i]=jc[i-1]*i%P,ine[i]=(P-ine[P%i]*(P/i)%P)%P,jcc[i]=jcc[i-1]*ine[i]%P;
for(i=1;i<=n;i++)
{
while(top&&v[st[top]]>v[i])
{
a=st[top],top--;
if(top&&v[st[top]]>v[i]) ch[st[top]][1]=a,fa[a]=st[top];
else ch[i][0]=a,fa[a]=i;
}
st[++top]=i;
}
while(top>1) ch[st[top-1]][1]=st[top],fa[st[top]]=st[top-1],top--;
rt=st[1],dfs(rt);
printf("%lld",f[rt][m]);
return 0;
}