레이팅 미적용농부 존의 농장에는 \(1 \dots N\)의 번호가 붙은 소 \(N\)마리 (\(2 \leq N \leq 2\cdot 10^5\))가 있다. 소 \(i\)는 정수 좌표 \((x_i, y_i)\) (\(1\le x_i,y_i\le N\))에 있다. 농부 존은 무볼(mooball) 경기를 위해 두 팀을 뽑으려 한다!
한 팀은 "빨간" 팀, 다른 팀은 "파란" 팀이다. 팀 구성 조건은 몇 가지뿐이다. 어느 팀도 비어 있으면 안 되고, \(N\)마리의 소 각각은 최대 한 팀에만 속해야 한다 (어느 팀에도 속하지 않을 수 있다). 나머지 유일한 조건은 무볼만의 독특한 특징에서 나온다. 바로 무한히 긴 네트인데, 네트는 \(x = 0.5\)처럼 정수가 아닌 좌표에서 평면상의 수평선 또는 수직선으로 놓아야 한다. 농부 존은 네트로 두 팀을 분리할 수 있도록 팀을 뽑아야 한다. 소들은 이를 위해 이동해 줄 생각이 없다.
농부를 도와주자! 위 조건을 만족하도록 빨간 팀과 파란 팀을 뽑는 경우의 수를 \(10^9+7\)로 나눈 나머지로 농부 존에게 알려 주자.
출제: Dhruv Rohatgi
배점
- 입력 5: \(N\le 10\)
- 입력 6-9: \(N\le 200\)
- 입력 10-13: \(N\le 3000\)
- 입력 14-24: 추가 제약 없음.
출제: Dhruv Rohatgi
입력의 첫째 줄에 정수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각각 공백으로 구분된 두 정수 \(x_i\)와 \(y_i\)가 주어진다. \(x_i\)들이 \(1\dots N\)의 순열을 이루고, \(y_i\)들도 마찬가지임이 보장된다.
위 조건을 만족하도록 빨간 팀과 파란 팀을 뽑는 경우의 수를 \(10^9+7\)로 나눈 나머지로 나타낸 정수 하나를 출력한다.
2
1 2
2 12We can either choose the red team to be cow 1 and the blue team to be cow 2, or
the other way around. In either case, we can separate the two teams by a net
(for example, \(x=1.5\)).
3
1 1
2 2
3 310Here are all ten possible ways to place the cows on teams; the \(i\)th character
denotes the team of the \(i\)th cow, or . if the \(i\)th cow is not on a team.
RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR
3
1 1
2 3
3 212Here are all twelve possible ways to place the cows on teams:
RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR
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 40441563023Make sure to output the answer modulo \(10^9+7\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Platinum