题解：CF2234E Vlad, Misha and Two Arrays

· · 题解

线性做法。

显然对于点 i，a_i 就是笛卡尔树左子树大小 +1 与右子树大小 +1 的乘积。考虑直接把笛卡尔树建出来，答案就是所有节点的 \displaystyle\binom{siz_l+siz_r}{siz_l} 乘积。

考虑现在在建树 [l,r]。l 必然是最左端的点，它的左子树大小为 0，我们得以获知其右子树大小，从而可以直接获得 l 的父亲 f_l。f_l 的左子树大小也已知，可以获知其右子树大小，也可获知 f_l 的父亲。以此类推，我们可以把根找出来的同时把根往左不断走的这条左偏链整个找出来。

那么一路上每个右子树 [l+1,f_l-1] 都是独立的子问题，进去建树就好了。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define mod 1000000007
#define MAXN 500005

int n,a[MAXN],fac[MAXN],inv[MAXN],ifac[MAXN],Fa[MAXN],siz[MAXN],vis[MAXN];
vector<int> E[MAXN];

inline int C( int n , int m ){ return n >= m && n >= 0 && m >= 0 ? fac[n] * ifac[m] % mod * ifac[n - m] % mod : 0; }

inline int read(){
    int x = 0; char ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = x * 10 + ch - 48,ch = getchar();
    return x;
}

int Ans = 1,flag = 0,Cnt = 0,Snt = 0;

inline void clear(){
    for( int i = 1 ; i <= n ; i ++ ) Fa[i] = 0,E[i].clear(),siz[i] = vis[i] = a[i] = 0;
    Ans = 1,flag = Cnt = Snt = 0;
}

int build( int t ){
    Cnt ++; if( Cnt > n ) return flag = 0;
    if( vis[t] ) return flag = 0;
    Snt ++,vis[t] = 1;
    siz[t] = 1;
    int L = 0,p = 1;
    for( int v : E[t] ){
        int res = build( v );
        if( !res ) return flag = 0;
        p *= ( siz[v] + 1 ),siz[t] += siz[v];
        if( !L ) L = siz[v];
    }
    Ans = Ans * C( siz[t] - 1 , L ) % mod;
        // assert( t <= n );
    if( p != a[t] ) return flag = 0;
    return 1;
}

//找左偏链
int BL( int l , int r ){
    //已知 [l,r] 是一棵子树
    if( l == r ) return a[l] == 1 ? l : flag = 0;
    int p = l;
    while( 1 ){
        assert( p <= n );
        if( a[p] % ( p - l + 1 ) ) return flag = 0;
        int rsiz = a[p] / ( p - l + 1 );
        int nxt = p + rsiz;
        if( nxt <= p ) return flag = 0;
        if( nxt <= r ) Fa[p] = nxt;
        //这里致命问题：p>n 的话也会进去
        if( nxt > r + 1 ){ return flag = 0; }
        if( nxt - p > 1 ){
            int res = BL( p + 1 , nxt - 1 );
            if( !res ) return flag = 0;
            Fa[res] = p;
        }
        if( nxt == r + 1 ) return p;
        else if( nxt > r + 1 ) return flag = 0;
        p = nxt;
    }
}

inline void solve(){
    flag = 1,Cnt = 0;
    n = read();
    int S = 0;
    for( int i = 1 ; i <= n ; i ++ ) a[i] = read(),S += a[i];
    if( S != n * ( n + 1 ) / 2 ){ puts("0"); clear(); return; }
    int rt = BL( 1 , n );
    if( !rt || !flag ){ puts("0"); clear(); return; }
    // int t
    for( int i = 1 ; i <= n ; i ++ ){
        if( Fa[i] ) E[Fa[i]].emplace_back( i );
        else if( i != rt ){ puts("0"); clear(); return; }
    }
    for( int i = 1 ; i <= n ; i ++ ) assert( E[i].size() <= 2 );
    Ans = 1,Snt = 0;
    int res = build( rt );
    if( !res || siz[rt] != n || !flag || Snt != n ){ puts("0"); clear(); return; }
    printf("%lld\n",Ans); clear(); return;
}

signed main(){
    fac[0] = inv[1] = ifac[0] = 1;
    for( int i = 1 ; i < MAXN ; i ++ ) fac[i] = fac[i - 1] * i % mod;
    for( int i = 2 ; i < MAXN ; i ++ ) inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;
    for( int i = 1 ; i < MAXN ; i ++ ) ifac[i] = ifac[i - 1] * inv[i] % mod;
    int t = read();
    while( t -- ) solve();
    return 0;
}