P6453 [COCI2008-2009#4] PERIODNI 题解

· · 题解

一道广为人知的笛树题。既然 SPOJ 交不了了双倍经验没了，那就在这里交一发题解。

事先感谢 @Dyc780511 大佬。

这道题运用了一个技巧：将图建成树。

考虑到如果有一个最小的棋盘将两边分隔开，那么除去这个棋所在的行以外，剩下的两组棋盘互不干扰。即对于 i>h_x，棋盘 x 左边的第 i 行和棋盘 x 右边的第 i 行互不干扰。那么可以通过这一点进行树形 DP。我们发现，一个子树的根节点是整个区间的最小值，所以整棵树是一棵笛卡尔树。给出的高度相当于 w，下标相当于 k。接着令 f_{i,j} 表示节点 i 为根的子树中放置 j 个节点，且所有棋子所在行的编号不小于节点 i 的父亲节点的高度，即棋子的行编号在区间 \left(h_{\textit{fa}(x)},\infty\right) 内的方案数。

先考虑棋子编号在区间 \left(h_x,\infty\right) 的方案数，此时相当于一个背包，转移方程为：

f_{i,j}=\sum_{\textit{to}\in\textit{son}_i}\sum_{k=1}^{j}f_{\textit{to},k}\times f_{i,j-k}

注意此时为了不让数组刚更新的内容去更新其他内容，因此 j 应从大到小循环。接着考虑行编号在区间 \left(h_{\textit{fa}(x)},h_x\right] 中的棋子。我们如果放 k 个这样的棋子，那么说明必须有一些列是空的，接着从范围内选出 k 个不同的数字然后分在这些空列当中，转移方程为：

f_{i,j}=\sum_{k=1}^{j}f_{i,j-k}\times \binom{h_x-h_{\textit{fa}(x)}}{k}\times\mathrm A_{\textit{siz}_i-(j-k)}^{k}

注意此时为了不让数组刚更新的内容去更新其他内容，因此 j 应从大到小循环。最后两个区间的方案数累加起来就是对应的值。最后的答案是 f_{rt,k}。

#include <bits/stdc++.h>
#define inv(i) (power(fac[i], MOD - 2))
#define int long long
using namespace std;

constexpr int MAXN = 505, MOD = 1e9 + 7, MAXH = 1e6 + 5;
int n, k, a[MAXN];
int ls[MAXN], rs[MAXN], rt, siz[MAXN];
stack<int> st;
int fac[MAXH];
int f[MAXN][MAXN];

int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < MAXH; i++) fac[i] = fac[i - 1] * i % MOD;
}

int A(int n, int m) {
    if (n < m || n < 0 || m < 0) return 0;
    return fac[n] * inv(n - m) % MOD;
}

int C(int n, int m) {
    if (n < m || n < 0 || m < 0) return 0;
    return fac[n] * inv(m) % MOD * inv(n - m) % MOD;
}

void insert(int k, int w) {
    while (!st.empty() && w < a[st.top()]) {
        ls[k] = st.top();
        st.pop();
    }
    if (!st.empty()) rs[st.top()] = k;
    else rt = k;
    st.push(k);
}

void dfs(int x, int fno) {
    siz[x] = 1;
    if (ls[x]) dfs(ls[x], x);
    if (rs[x]) dfs(rs[x], x);
    siz[x] += siz[ls[x]] + siz[rs[x]];
    f[x][0] = 1;
    for (int i = k; i >= 1; i--)
        for (int j = 1; j <= min(i, siz[ls[x]]); j++)
            f[x][i] = (f[x][i] + f[ls[x]][j] * f[x][i - j] % MOD) % MOD;
    for (int i = k; i >= 1; i--)
        for (int j = 1; j <= min(i, siz[rs[x]]); j++)
            f[x][i] = (f[x][i] + f[rs[x]][j] * f[x][i - j] % MOD) % MOD;
    for (int i = min(k, siz[x]); i >= 1; i--)
        for (int j = 1; j <= i; j++)
            f[x][i] = (f[x][i] + f[x][i - j] * C(a[x] - a[fno], j) % MOD * A(siz[x] - i + j, j) % MOD) % MOD;
}

signed main() {
    init();
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), insert(i, a[i]);
    dfs(rt, 0);
    cout << f[rt][k] << '\n';

    return 0;
}