레이팅 미적용농부 존에게는 크기가 제각각인 소 \(N\)마리\((1 \le N \le 3000)\)가 있다. 그는 원래 각 소에게 맞춤형 외양간을 지어 주었지만, 이제 일부 소들은 자라서 자기 외양간에 들어가지 못하게 되었다. 구체적으로, 농부 존은 원래 크기가 \(t_1,t_2,\ldots,t_N\)인 외양간 \(N\)개를 지었고, 소들의 현재 크기는 \(s_1,s_2,\ldots,s_N\)이다(\(1\le s_i,t_i\le 10^9\)).
매일 밤 소들은 잠잘 외양간을 찾는 의식을 치른다. 소 \(i\)는 외양간 \(j\)에 들어갈 수 있을 때(\(s_i\le t_j\)), 그리고 그때에만 외양간 \(j\)에서 잘 수 있다. 각 외양간에는 최대 한 마리의 소만 들어갈 수 있다.
소와 외양간의 매칭이 극대(maximal)라는 것은, 외양간에 배정된 모든 소가 그 외양간에 들어갈 수 있고, 배정되지 않은 모든 소가 매칭에서 빠진 빈 외양간 어느 곳에도 들어갈 수 없는 경우를 말한다.
극대 매칭의 개수를 \(10^9 + 7\)로 나눈 나머지를 구하시오.
문제 제공: Nick Wu
배점
- 테스트 케이스 2-3에서는 \(N\le 8\)이다.
- 테스트 케이스 4-12에서는 \(N\le 50\)이다.
- 테스트 케이스 13-20에서는 추가 제약이 없다.
문제 제공: Nick Wu
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 공백으로 구분된 \(N\)개의 정수 \(s_1,s_2,\ldots,s_N\)이 주어진다.
셋째 줄에 공백으로 구분된 \(N\)개의 정수 \(t_1,t_2,\ldots,t_N\)이 주어진다.
극대 매칭의 개수를 \(10^9 + 7\)로 나눈 나머지를 출력한다.
4
1 2 3 4
1 2 2 39Here is a list of all nine maximal matchings. An ordered pair \((i,j)\) means that
cow \(i\) is assigned to barn \(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)
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > December > Platinum