SPOJ3734 PERIODNI(笛卡尔树+组合+DP)
SPOJ3734 PERIODNI
洛谷题目传送门
给定一个N列的表格，每列的高度各不相同，但底部对齐，然后向表格中填入K个相同的数，填写时要求不能有两个数在同一列，或同一行，下图中b是错误的填写，a是正确的填写，因为两个a虽然在同一行，但它们中间的表格断开。
输出所有填写方案数对1 000 000 007的余数。
解题思路
这道题是加在笛卡尔树作业里的，那就是和笛卡尔树有关的
先考虑一种简化情况
如果是正方形，填n个数，那么第一行有n种，第二行有（n-1）种
一共有
n
!
n!
n!种填法
如果是矩形，长n，宽m，填k个
那么可以想成选k行，选k列，然后转化为情况一
方案数
C
n
k
C
m
k
k
!
C_n^kC_m^kk!
CnkCmkk!
现在考虑这个题
建出笛卡尔树，设
F
[
i
]
[
j
]
F[i][j]
F[i][j]表示在
i
i
i的子树中放置
j
j
j个数的方案数（不包含自己）
设
f
[
j
]
f[j]
f[j]表示在
i
i
i的子树中放
j
j
j个数的方案数（不包含自己）
f
[
i
]
=
∑
j
=
0
s
i
z
[
l
s
o
n
[
x
]
]
F
[
l
s
o
n
[
x
]
]
[
j
]
×
F
[
r
s
o
n
[
x
]
]
[
i
−
j
]
f[i]=\sum_{j=0}^{siz[lson[x]]}F[lson[x]][j]\times F[rson[x]][i-j]
f[i]=j=0∑siz[lson[x]]F[lson[x]][j]×F[rson[x]][i−j]
进而表示出
F
[
i
]
[
j
]
F[i][j]
F[i][j]
F
[
i
]
[
j
]
=
∑
k
=
0
H
f
[
j
−
k
]
×
C
H
k
×
C
W
−
(
j
−
k
)
k
×
k
!
F[i][j]=\sum_{k=0}^H f[j-k]\times C_H^k\times C_{W-(j-k)}^{k}\times k!
F[i][j]=k=0∑Hf[j−k]×CHk×CW−(j−k)k×k!
j
j
j是放置的总数，
k
k
k是在当前矩形放的数字
f
[
j
−
k
]
f[j-k]
f[j−k]表示在子树中（不含自己）放
j
−
k
j-k
j−k个数字
然后再下面的矩形中，高度是
H
H
H，宽度原本是
W
W
W，在子树中占据了
j
−
k
j-k
j−k
所以剩下了
W
−
(
j
−
k
)
W-(j-k)
W−(j−k)列，再转化为上面的矩形方案数
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod =1e9+7;
const int N = 720;
const int V = 1e6+7;
LL f[N][N];
int lson[N],rson[N];
int W[N];
int n,a[N];
stack<int> q;
int rot;
void build()
{
for(int i=1;i<=n;i++)
{
while(!q.empty()&&a[q.top()]>a[i])
{
lson[i]=q.top();
q.pop();
}
if(!q.empty()) rson[q.top()]=i;
q.push(i);
}
while(!q.empty())
{
rot=q.top();
q.pop();
}
}
LL add(LL a,LL b)
{
return (a+b)%mod;
}
LL mul(LL a,LL b)
{
return 1ll*a*b%mod;
}
LL Pow(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1) res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
LL Jc[V];
LL Ny[V];
void pre(int n)
{
Jc[0]=1;
for(int i=1;i<=n+1;i++)
Jc[i]=mul(Jc[i-1],i);
Ny[n+1]=Pow(Jc[n+1],mod-2)%mod;
for(int i=n;i>=1;i--)
Ny[i]=mul(Ny[i+1],i+1);
Ny[0]=1;
}
LL C(int n,int m)
{
if(n<m) return 0;
return mul(Jc[n],mul(Ny[m],Ny[n-m]));
}
LL dp[N];
int k;
void trans(int x,int h)
{
int H=a[x]-h;
W[x]=1;
if(lson[x]) trans(lson[x],a[x]);
if(rson[x]) trans(rson[x],a[x]);
W[x]=W[lson[x]]+W[rson[x]]+1;
memset(dp,0,sizeof(dp));
for(int i=0;i<=W[lson[x]];i++)
{
for(int j=0;j<=W[rson[x]];j++)
{
if(i+j>k) break;
dp[i+j]=add(dp[i+j],mul(f[lson[x]][i],f[rson[x]][j]));
}
}
for(int i=0;i<=W[x];i++)
{
for(int j=0;j<=H&&j<=i;j++)
{
if(i>k) break;
f[x][i]=add(f[x][i],mul(Jc[j],mul(dp[i-j],mul(C(H,j),C(W[x]-(i-j),j)))));
}
}
}
int main()
{
freopen("periodni.in","r",stdin);
freopen("periodni.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
pre(520);
build();
f[0][0]=1;
trans(rot,0);
cout<<f[rot][k];
return 0;
}