题解：P13037 [GCJ 2021 #2] Hidden Pancakes

· · 题解

tag： 组合数学，单调栈，笛卡尔树，DP。

首先无解情况是 a_{i+1}>a_i+1。

考虑对已知信息进行一些大小判断。覆盖操作类似单调栈，所以考虑建出笛卡尔树。

我们知道了树根 rt。那么，树根一定是最大值 n。那么它的子树呢？考虑给每个子树分配权值，这样可以使方案不重不漏，因为这些方案互相都保证了存在一个元素不同。设选了一些子树后，剩余子树大小的和为 s，当前需要分配的子树大小为 x，那么每个子树被分配的方案为 \binom{s}{x}。根据乘法原理累乘到 rt 即可。

这个方法也可以推广到任意子树。时间复杂度 O(n)。

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define fi first
#define se second
#define y1 noip200
#define stp(x) fixed << setprecision(x)

using namespace std;

const int N = 1e5 + 50, p = 1e9 + 7, inf = 1 << 29;

int n, stk[N], top, f[N], sz[N], fa[N];
int mul1[N], mul2[N];
vector <int> e[N];

void init() {
    mul1[0] = 1;
    for (int i = 1; i <= 100000; i++) mul1[i] = 1LL * mul1[i - 1] * i % p;
    mul2[0] = mul2[1] = 1;
    for (int i = 2; i <= 100000; i++) mul2[i] = 1LL * (p - p / i) * mul2[p % i] % p;
    for (int i = 1; i <= 100000; i++) mul2[i] = 1LL * mul2[i - 1] * mul2[i] % p;
}

int C(int x, int y) {
    return 1LL * mul1[x] * mul2[y] % p * mul2[x - y] % p;
}

void dfs(int u) {
    for (auto v : e[u]) {
        if (v == fa[u]) continue;
        dfs(v);
        sz[u] += sz[v];
        f[u] = 1LL * f[u] * f[v] % p * C(sz[u], sz[v]) % p;
    }
    sz[u]++;
}

void solve() {
    cin >> n;
    top = 0;
    int rt = 0, ok = 1;
    for (int i = 1; i <= n; i++) f[i] = 1, e[i].clear(), sz[i] = 0, fa[i] = 0, stk[i] = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x >= top + 2) 
            ok = 0;
        while (top > x) stk[top--] = 0;
        if (top >= x) --top;
        fa[stk[top + 1]] = i;
        fa[i] = stk[top];
        if (!top) rt = i;
        stk[++top] = i;
    }
    if (!ok) {
        cout << 0 << endl;
        return;
    }
    for (int i = 1; i <= n; i++) e[fa[i]].push_back(i);
    dfs(rt);
    cout << f[rt] << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) 
        cout << "Case #" << i << ": ", solve();
    return 0;
}