IOI 2008 day1 3- 물고기(Fish) > 문제은행 : 정보올림피아드&알고리즘




2672 : 물고기(Fish)

제한시간
3000 ms   
메모리제한
64 MB   
해결횟수
6 회   
시도횟수
13 회   

문제

아라비안나이트를 들려 준 셰에라자드 왕비의 이야기에 따르면, 어떤 사막의 한복판엔 호수가 하나 있었다고 한다.

원래 이 호수에는 F 마리의 물고기가 살았다.

그리고 이 땅에서 가장 귀중한 보석들이 K 종류 선정되어 모든 물고기들이 이 보석을 한 덩이씩 삼켰다.

K의 값은 F보다 작을 수 있기 때문에 동일한 종류의 보석을 두 마리 이상의 물고기가 먹었을 수도 있다.


시간이 흐르면서 어떤 물고기는 다른 물고기를 잡아먹기도 했다.

물고기는 몸길이가 자신의 절반 이하인 것만 잡아먹을 수 있다. (물고기 A가 물고기 B를 잡아먹기 위해서는 LA ≥ 2×LB여야만 한다.)

물고기가 언제 다른 물고기를 잡아먹는지에 대해서는 특별한 규칙이 없다.

어떤 물고기는 자기보다 충분히 작은 물고기들을 수차례 잡아먹었을 수 있으나,

어떤 물고기는 다른 물고기를 잡아먹을 수 있는데도 그렇게 하지 않았을 수도 있다.

다른 물고기를 잡아먹은 물고기는 몸길이는 변하지 않으나, 잡아먹힌 물고기의 뱃속에 있던 보석을 자기 뱃속에 고스란히 갖고 있게 된다.


모든 물고기에 보석이 들어있는 이 호수를 찾아낼 수만 있다면 당신은 물고기를 잡아 뱃속의 모든 보석을 차지할 수 있다고 셰에라자드 왕비는 말했다.

이제 당신의 운을 시험할 때가 온 것이다.

하지만 호수를 찾아 긴 여행을 떠나기에 앞서, 당신은 물고기를 하나 잡았을 때 얻을 수 있는 보석들의 조합 가짓수가 얼마나 존재할지 알고 싶어 한다.


물고기들의 몸길이와 초창기에 이들이 하나씩 삼킨 보석들의 종류 수를 입력 받아,

물고기를 아무거나 하나 잡았을 때 이 물고기의 뱃속에 있을 수 있는 보석의 조합 가짓수를 찾아서

이 값을 어떤 정수 M으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

 

한 조합이란 K개의 종류별 보석 개수만으로 구성된다. 보석을 얻은 순서라든가, 종류가 같은 두 보석끼리는 구분을 하지 않는다.


이 M이라는 수는 문제 풀이를 더 쉽게 해 주기 위해 있는 것으로, 다른 의미는 없음을 밝힌다.

 


입력형식

첫째 줄에는 최초에 호수에 들어있던 물고기의 개체 수 F가 들어있다. (1≤F≤500,000)

둘째 줄에는 보석의 종류 수 K가 들어있다. (1≤K≤F) 보석의 종류를 식별하는 번호는 1 이상 K 이하의 범위에 드는 정수이다.

셋째 줄에는 정수 M이 있다. (2≤M≤30,000)

다음 F개의 줄에는 각 물고기의 몸길이와 자신이 초기에 삼킨 보석의 종류 번호가 공백을 사이에 두고 들어있다. (1≤Lx≤1,000,000,000) 모든 종류의 보석이 최소한 한 물고기 이상의 뱃속에는 들어있으며, 1부터 K 중 존재하지 않는 보석은 없다고 가정해도 된다.


출력형식

0 이상 M-1 이하의 범위에 있는 정수 하나를 출력한다. 보석들의 모든 조합 가짓수를 M으로 나눈 나머지의 값이다.


입력 예

5
3
7
2 2
5 1
8 3
4 1
2 3

출력 예

4

Hint!

위의 입력에 대한 가능한 조합 가짓수는 11이기 때문에, 이를 7로 나눈 나머지인 4를 출력하면 된다. 그 조합을 나열하면 다음과 같다. [1] [1,2] [1,2,3] [1,2,3,3] [1,3] [1,3,3] [2] [2,3] [2,3,3] [3] [3,3] (각 숫자 하나가 물고기 배에 있는 보석을 뜻한다. 가령 [2,3,3]은 2번 보석 하나와 3번 보석 두 개를 가리킴.)

[1]: 2번이나 4번




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP