题解 P7154 【[USACO20DEC] Sleeping Cows P】
Kubic
·
·
题解
看到题解里没有跟我做法一样的，就来写一篇（
首先很容易想到把 s,t 分别从小到大排序，不影响答案。
然后可以暴力统计出 s 中每个数可以跟 t 中多少数匹配（记为 a_i）。以及 t 中每个数可以跟 s 中多少数匹配（记为 b_i）。
接下来我们考虑枚举一个 i，并计算出所有未匹配的牛中编号最小值为 i 时的方案数。
设这个 i 可以匹配到的牛棚中编号最小值为 t。
此时我们发现，编号在 [t,n] 中的牛棚必须被其它的牛匹配完毕，否则这个匹配就不是极大的。
现在有这样几种匹配方式：
显然 [1,i) 中的每一头牛都可以与 [t,n] 中的任何一个牛棚匹配。而 [1,i) 中不与 [t,n] 中某一个牛棚匹配的牛一定全部都与 [1,t) 中某一个牛棚匹配。
我们就可以考虑枚举一个 j，并算出 [1,i) 中的牛与 [t,n] 中的牛棚一共匹配了 j 对的方案数。
此时可以发现：
这样就可以利用很久之前算出的 a,b 来预处理。
$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;
}
```