Mooball Teams III

题目描述

农夫约翰的农场里有 $N$ 头奶牛（$2 \leq N \leq 2\cdot 10^5$），方便起见编号为 $1\dots N$。奶牛 $i$ 位于整点坐标 $(x_i, y_i)$（$1\le x_i,y_i\le N$）。农夫约翰想为一场 mooball 游戏挑选两支队伍！

其中一支队伍是“红队”，另一支队伍是“蓝队”。对队伍只有一些要求：两支队伍都不能为空，并且 $N$ 头奶牛中每头最多只能加入一支队伍（也可能两队都不加入）。唯一的其他要求来自 mooball 的一个独特设定：一张无限长的网，必须在平面中以水平线或竖直线的形式放置在非整数坐标处，例如 $x = 0.5$。农夫约翰必须选择队伍，使得存在一张网可以把两队分隔开。奶牛不愿意移动来满足这一点。

请帮帮农夫！计算满足上述要求的选择红队与蓝队的方案数，并对 $10^9+7$ 取模。

输入格式

第一行输入一个整数 $N$。 接下来 $N$ 行每行包含两个用空格分隔的整数 $x_i$ 和 $y_i$。保证所有 $x_i$ 构成 $1\dots N$ 的一个排列，$y_i$ 也同样构成 $1\dots N$ 的一个排列。

输出格式

输出一个整数，表示满足上述要求的选择红队与蓝队的方案数，并对 $10^9+7$ 取模。

2
1 2
2 1

2

3
1 1
2 2
3 3

10

3
1 1
2 3
3 2

12

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

441563023

提示

我们可以选择红队为奶牛 1、蓝队为奶牛 2，或者反过来。在两种情况下，都可以用一张网将两队分开（例如 $x=1.5$）。 这里给出了将奶牛分配到队伍的全部十种可能方式；第 $i$ 个字符表示第 $i$ 头奶牛所在的队伍，或者用 . 表示第 $i$ 头奶牛不在任何队伍中。 RRB R.B RB. RBB .RB .BR BRR BR. B.R BBR 这里给出了将奶牛分配到队伍的全部十二种可能方式： RRB R.B RBR RB. RBB .RB .BR BRR BR. BRB B.R BBR 请确保输出对 $10^9+7$ 取模后的答案。 评分： Input 5: $N\le 10$ Inputs 6-9: $N\le 200$ Inputs 10-13: $N\le 3000$ Inputs 14-24: 无额外限制。 题目署名：Dhruv Rohatgi

标签: USACO|2024|Platinum

来源

USACO|2024|Platinum