시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 214 | 51 | 46 | 34.074% |
취미로 게임 만드는 걸 좋아하는 현욱은 오늘 간단한 게임 기획을 하나 떠올렸다. 현욱이 생각한 게임에는 N개의 레벨이 있는데, 각 레벨을 클리어하면 플레이어는 일정량의 점수를 획득할 수 있다. 또, 각 레벨은 클리어 후 진행할 수 있는 다음 레벨이 몇 종류 정해져있고, 플레이어는 그 레벨들 중 하나를 골라 해당 레벨로 진행할 수 있다.
현욱이 만든 게임의 기획을 요약하면 다음과 같다.
현욱은 기획을 끝내고 나서 문득, 위의 조건을 만족하는 레벨 배치를 얼마나 다양하게 만들 수 있을 지 궁금해졌다. 현욱을 도와 주어진 Si, Ki 수치 조건을 만족하게 모든 레벨을 배치할 수 있는 경우의 수를 모두 구하는 프로그램을 작성해보자.
첫 줄에 레벨의 개수 N(1 ≤ N ≤ 3 × 105)이 주어진다. 둘째 줄에 각 레벨에 대한 Si(1 ≤ Si ≤ 109)가 주어진다. 셋째 줄에 각 레벨에 대한 Ki(1 ≤ Ki ≤ 109)가 주어진다.
첫째 줄에 주어진 Si, Ki값을 만족하게 레벨을 배치할 수 있는 경우의 수를 109 + 7로 나눈 나머지를 출력한다. 각 레벨 배치에서 모든 레벨에 대해, 그 레벨을 클리어한 후 진행할 수 있는 다음 레벨 목록이 동일하다면(순서는 상관 없음), 두 배치는 동일한 배치로 생각한다.
3 2 6 4 2 8 6
1
3 2 1 3 2 3 4
0
첫 번째 입력에서, 조건을 만족하는 배치는 시작 레벨이 1레벨이고, 1레벨을 클리어한 후 2,3레벨 중 하나를 골라 진행할 수 있는 배치 하나 밖에 없다. 두 번째 입력에서 조건을 만족하게 배치할 수 있는 방법은 존재하지 않는다.
Contest > BOJ User Contest > 소프트콘 > 제1회 소프트콘 C번