시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 158 | 51 | 36 | 39.130% |
N명이 한 채팅 프로그램에서 대화 중에 있다. 이 채팅 프로그램은 각 메시지마다 누가 보냈는지, 그 메시지를 N명 중에서 몇 명이 읽지 않았는지 알려준다.
이 채팅 프로그램은 읽지 않은 사람 수를 업데이트할 때 다음과 같은 규칙을 따른다:
모든 메시지의 발신자와 안 읽은 사람의 수를 알고 있는 호준이는 각각 누가 어디부터 메시지를 읽지 않았는지를 따져 보고, 가능한 경우의 수가 몇 가지가 있는지 알아보려고 한다. 여기서 두 경우가 다르다는 뜻은, 어떤 메시지에 대해서 메시지를 읽은 사람의 집합이 각각의 경우에서 다르다는 것을 의미한다.
예를 들어, 이 채팅 프로그램에 4명이 참여 중이고, 차례대로 두 개의 메시지가 각각 1번, 2번 사람이 보냈으며, 각각 1명, 2명이 읽지 않았다고 하면
의 4가지가 가능하다.
호준이는 이 경우의 수가 매우 큰 값이 나올 수 있다는 걸 깨달았기에, 경우의 수를 109+7로 나눈 나머지를 구하려고 한다. 호준이를 도와주자.
첫 번째 줄에 두 정수 N과 M이 공백으로 구분되어 입력된다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000)
두 번째 줄부터 M개의 줄에 걸쳐 각 메시지에 대한 정보인 두 정수 a, b가 공백으로 구분되어 입력된다. 메시지는 시간 순서대로이며, 생략된 메시지는 없다고 가정한다. a는 어떤 사람이 이 메시지를 보냈는지, b는 그 메시지를 읽지 않은 사람이 몇 명인지를 나타낸다. (1 ≤ a ≤ N, 0 ≤ b < N)
첫 번째 줄에 누가 읽지 않았는지 가능한 경우의 수를 109+7로 나눈 나머지를 출력하라.
4 2 1 1 2 2
4
4 3 1 2 2 3 3 3
0
불가능한 경우에는 가능한 경우의 수가 0이므로 0을 출력한다.
3 2 1 0 2 0
1
모든 사람이 모든 메세지를 읽은 한 가지 경우만 가능하다.
University > 성균관대학교 > 2019 Overflow Programming Contest (OPC) F번