A6148. 「USACO 2024.1 Platinum」Mooball Teams III
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目来自 [USACO 2024 January Contest, Platinum](http://usaco.org/index.php?page=jan24results) Problem 3. [Mooball Teams III](http://usaco.org/index.php?page=viewproblem2&cpid=1382)**
Farmer John 在他的农场上有 $N$ 头牛（$2\le N\le 2\cdot 10^5$），编号为 $1\ldots N$。奶牛 $i$ 位于整数坐标 $(x_i,y_i)$（$1\le x_i,y_i\le N$）。Farmer John 想要挑选两支队伍来玩哞球游戏！
其中一支队伍将是「红队」；另一队将是「蓝队」。对组队只有很少的要求。两队都不能为空，并且 $N$ 头奶牛中的每一头至多只能在一个队中（可以两队都不在）。唯一的其他要求是基于哞球独特的特点：一个无限长的网，必须将其放置为平面中非整数坐标的水平或垂直直线，例如 $x=0.5$。FJ 挑选队伍必须使得可以用网将两队分开。奶牛们不愿意为此进行移动。
帮帮农夫吧！为 Farmer John 计算选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。
Farmer John 在他的农场上有 $N$ 头牛（$2\le N\le 2\cdot 10^5$），编号为 $1\ldots N$。奶牛 $i$ 位于整数坐标 $(x_i,y_i)$（$1\le x_i,y_i\le N$）。Farmer John 想要挑选两支队伍来玩哞球游戏！
其中一支队伍将是「红队」；另一队将是「蓝队」。对组队只有很少的要求。两队都不能为空，并且 $N$ 头奶牛中的每一头至多只能在一个队中（可以两队都不在）。唯一的其他要求是基于哞球独特的特点：一个无限长的网，必须将其放置为平面中非整数坐标的水平或垂直直线，例如 $x=0.5$。FJ 挑选队伍必须使得可以用网将两队分开。奶牛们不愿意为此进行移动。
帮帮农夫吧！为 Farmer John 计算选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。
输入格式
输入的第一行包含一个整数 $N$。
以下 $N$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。输入保证 $x_i$ 组成 $1\ldots N$ 的一个排列，$y_i$ 类似。
以下 $N$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。输入保证 $x_i$ 组成 $1\ldots N$ 的一个排列，$y_i$ 类似。
输出格式
输出一个整数，为选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。
输入输出样例
输入 #1
2 1 2 2 1
输出 #1
2
输入 #2
3 1 1 2 2 3 3
输出 #2
10
输入 #3
3 1 1 2 3 3 2
输出 #3
12
输入 #4
40 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40
输出 #4
441563023
说明/提示
- 测试点 5：$N\le 10$。
- 测试点 6-9：$N\le 200$。
- 测试点 10-13：$N\le 3000$。
- 测试点 14-24：没有额外限制。
供题：Dhruv Rohatgi
- 测试点 6-9：$N\le 200$。
- 测试点 10-13：$N\le 3000$。
- 测试点 14-24：没有额外限制。
供题：Dhruv Rohatgi