CFR 367 E. Sereja and Intervals ( Segment Trick DP + Pigeon Hole Principle )

Problem - E - Codeforces

題意：
在 [ 1, M ] 中，要算有多少種方法，可以有 N 個有序區間( ex: { [ 1, 2 ], [ 3, 4 ] } != { [ 3, 4 ], [ 1, 2 ] } )，不存在任一個區間包含另一個區間，且有至少一個區間的左界為 X，求其餘數。

數據範圍：
需要區間數，值域，1 ≤ N * M ≤ 1e5
指定值 1 ≤ X ≤ M

解法：
首先，若 N > M，根據鴿籠原理，方案數一定是 0，所以我們只需要考慮 N <= M 的情況。
接著考慮，不存在包含關係會是什麼樣的意義，此時如果將左界想成左括弧，右界右括弧，便會發現任一個有包含關係的括弧匹配，都對應一種唯一的不相互包含的區間左右界匹配。
為何？
舉個例子 [ [ ] ]，對應唯一的合法區間匹配 L1, L2, R1, R2。再來 [ [ [ ] ] ]，對應唯一合法的區間匹配 L1, L2, L3, R1, R2, R3。很明顯，無論再往外包幾層，都只會唯一對應一種不存在包含關係的區間匹配。就算形如 [ [ ] [ ] [ ] ]，想想如果要做區間匹配的演算法會怎麼做，一定是從左掃到右，遇到左界的時候... 沒錯，那個左界只會唯一對應它遇到的第一個右界，否則就會存在包含關係。因此得到結論，一個正確的括弧匹配對應一個正確的無包含關係區間匹配，反之亦然，而藉由這個性質可以將原問題轉換成求值域上，每個值至多可放置一個左括弧和右括弧，此時正確的括弧匹配的方案數。
dp[ i ][ j ][ k ][ l ] : 已考慮值域中前 i 個值，已有 j 個左括弧，已有 k 個右括弧，有一個左括弧在指定值 X 上。
轉移如一般括弧匹配動態規劃顯然，詳見代碼。
注意題目求的是排列，以上是組合，所以最後組合數要做全排列。

時間 / 空間複雜度：
O( N * M ) / O( N ^ 2 )

int N, M, X;

void init(){
    cin >> N >> M >> X;
    if( N > M )
        cout << 0 << endl,
        exit( 0 );
}

vvvvi dp;

void preprocess(){
    dp = vvvvi( 2, vvvi( N + 1, vvi( N + 1, vi( 2 ) ) ) );
    dp[ 0 ][ 0 ][ 0 ][ 0 ] = 1;
    for( int i = 0; i < M; ++i ){
        for( int j = 0; j <= N; ++j )
            for( int k = 0; k <= j; ++k )
                for( int l = 0; l < 2; ++l ){
                    ( dp[ 1 ][ j ][ k ][ l ] += dp[ 0 ][ j ][ k ][ l ] ) %= MOD7;
                    if( j + 1 <= N )
                        ( dp[ 1 ][ j + 1 ][ k ][ l | i + 1 == X ] += dp[ 0 ][ j ][ k ][ l ] ) %= MOD7;
                    if( k + 1 <= j )
                        ( dp[ 1 ][ j ][ k + 1 ][ l ] += dp[ 0 ][ j ][ k ][ l ] ) %= MOD7;
                    if( j + 1 <= N and k + 1 <= N )
                        ( dp[ 1 ][ j + 1 ][ k + 1 ][ l | i + 1 == X ] += dp[ 0 ][ j ][ k ][ l ] ) %= MOD7;
                }
        swap( dp[ 0 ], dp[ 1 ] );
        for( int j = 0; j <= N; ++j )
            for( int k = 0; k <= j; ++k )
                for( int l = 0; l < 2; ++l )
                    dp[ 1 ][ j ][ k ][ l ] = 0;
    }
}

void solve(){
    int ans = dp[ 0 ][ N ][ N ][ 1 ];
    function< int ( int, int ) > permutate = [ & ]( int v, int p ){ return p == 1 ? v : permutate( 1LL * v * p % MOD7, p - 1 ); };
    cout << permutate( ans, N ) << endl;
}