SP3734

· · 题解

一道十分神奇的题目。

首先，本题中的图形形状过于诡异，我们可以把它拆成若干个矩形，对于每个矩形单独处理，最后合并答案。为了方便处理，笔者使用的方法如下：

从以上图形中不难看出：设这段图形是 [l,r]，则图中的 C 和 F 区域长度即为 r-l+1，高度即为 \min\{h_i\},i\in[l,r]，然后上方的图形分为左右两个区域，递归处理即可。

在这个分图形的过程中，不难发现，这就是一颗笛卡尔树的建树过程，其中 i 满足二叉搜索树，h_i 满足小根堆，于是我们可以优化建树的过程（其实不优化也可以，但跑得可能相对会慢一些）。

接下来考虑怎么统计答案。

首先我们先来给各个矩形编号以方便处理。

对于长在 [l,r] 的矩形，我们令其编号为 u，当且仅当 \min\{h_i\}=h_u,i\in[l,r]，若有多个满足条件的 u 任选其一即可。容易发现，如果我们以 u 为界限，将编号为 u 的矩形上方的图形分为两个并递归处理（即上面所讲的笛卡尔树建树过程），每个矩形的编号不重复。

接下来，设 f[u][k] 表示编号为 u 的矩形即其上方图形部分中放入 k 个数且满足题设条件的方案数。

对于上面的 A，不难发现，如果当前矩形上方什么也没有，设 a 为矩形的长（r-l+1），b 为矩形的宽，那么

f[u][k]=\dfrac{A_a^kA_b^k}{A_k^k}

解释：从 a 列里有序选 k 列，从 b 行里有序选择 k 行，得到 k 个有序的交点，但由于填入 k 个无序的数，所以要去重。

接下来考虑答案的合并。

设编号为 u 的矩形上方部分中左边部分的编号为 l（即笛卡尔树中的该节点的左儿子），右边部分为 r（即笛卡尔树中的该节点的右儿子），我们可以枚举在 l 中放了 i 个数，在 r 中放了 j 个数，于是在矩形中便要放 k-i-j。不难发现

f[u][k]=\sum_{i=0}^{k}\sum_{j=0}^{k-i}f[l][i]\times f[r][j]\times\dfrac{A_{a-i-j}^{k-i-j}A_b^{k-i-j}}{A_{k-i-j}^{k-i-j}}

其中 a 为矩形的长，b 为矩形的宽。

但是这个式子的时间复杂度是遍历树 O(n) 乘上枚举 k,i,j 共为 O(nk^3)，过不了。

考虑设

g[u][p]=\sum_{i+j=p}f[l][i]\times f[r][j]

该式子为 O(k^2)。

则

f[u][k]=\sum_{p=0}^{k}g[u][p]\times\dfrac{A_{a-p}^{k-p}A_b^{k-p}}{A_{k-p}^{k-p}}

式子被优化成了 O(k^2)。

此时总复杂度已经降为 O(nk^2)，可过。

code

#include <bits/stdc++.h>
#define fq(i,a,b) for (int i = (a); i <= (b); i++)
using namespace std;
#define int long long
inline int rd () {
    int f = 1;
    char ch = getchar ();
    while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
    int num = 0;
    while (isdigit (ch)) num = num * 10 + ch - '0', ch = getchar ();
    return num * f;
}
#define d rd ()

const int maxn = 550;
const int mod = 1e9+7;
int n = d, k = d, h[maxn];
int l[maxn], r[maxn], sk[maxn], top;
int mul[1001000], invm[1001000];
bool cmp (int a, int b) {
    return h[a] < h[b];
}
int f[maxn][maxn], g[maxn], sz[maxn];
void prew (int u) {
    sz[u] = 1;
    if (l[u]) prew (l[u]), sz[u] += sz[l[u]];
    if (r[u]) prew (r[u]), sz[u] += sz[r[u]];
}
int A (int N, int M) {
    if (M > N) return 0;
    return mul[N] * invm[N - M] % mod;
}
int sol (int N, int M, int K) {
    return A (N, K) * A (M, K) % mod * invm[K] % mod;
}
void dfs (int u, int low) {
    int uh = h[u] - low;
    if (!l[u] && !r[u]) {
        f[u][0] = 1;
        fq (i, 1, k) f[u][i] = sol (sz[u], uh, i);
        return;
    }
    if (!l[u] || !r[u]) {
        int v;
        if (!l[u]) v = r[u];
        else v = l[u];
        dfs (v, h[u]);
        memset (g, 0, sizeof g);
        g[0] = 1;
        fq (i, 1, k) fq (j, 0, i) g[i] = (g[i] + f[0][j] * f[v][i - j]) % mod;
        f[u][0] = 1;
        fq (i, 1, k) fq (j, 0, i) f[u][i] = (f[u][i] + g[j] * sol (uh, sz[u] - j, i - j)) % mod;
        return;
    }
    dfs (l[u], h[u]);
    dfs (r[u], h[u]);
    memset (g, 0, sizeof g);
    g[0] = 1;
    fq (i, 1, k) fq (j, 0, i) g[i] = (g[i] + f[l[u]][j] * f[r[u]][i - j]) % mod;
    f[u][0] = 1;
    fq (i, 1, k) fq (j, 0, i) f[u][i] = (f[u][i] + g[j] * sol (uh, sz[u] - j, i - j)) % mod;
}
int power (int a, int b, int p) {
    int c = 1;
    while (b) {
        if (b & 1) c = c * a % p;
        a = a * a % p;
        b >>= 1;
    } return c;
}
signed main () {
    mul[0] = invm[0] = 1;
    fq (i, 1, 1000000) {
        mul[i] = mul[i - 1] * i % mod;
        invm[i] = invm[i - 1] * power (i, mod - 2, mod) % mod;
    }
    fq (i, 1, n) h[i] = d;
    fq (i, 1, n) {
        int kk = top;
        while (kk && h[sk[kk]] > h[i]) --kk;
        if (kk) r[sk[kk]] = i;
        if (kk != top) l[i] = sk[kk + 1];
        sk[top = ++kk] = i;
    } prew (sk[1]); f[0][0] = 1;
    dfs (sk[1], 0); cout << f[sk[1]][k] << endl;
    return 0;
}