题解-bzoj4221 JOI2012kangaroo

Problem

bzoj

题意：给定\(n\)只袋鼠，每只袋鼠有俩属性\(a,b\)，若\(a_i\leq b_j\)，则\(i\)是可以被\(j\)放置在袋子里的，求经过一系列放置操作后无法进行操作时的状态有多少种可能（每只袋鼠只能被一只袋鼠放在袋子里，同时也只能放一只袋鼠在袋子里）

\(n\leq 300,\forall i\in[1,n]a_i\geq b_i\)

Solution

将每只袋鼠拆成出点和入点后做匹配，相当于剩余未匹配点中\(\min a\geq \max b\)的匹配方案数

由于\(a_i\geq b_i\)保证不可能自己连向自己，相当于是自由匹配，所以点与点之间的顺序是没有任何关系的，考虑将两者从大到小排序

设\(f[i][j][k]\)表示当前考虑到第\(i\)只袋鼠的体积，这\(i\)只袋鼠中有\(j\)只已经被匹配，设\(t\)为第\(i\)只袋鼠能塞进的最小口袋（\(t\)也递增），则\(k\)表示前\(t\)个口袋中与袋鼠\([i+1,n]\)中匹配的数量

考虑到在定义下的\(f[i][j][k]\)中，这\(j\)只已经被匹配的袋鼠所对应的口袋一定在区间\([1,t]\)中，所以口袋\([1,t]\)分为三类：

• ① 和区间\([1,i]\)内共\(j\)只袋鼠匹配的口袋，共\(j\)个
• ② 和区间\([i+1,n]\)内共\(k\)只袋鼠匹配的口袋，共\(k\)个
• ③ 自由节点，尚未匹配，共\(t-j-k\)个

理顺了这些可以得到以下仨转移式（一般自己写可能会有情况缺漏，反正我是想了很久）

\[f[i][j][t-j]+=f[i-1][j][k]\]

\[f[i][j+1][k]+=f[i-1][j][k]\cdot (t-j-k)\]

\[f[i][j+1][k-1]+=f[i-1][j][k]\cdot k\]

自然统计答案

\[Ans=\sum_{i=0}^nf[n][i][0]\]

Code

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

template <typename _Tp> inline _Tp read(_Tp&x){
    char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
    while(isdigit(c11))x=x*10+c11-'0',c11=getchar();return x;
}

const int N=301,p=1e9+7;
int f[N][N][N],a[N],b[N];
int n,ans;

template <typename _tp> inline void pls(int&A,_tp B){A=A+B<p?A+B:A+B-p;}
inline bool cmp(const int&A,const int&B){return A>B;}

void init();void work();void print();
int main(){init();work();print();return 0;}

void work(){
    f[0][0][0]=1;
    for(rg int i=1,t=1;i<=n;++i){
        if(!t)++t;
        while(a[i]<b[t]&&t<=n)++t;--t;
        for(rg int j=0;j<i;++j)
        for(rg int k=0;k+j<=t;++k){
            pls(f[i][j][t-j],f[i-1][j][k]);
            pls(f[i][j+1][k],1ll*f[i-1][j][k]*(t-j-k)%p);
            if(k)pls(f[i][j+1][k-1],1ll*f[i-1][j][k]*k%p);
        }
    }
}

void print(){
    for(rg int i=0;i<=n;++i)
        pls(ans,f[n][i][0]);
    printf("%d\n",ans);
}

void init(){
    read(n);
    for(rg int i=1;i<=n;++i)
        read(a[i]),read(b[i]);
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
}