【洛谷】COCI2008-2009第四轮PERIODNI问题深入解析

题目链接：https://www.luogu.com.cn/problem/P6453

因为一行中如果断开的话就不算在同一行了，所以我们可以一行一行来考虑。

这样的话每层都会截出来一个最大的矩形，这有点向一个树形结构，可以用笛卡尔树（还是有点难想的）

这里提一下，对于2312131这样的棋盘

三个1本来应该是同等级别的，但是在树上却有父子关系，这不要紧，因为它们之间的高的差为0

记f[i][j]表示以i为代表的区域内放j个棋的方案数，sz[u]表示以u为根的子树大小

显然，对于节点u，其矩阵的长为sz[u]，宽为h[u]-h[fa[u]]。

所以我们先跑一个树上背包，合并所有子树的情况，再单独讨论该节点的区域内的放置情况。

假设一共放j个棋，在该区域内放k个棋则方案数为\(\dbinom{sz[u]-j+k}{k} \dbinom{h[u]-h[fa[u]]}{k} k!\)

本来矩阵的长为sz[u]，但是要在子节点的范围内先放上j-k个棋，占用了j-k列，故还有sz[u]-j+k列能用来放

#include
using namespace std;
const int N = 505, M = 1e6 + 5, P = 1e9 + 7;
int n, m, top, stk[N], inv[M], invfac[M], fac[M];
int h[N], f[N][N], sz[N], son[N][2];
inline void init(int n){
inv[1] = fac[1] = fac[0] = invfac[1] = invfac[0] = 1;
for (int i = 2; i <= n; ++i){
inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
invfac[i] = 1ll * invfac[i - 1] * inv[i] % P;
fac[i] = 1ll * fac[i - 1] * i % P;
}
}
inline int C(int x, int y){
if (x <0 || y <0 || x > y) return 0;
return 1ll * fac[y] * invfac[y - x] % P * invfac[x] % P;
}
void dfs(int u, int fath){
f[u][0] = 1, sz[u] = 1;
int hi = h[u] - h[fath];
for (int i = 0; i <= 1; ++i){
int v = son[u][i];
if (!v) continue;
dfs(v, u);
for (int j = min(sz[u], m); j >= 0; --j)
for (int k = 1; k <= min(sz[v], m - j); ++k)
f[u][j + k] = (f[u][j + k] + 1ll * f[u][j] * f[v][k]) % P;
sz[u] += sz[v];
}
for (int i = min(sz[u], m); i >= 1; --i)
for (int j = 1; j <= min(i, hi); ++j)
f[u][i] = (f[u][i] + 1ll * f[u][i - j] * C(j, sz[u] - i + j) % P * C(j, hi) % P * fac[j]) % P;
}
int main(){
init(M - 5);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", h + i);
for (int i = 1; i <= n; ++i){
while (top && h[i] if (top) son[stk[top]][1] = i;
stk[++top] = i;
}
dfs(stk[1], 0);
printf("%d\n", f[stk[1]][m]);
return 0;
}