(mathcal{Description})
Link.
有 (n) 个牛棚，大小为 (t_{1..n})，(n) 头奶牛，大小为 (s_{1..n})，奶牛只能住进不小于自己的牛棚，每个牛棚最多住一头奶牛。求满足不能让更多奶牛住进牛棚的安排方案数，答案对 ((10^9+7)) 取模。
(nle3 imes10^3)。
(mathcal{Solution})
把 (s) 和 (t) 倒一块儿升序排序，大小相同奶牛优先。那么相当于奶牛只能住进自己后面的某个房间，转化成了熟悉的括号问题。
考虑一个方案合法的条件：最左侧失配的左括号（奶牛）在最右侧失配的右括号（牛棚）右侧（否则它们就能够再匹配了）。
接下来的 DP 就比较平凡啦，令 (f(i,j,0/1)) 表示考虑了序列前 (i) 个元素，有 (j) 个左括号预定了接下来的右括号和它匹配，出现 / 未出现“最左侧失配的左括号”时的方案数。分第 (i) 个位置是奶牛还是牛棚转移（(longleftarrow) 表示前者被后者贡献）：
- 奶牛转移：
- 预定后方房间，(f(i,j,0/1)longleftarrow f(i-1,j-1,0/1))；
- 成为最左侧失配，(f(i,j,1)longleftarrow f(i-1,j,0))；
- 再次失配，(f(i,j,1)longleftarrow f(i-1,j,1))。
- 牛棚转移：
- 去满足某个房间预定，(f(i,j,0/1)longleftarrow (j+1)cdot f(i-1,j+1,0/1))；
- 失配，(f(i,j,0)longleftarrow f(i-1,j,0))。
转移最后一步体现了合法限制。最后答案显然是 (f(2n,0,0)+f(2n,0,1))。
最终，(mathcal O(n^2)) 解决问题。
(mathcal{Code})
代码中最后一维 (0/1) 状态是反过来的 awa。
/* Clearink */
#include <cstdio>
#include <algorithm>
#define rep( i, l, r ) for ( int i = l, rpbound##i = r; i <= rpbound##i; ++i )
#define per( i, r, l ) for ( int i = r, rpbound##i = l; i >= rpbound##i; --i )
typedef std::pair<int, int> PII;
#define fi first
#define se second
const int MAXN = 3e3, MOD = 1e9 + 7;
int n, f[MAXN * 2 + 5][MAXN + 5][2]; // !!!
PII s[MAXN * 2 + 5];
inline int mul( const long long a, const int b ) { return a * b % MOD; }
inline int sub( int a, const int b ) { return ( a -= b ) < 0 ? a + MOD : a; }
inline int add( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline void addeq( int& a, const int b ) { ( a += b ) >= MOD && ( a -= MOD ); }
int main() {
// freopen ( "sleeping.in", "r", stdin );
// freopen ( "sleeping.out", "w", stdout );
scanf( "%d", &n );
rep ( i, 1, n ) scanf( "%d", &s[i].fi ), s[i].se = 0;
rep ( i, n + 1, n << 1 ) scanf( "%d", &s[i].fi ), s[i].se = 1;
std::sort( s + 1, s + ( n << 1 | 1 ) );
f[0][0][1] = 1;
rep ( i, 1, n << 1 ) {
if ( !s[i].se ) rep ( j, 0, n ) { // cow.
if ( j ) {
addeq( f[i][j][1], f[i - 1][j - 1][1] );
addeq( f[i][j][0], f[i - 1][j - 1][0] );
}
addeq( f[i][j][0], add( f[i - 1][j][0], f[i - 1][j][1] ) );
} else rep ( j, 0, n ) { // house.
f[i][j][0] = mul( j + 1, f[i - 1][j + 1][0] );
f[i][j][1] = add( mul( j + 1, f[i - 1][j + 1][1] ),
f[i - 1][j][1] );
}
}
printf( "%d
", add( f[n << 1][0][0], f[n << 1][0][1] ) );
return 0;
}