摘要:笛卡尔树dp

SP3734 PERIODNI - Periodni

题面

题目分析

首先可以发现这个不规则的图形可以用笛卡尔树来表示成树形结构.

首先取最低的矩形作为根,然后在左边找到最低的矩形作为左儿子,在右边找到最低的作为右儿子,取最值可以预处理出一个st表,递归地这样做下去就构出了一颗笛卡尔树,树上的每个节点代表图上一个矩形.

然后在这棵树上考使用树形dp,设f(i,j)表示i点的子树内放j个数的方案数,g(i,j)表示i点代表的矩形里什么都不放,j个数全放在子树里的方案数,设点表示的矩阵宽为b,高为a.

这样就可以得到转移:

$g[u][i]+=f[c[u][0]][j] \times f[c[u][1]][i-j] ~(0 \leq j \leq i)$

$f[u][i]+=g[u][j] \times C^a_{i-j} \times C^{b-j}_{i-j} \times (i-j)! ~(0 \leq j \leq i)$

第一个很好懂,因为左右子树互不影响,所以直接并起来即可.

第二个就是考虑在子树里放了j个,自己的矩形里放i-j个,因为数放在子树里,所以当前矩形的宽上只剩b-j个位置,高上全都可以放,让后乘上这i-j个的全排列即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cstdlib"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl maxn=510,maxa=1000010,mod=1e9+7;
lxl n,k,root;
lxl h[maxn],lg[maxn],st[maxn][11],c[maxn][2],a[maxn],b[maxn],f[maxn][maxn],g[maxn][maxn],fac[maxa],inv[maxa],inv2[maxa];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline lxl C(lxl a,lxl b)
{
if(a<b)return 0;
return fac[a]*inv2[a-b]%mod*inv2[b]%mod;
}
inline void GetST()
{
lg[0]=-1;
for(R int i(1);i<=n;lg[i]=lg[i>>1]+1,st[i][0]=i,++i);
for(R int j(1);j<=10;++j)
for(R int i(1);i+(1<<j)-1<=n;++i)
st[i][j]=h[st[i][j-1]]<=h[st[i+(1<<(j-1))][j-1]]?st[i][j-1]:st[i+(1<<(j-1))][j-1];
}
inline lxl query(lxl l,lxl r)
{
lxl t=lg[r-l+1];
return h[st[l][t]]<=h[st[r-(1<<t)+1][t]]?st[l][t]:st[r-(1<<t)+1][t];
}
lxl build(lxl l,lxl r)
{
if(l>r)return 0;
lxl mid=query(l,r);
c[mid][0]=build(l,mid-1),c[mid][1]=build(mid+1,r);
a[c[mid][0]]=h[c[mid][0]]-h[mid];
a[c[mid][1]]=h[c[mid][1]]-h[mid];
b[mid]=r-l+1;
return mid;
}
inline lxl get(lxl a,lxl b,lxl k)
{
if(a<k||b<k)return 0;
lxl res=fac[k]*C(a,k)%mod*C(b,k)%mod;
return res;
}
void dfs(lxl u)
{
f[u][0]=g[u][0]=1;
if(!u)return;
dfs(c[u][0]),dfs(c[u][1]);
for(R int i(1);i<=k;++i)
for(R int j(0);j<=i;++j)
g[u][i]=(g[u][i]+f[c[u][0]][j]*f[c[u][1]][i-j]%mod)%mod;
for(R int i(1);i<=k;++i)
for(R int j(0);j<=i;++j)
if(g[u][j])f[u][i]=(f[u][i]+(g[u][j]*get(a[u],b[u]-j,i-j)%mod))%mod;
}
int main(void)
{
fac[0]=inv[0]=inv2[0]=fac[1]=inv[1]=inv2[1]=1;
for(R int i(2);i<maxa;++i)
fac[i]=i*fac[i-1]%mod,inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod,inv2[i]=inv2[i-1]*inv[i]%mod;
n=read(),k=read();
for(R int i(1);i<=n;h[i]=read(),++i);
GetST();
root=build(1,n);a[root]=h[root];
dfs(root);
printf("%lld\n",f[root][k]);
return 0;
}