SPOJ3734 Periodni

Description

给定一个 $n$ 列的表格，每列的高度 $h_i$ 各不相同，但底部对齐，然后向表格中填入 $k$ 个相同的数，填写时要求不能有两个数在同一列。若两个数在同一行，但是中间某一列断开是被允许的，否则也不允许。求填数的方案数对 $10^9+7$ 取模的值。
$n\leq 500,h_i\leq 10^6$

Solution

经典题了，这里 mark 一下做法。
可以发现，取出全局最小的位置 $p$ 后，该位置将序列分为了左右两个部分。这两个部分在 $h_p$ 以上的部分是互相独立的，也就被划成了两个不相关的子问题。
建出原树的笛卡尔树。每个节点掌管的高度为自己的高度减去父节点的高度，设为 $H[p]=h[p]-h[\text{fa}_p]$ ；掌管的长度为区间的长度，设为 $L[p]$ 。
在笛卡尔树上做背包合并。设 f[p][i] 表示 $p$ 节点代表的区间选 $i$ 个的方案数，那么合并子树时有：

$f[p][i+j]=\sum_{i=0}^{n}\sum_{j=0}^{n}f[\text{lc}_p][i]\times f[\text{rc}_p][j]$

接下来考虑合并在 H[p] 的范围内的点。这时我们所需要考虑的选点就是在一个 $H[p]\times L[p]$ 的矩形内。
假设选 $j$ 个点，那么首先我们要选出 $j$ 行，再选出 $j$ 列，然后再对这 $j$ 行和 $j$ 列进行匹配。
于是可以知道

$f[p][i+j]=\sum_{i=0}^{n}\sum_{j=0}^{n} f[p][i]\times \binom{H[p]}{j}\binom{L[p]}{j}\times j!$

所以就得到了一个复杂度 $\mathcal{O}(n^3)$ 的做法。卡卡上界就过了。

Code

long long tmp[N],f[N][N];
void DFS(int p,int l,int r,int las){
    if(c[p][0]) DFS(c[p][0],l,p-1,h[p]);
    if(c[p][1]) DFS(c[p][1],p+1,r,h[p]);
    for(int i=0;i<=p-l;++i)
    for(int j=0;j<=r-p;++j)
        Plus(f[p][i+j],1ll*f[c[p][0]][i]*f[c[p][1]][j]%mod);
    int H=h[p]-las,L=r-l+1;
    memset(tmp,0,sizeof tmp);
    for(int i=0;i<=n;++i)
    for(int j=0;j<=n&&i+j<=k;++j)
        Plus(tmp[i+j],1ll*f[p][i]*C(H,j)%mod*C(L-i,j)%mod*fac[j]%mod);
    for(int i=0;i<=min(L,k);++i)
        f[p][i]=tmp[i];
}