题解 P7154 【[USACO20DEC] Sleeping Cows P】
Kubic
2020-12-26 19:51:50
看到题解里没有跟我做法一样的，就来写一篇（
首先很容易想到把 $s,t$ 分别从小到大排序，不影响答案。
然后可以暴力统计出 $s$ 中每个数可以跟 $t$ 中多少数匹配（记为 $a_i$）。以及 $t$ 中每个数可以跟 $s$ 中多少数匹配（记为 $b_i$）。
接下来我们考虑枚举一个 $i$，并计算出所有未匹配的牛中编号最小值为 $i$ 时的方案数。
设这个 $i$ 可以匹配到的牛棚中编号最小值为 $t$。
此时我们发现，编号在 $[t,n]$ 中的牛棚必须被其它的牛匹配完毕，否则这个匹配就不是极大的。
现在有这样几种匹配方式：
- $[1,i)$ 中的牛匹配 $[1,t)$ 中的牛棚
- $[1,i)$ 中的牛匹配 $[t,n]$ 中的牛棚
- $(i,n]$ 中的牛匹配 $[t,n]$ 中的牛棚
显然 $[1,i)$ 中的每一头牛都可以与 $[t,n]$ 中的任何一个牛棚匹配。而 $[1,i)$ 中不与 $[t,n]$ 中某一个牛棚匹配的牛一定全部都与 $[1,t)$ 中某一个牛棚匹配。
我们就可以考虑枚举一个 $j$，并算出 $[1,i)$ 中的牛与 $[t,n]$ 中的牛棚一共匹配了 $j$ 对的方案数。
此时可以发现：
- $[1,i)$ 中剩下的牛有 $i-j-1$ 头，全部都与 $[1,t)$ 中的牛棚匹配。
- $[t,n]$ 中剩下的牛棚有 $n-t-j+1$ 个，全部都与 $(i,n]$ 中的牛匹配。
这样就可以利用很久之前算出的 $a,b$ 来预处理。
$f_{i,j}$ 表示 $[1,i]$ 中的**牛棚**与所有**牛**匹配 $j$ 对的方案数。
$g_{i,j}$ 表示 $[i,n]$ 中的**牛**与所有**牛棚**匹配 $j$ 对的方案数。
具体转移比较显然，可以看代码（
然后我们利用计算出的 $f,g$ 来求答案。枚举到 $i,j$ 时的答案就是 $f_{t-1,i-j-1}\times g_{i+1,n-t-j+1}\times j!$。其中 $j!$ 的意思就是 $[1,i)$ 中的牛与 $[t,n]$ 中的牛匹配 $j$ 对的方案数，因为可以任意匹配。
注意答案还要加上 $f_{n,n}$，表示全部牛都匹配完的方案数。
注：代码中变量名与题解中不太一样，$a1=s,a2=t,b1=a,b2=b,dp1=f,dp2=g$。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define N 3005
#define MOD 1000000007
int n,ans,fc[N],a1[N],a2[N],b1[N],b2[N],dp1[N][N],dp2[N][N];
int main()
{
scanf("%d",&n);fc[0]=dp1[0][0]=dp2[n+1][0]=1;
for(int i=1;i<=n;++i) fc[i]=1ll*fc[i-1]*i%MOD;
for(int i=1;i<=n;++i) scanf("%d",&a1[i]);sort(a1+1,a1+n+1);
for(int i=1;i<=n;++i) scanf("%d",&a2[i]);sort(a2+1,a2+n+1);
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(a1[i]<=a2[j]) ++b1[i],++b2[j];
for(int i=1;i<=n;++i)
{
dp1[i][0]=1;
for(int j=1;j<=i;++j)
dp1[i][j]=(dp1[i-1][j]+1ll*dp1[i-1][j-1]*max(b2[i]-j+1,0))%MOD;
}
for(int i=n;i;--i)
{
dp2[i][0]=1;
for(int j=1;j<=n-i+1;++j)
dp2[i][j]=(dp2[i+1][j]+1ll*dp2[i+1][j-1]*max(b1[i]-j+1,0))%MOD;
}
for(int i=1,t=1;i<=n;++i)
{
while(t<=n && a1[i]>a2[t]) ++t;
for(int j=0;j<=min(i-1,n-t+1);++j)
ans=(ans+1ll*dp1[t-1][i-j-1]*dp2[i+1][n-t-j+1]%MOD*fc[j])%MOD;
}printf("%d\n",(ans+dp1[n][n])%MOD);return 0;
}
```