题解：CF1946E Girl Permutation

· · 题解

先判定一些必然条件，a_1=1,b_{m_2}=n,a_{m_1}=b_1。然后考虑刻画前缀最大值的要求。建出一棵外向树，x 向 y 连边表示要求 p_x>p_y。对于 a 数列，遍历 i\in[1,m_1)，a_{i+1} 向 a_{i} 连边，a_{i} 向 [a_{i}+1,a_{i+1}-1] 之间所有数连边；对于 b 数列，遍历 i\in[1,m_2)，b_{i} 向 b_{i+1} 连边，b_{i+1} 向 [b_{i+1}+1,b_i-1] 之间所有数连边。然后 \rm dfs，求出树上所有点的子树大小 siz_i，树的拓扑序个数 \displaystyle\frac{n!}{\prod_{i=1}^nsiz_i} 就是答案。

复杂度 O(n)。答案还可以刻画成连续段 \rm DP 的形式，也即若干组合数的乘积。

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

#define int long long
#define MAXN 200005
#define mod 1000000007

const int INF = 1000000000000000000ll;

int fac[MAXN],inv[MAXN],ifac[MAXN];
int n,m1,m2,siz[MAXN],a[MAXN],b[MAXN];
vector<int> E[MAXN];

inline int C( int n , int m ){ return n >= m ? fac[n] * ifac[m] % mod * ifac[n - m] % mod : 0; }
inline int fp( int x , int p ){ int res = 1; while( p ){ if( p & 1 ) res = res * x % mod; x = x * x % mod; p >>= 1; } return res; }

int Ans = 1;
void dfs( int x ){
    siz[x] = 1;
    for( int v : E[x] ) dfs( v ),siz[x] += siz[v];
    Ans = Ans * inv[siz[x]] % mod;
}

inline void solve(){
    scanf("%lld%lld%lld",&n,&m1,&m2);
    for( int i = 1 ; i <= m1 ; i ++ ) scanf("%lld",&a[i]);
    for( int i = 1 ; i <= m2 ; i ++ ) scanf("%lld",&b[i]);
    if( a[m1] != b[1] || a[1] != 1 || b[m2] != n ){ puts("0"); return; }
    for( int i = 1 ; i < m1 ; i ++ ){
        for( int j = a[i] + 1 ; j < a[i + 1] ; j ++ ) E[a[i]].emplace_back( j );
        E[a[i + 1]].emplace_back( a[i] );
    }
    for( int i = m2 ; i > 1 ; i -- ){
        for( int j = b[i] - 1 ; j > b[i - 1] ; j -- ) E[b[i]].emplace_back( j );
        E[b[i - 1]].emplace_back( b[i] );
    }
    Ans = fac[n];
    dfs( a[m1] );
    printf("%lld\n",Ans);
    for( int i = 1 ; i <= n ; i ++ ) E[i].clear();
}

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 testcase; scanf("%lld",&testcase);
    while( testcase -- ) solve();
    return 0;
}