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

Problem - E - Codeforces

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;
}
```