题解 P6453 【[COCI2008-2009#4] F】

· · 题解

算是笛卡尔树的经典例题了，现在SPOJ好像把这题毙掉了，就在这里交吧。

题意

给定一个 n 列的表格，第 i 列的高度为 h_i。要求在这个表格中选出 k 个格子，满足没有两个格子在同一列或是联通的同一行。求这样选择的方案数

n,k\le 500 , \max\{h_i\} \le 10^6

题解

前置知识是笛卡尔树，这里，我们对序列 \{h_i\} 建立小根笛卡尔树。
我们每次尽可能地删去整张表格的最底行，直到当前情况下最低行已经不连通，用这些删掉的行组成一个矩形，再将分开的至多两个联通块递归处理，就可以将原图剖分成若干个矩形。

我们发现，这样构成的若干个矩形正好对应小根笛卡尔树上的所有节点，每次递归处理的两个小联通块正是当前节点的两个儿子。根据定义，我们可以知道，对于节点 x 代表的矩形，它的长度为 siz_x，高度为 h_x-h_{fa_x}。
这样，我们建出笛卡尔树，就可以把这一问题转化成树上背包问题了。

定义 f_{i,j} 表示在节点 i 子树所代表的区域内选择了 j 个格子的方案数，两个儿子的答案显然可以用树形背包合并，难点就只剩下如何计算与合并当前节点的方案了。
枚举当前节点所代表的矩形选了 j 个格子，子树内其余部分选了 k 个格子，我们可以将当前矩形的方案数表示成 C_{siz_x-k}^j\times C_{h_x-h_{fa_x}}^j \times j!，也就是选择行、列的方案数乘上 j 的全排列。
通过树上背包的 siz 优化，我们保证两个节点总是在它的 LCA 处合并，总复杂度为 O(nk+\max\{h_i\})。

代码

#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int mod=1e9+7;
const int MN=505;
const int MM=1e6+5;
int n,m,top,h[MN],stk[MN],ch[MN][2],f[MN][MN],siz[MN];
int fac[MM],inv[MM];
inline ll C(int n,int m){
    return 1ll*fac[n]*inv[n-m]%mod*inv[m]%mod;
}
void dfs(int st,int pre){
    f[st][0]=1;siz[st]=1;
    reg int val=h[st]-pre;
    for(reg int i=0;i<2;i++){
        if(!ch[st][i])continue;
        dfs(ch[st][i],h[st]);
        siz[st]+=siz[ch[st][i]];
        for(reg int j=min(siz[st],m);~j;j--)
            for(reg int k=1;k<=min(siz[ch[st][i]],j);k++)
                f[st][j]=(f[st][j]+1ll*f[ch[st][i]][k]*f[st][j-k])%mod;
    }
    for(reg int i=min(siz[st],m);~i;i--)
        for(reg int j=1;j<=min(val,i);j++)
            f[st][i]=(f[st][i]+1ll*f[st][i-j]*fac[j]%mod*C(val,j)%mod*C(siz[st]-i+j,j))%mod;
}
int main(){
    scanf("%d%d",&n,&m);
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(reg int i=2;i<MM;i++)fac[i]=1ll*fac[i-1]*i%mod;
    for(reg int i=2;i<MM;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(reg int i=2;i<MM;i++)inv[i]=1ll*inv[i-1]*inv[i]%mod;
    for(reg int i=1;i<=n;i++)scanf("%d",h+i);
    for(reg int i=1;i<=n;i++){
        while(top&&h[stk[top]]>h[i])ch[i][0]=stk[top--];
        if(top)ch[stk[top]][1]=i;
        stk[++top]=i;
    }
    dfs(stk[1],0);
    printf("%d\n",f[stk[1]][m]);
    return 0;
}