Gym102501J

题意：给定一个二叉树的中序遍历，且子节点的值一定大于或等于父节点的值，求有多少种二叉树满足该中序遍历。

子问题：n个节点的二叉树有多少种形态

1. 若有1个节点，显然$f(1)=1$
2. 若有2个节点，考虑固定一个节点，有$f(2)=f(0)*f(1)+f(1)*f(0)=2$，这里我们定义$f(0)=1$
3. 若有3个节点，考虑固定一个节点，则易得$f(3) = f(2)+f(1)*f(1)+f(2)$
4. 若有n各节点，有$f(n)=f(n-1)+f(n-2)f(1)+...+f(1)f(n-2)+f(n-1)$

很明显是卡特兰数，祭出公式：$f(n)=\frac{(2n)!}{n!(n+1)!}$

观察：若一段序列有$a[l]=a[r]$且$min(a[l+1],...a[r-1])>a[l]$，则$a[l+1],...a[r-1]$在同一颗子树中

反证法，如果不在同一颗子树，意味着存在$a[i]\le a[l]\ (i \notin \{l, r\})$，与前提相违背

处理中序遍历用堆栈！

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 1e6 + 1e5;
const ll mod = 1e9 + 7;

int n, w[maxn];
ll fac[maxn * 2], inv[maxn + 100];

ll qpow(ll base, ll t){
    ll ret = 1;
    while(t){
        if(t & 1) ret = ret * base % mod;
        t >>= 1;
        base = base * base % mod;
    }
    return ret;
}

void init(){
    fac[1] = 1;
    for(int i=2, k=maxn*2; i<k; i++) fac[i] = fac[i-1] * i % mod;
    inv[maxn] = qpow(fac[maxn], mod-2);
    for(int i=maxn-1; i>=0; i--) inv[i] = (inv[i+1]*(i+1)) % mod;
}

int stk[maxn], top = 0;
void solve(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> w[i];
    w[n+1] = -1;
    ll ans = 1;
    for(int i=1; i<=n+1; i++){
        while(top && stk[top-1] > w[i]){
            int cnt = 0;
            while(cnt < top && stk[top-1] == stk[top-1-cnt]) cnt++;
            top -= cnt;
            ans = ans * fac[2*cnt] % mod * inv[cnt] % mod * inv[cnt+1] % mod;
        }
        stk[top++] = w[i];
    }
    cout << ans << endl;
}

signed main(){
    init();
    solve();
}