Sleeping Cows

提交数: 1, 通过率: 100%, 平均分: 100

题目描述:

Farmer John 有 N （1≤N≤3000）头各种大小的奶牛。他原本为每头奶牛量身定制了牛棚，但现在某些奶牛长大了，使得原先的牛棚大小不够用。具体地说，FJ 原来建造了 N 个牛棚的大小为t1,t2,…,tN，现在奶牛的大小为 s1,s2,…,sN（1≤si,ti≤109）。

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

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

计算极大的匹配的数量模 109+7 的结果。

输入格式:

输入的第一行包含 N。

第二行包含 N 个空格分隔的整数s1,s2,…,sN。

第三行包含 N 个空格分隔的整数 t1,t2,…,tN。

输出格式:

输出极大的匹配的数量模 109+7 的结果。

样例输入:

4
1 2 3 4
1 2 2 3

样例输出:

9

提示:

以下是全部九种极大的匹配。有序对 (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-3 中，N≤8。
  • 测试点 4-12 中，N≤50。
  • 测试点 13-20 没有额外限制。
时间限制: 1000ms
空间限制: 256MB

来源: USACO 2020 DEC Platinum