kangaroo

题意:

有n(n<=300)只袋鼠，袋鼠i的体积为a_i，口袋大小为bi(a_i>b_i)。

把袋鼠i放入袋鼠j的口袋里。

要求此时袋鼠i和j的口袋里没有袋鼠，且袋鼠i,j不在其它袋鼠口袋里。

不断操作直到不能操作为止，有多少种不同的终止状态，对10⁹+7取模。

分析:

考虑一种合法的终止状态。

一定存在一只袋鼠，比它小的袋鼠都被装了，能装它的袋鼠都装了其它袋鼠。

先将a和b分别排序。

然后枚举这只倒霉的袋鼠i，dp算出方案数。

将a和b都按是否大于a_i分成左右两边。

用f[i][j]表示a中左边前i个与b中左边匹配j对的方案数。

用g[i][j]表示b中右边前i个与a中右边匹配j对的方案数。

枚举a中左边与b中右边匹配的对数k，则这k对有k!种匹配方法。

再乘上ab两边分别匹配的方案数，就是所有的方案数。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>inline void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)
#define dat(i,a,b) for(int i=a;i>b;--i)

const int MAXN=305;
const int Mod=1e9+7;

int n,ans;

int fac[MAXN];

int f[MAXN][MAXN],g[MAXN][MAXN];

int a[MAXN],b[MAXN];

inline void Init(){
	Scan(n);
	rep(i,1,n+1){
		Scan(a[i]),Scan(b[i]);
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	fac[0]=1;
	rep(i,1,n+1)
		fac[i]=1ll*fac[i-1]*i%Mod;
}

inline void Solve(){
	rep(wuke,1,n+1){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		int r=upper_bound(b+1,b+n+1,a[wuke])-b;
		f[0][0]=1;
		rep(i,1,r)
			rep(j,0,i+1){
				f[i][j]=f[i-1][j];
				int x=lower_bound(a+1,a+wuke,b[i])-a-1;
				if(j&&x-j+1>0){
					f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*(x-j+1)%Mod)%Mod;
				}
			}
		g[n+1][0]=1;
		dat(i,n,wuke)
			rep(j,0,n-i+2){
				g[i][j]=g[i+1][j];
				int x=n-(upper_bound(b+r,b+n+1,a[i])-b)+1;
				if(j&&x-j+1>0){
					g[i][j]=(g[i][j]+1ll*g[i+1][j-1]*(x-j+1)%Mod)%Mod;
				}
			}
		int s=min(wuke-1,n-r+1);
		rep(i,0,s+1){
			ans=(ans+1ll*f[r-1][wuke-1-i]*g[wuke+1][n-r+1-i]%Mod*fac[i]%Mod)%Mod;
		}
	}
	printf("%d\n",ans);
}

int main(){
	freopen("kangaroo.in","r",stdin);
	freopen("kangaroo.out","w",stdout);
	Init(); Solve(); return 0;
}