3528. [USACO20Dec Platinum]Sleeping Cows

【题目描述】

$Farmer$ $John$ 有 $N$ （$1 \le N \le 3000$）头各种大小的奶牛。他原本为每头奶牛量身定制了牛棚，但现在某些奶牛长大了，使得原先的牛棚大小不够用。具体地说，FJ 原来建造了 $N$ 个牛棚的大小为 $t_1,t_2,\ldots,t_N$，现在奶牛的大小为 $s_1,s_2,\ldots,s_N$（$1\le s_i,t_i\le 10^9$）。

每天晚上，奶牛们都会按照某种方式寻找睡觉的牛棚。奶牛 $i$ 可以睡在牛棚 $j$ 中当且仅当她的大小可以进入牛棚（$s_i\le t_j$）。每个牛棚中至多可以睡一头奶牛。

我们称奶牛与牛棚的一个匹配是极大的，当且仅当每头奶牛可以进入分配给她的牛棚，且对于每头未被分配牛棚的奶牛无法进入任何未分配的空牛棚。

计算极大匹配的数量模 $10^9 + 7$ 的结果。

【输入格式】

输入的第一行包含 $N$。

第二行包含 $N$ 个空格分隔的整数 $s_1,s_2,\ldots,s_N$。

第三行包含 $N$ 个空格分隔的整数 $t_1,t_2,\ldots,t_N$。

【输出格式】

输出极大的匹配的数量模 $10^9 + 7$ 的结果。

【样例1输入】

4
1 2 3 4
1 2 2 3

【样例1输出】

9

【样例1说明】

以下是全部九种极大的匹配。有序对 $(i,j)$ 表示奶牛 $i$ 被分配到了牛棚 $j$。
$(1, 1), (2, 2), (3, 4)$

$(1, 1), (2, 3), (3, 4)$

$(1, 1), (2, 4)$

$(1, 2), (2, 3), (3, 4)$

$(1, 2), (2, 4)$

$(1, 3), (2, 2), (3, 4)$

$(1, 3), (2, 4)$

$(1, 4), (2, 2)$

$(1, 4), (2, 3)$

【样例2输入】

5
2 2 3 3 3
1 1 1 1 3

【样例2输出】

5

【样例3输入】

6
1 2 3 4 5 5
1 2 2 3 3 5

【样例3输出】

90

【样例4输入输出】

点击下载样例4

【数据规模与约定】

测试点 $1\sim3$，满足 $ N \le 8 $。

测试点 $4\sim12$，满足 $ N \le 50 $。

对于 $100\%$ 的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月月赛 Platinum 组