Problem : 249 - Fish

Problem Statistics

Solved Member: 7　　Submission: 64　　User Tried: 9

Statement:

據Scheherazade說，在很遠的沙漠中有一個湖。湖中起初有N條魚。選擇最值錢的K種寶石，對F條魚的每一條只餵給它一塊寶石。注意，因為K可能小於F，兩條或更多的魚可能會吞下同一種寶石。

隨著時間的流逝，有些魚吃掉了別的魚。一條魚能夠吃掉另一條魚，當且僅當它的長度是被吃掉的魚的兩倍(A 能吃掉B 當且僅當L_A >= 2 * L_B)。沒有規則說明一條魚何時會吃掉另一條魚。有的魚可能會一條接一條地吃掉幾條小魚，而有的魚可能不吃別的魚，即使它們有能力吃。當一條魚吃掉一條小魚時，它的身長並不改變，但是小魚腹中的寶石會完好無損地進到大魚腹中。

據Scheherazade說，如果你能夠找到那個湖，你會被准許捕捉一條魚，並且得到魚腹中的寶石。你很想試試運氣，但是在出發前很想知道捉到一條魚可能會有多少種不同的寶石組合。

Task:

寫一個程序，給定每條魚的長度以及其最初吞食的寶石的種類，找出魚腹中寶石不同組合的數量對給定整數M取模的值。

組合由每種寶石的數量定義，與寶石的排列順序無關。同一類寶石中任意兩塊是沒有區別的。

限制：
•1 <= F <= 500,000，湖中最初魚的數量。
•1 <= K <= F，寶石的種類。
•2 <= M <= 30,000
•1 <= L_X <= 1,000,000,000，魚X的長度。

Input:Output:

你的程序需要從標準輸入上讀入下列數據：

• 第一行是整數F, 即湖中最初魚的數量。
• 第二行是整數K, 即寶石的種類數。不同類型的寶石分別用從1 到K的整數表示。
• 第三行是整數M。
• 以後F 行中的每一行用由一個空格分隔的兩個整數描述一條魚：按順序分別是魚的長度以及魚腹中的寶石的類型。

注意: 在所有的測試用例中，K 種寶石中的每一種都會至少有一塊。

輸出你的程序需要在標準輸出上輸出一個介於0和M-1(包含)的整數，即寶石所有可能的不同組合數量模M，佔一行。

注意，在問題求解中，數值M 除了簡化計算外沒有其他的作用。

有 70 分的測試資料中 K 不超過7,000。

有 25 分的測試資料中 K 不超過20。

Sample Input:Sample Output:

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

HINT:

有11 種可能的組合，所以你需要輸出4，也就是11 模7。

這些可能的組合是: [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]: 如果你在第二條魚(或第四條) 吃掉任何其它魚之前捕捉到它。
• [1,2]: 如果第二條魚吃掉第一條魚, 它就會有一塊1 型寶石(它在初始時刻吞下的) 和一塊2型寶石(從第一條魚腹中得到的)。
• [1,2,3]: 一種可能的途徑是: 第四條魚吃掉第一條魚，然後第三條魚又吃掉它。如果你此時捉到了第三條魚，那它腹中就會有這三種寶石一樣一塊。
• [1,2,3,3]: 第四條魚吃掉第一條魚，第三條魚吃掉第四條魚，第三條魚吃掉第五條魚，你捉到了第三條魚。
• [1,3]: 第三條魚吃掉第四條魚，你捉到了第三條魚。
• [1,3,3]: 第三條魚吃掉第五條魚，第三條魚吃掉第四條魚，你捉到了第三條魚。
• [2]: 你捉到了第一條魚。
• [2,3]: 第三條魚吃掉第一條魚，你捉到了第三條魚。
• [2,3,3]: 第三條魚吃掉第一條魚，第三條魚吃掉第五條魚，你捉到了第三條魚。
• [3]: 你捉到了第三條魚。
• [3,3]: 第三條魚吃掉第五條魚，你捉到了第三條魚。

Source:

IOI 2008

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	3000ms	65536kb
1	3000ms	65536kb	5
2	3000ms	65536kb	5
3	3000ms	65536kb	5
4	3000ms	65536kb	5
5-1	3000ms	65536kb	5
5-2	3000ms	65536kb
6-1	3000ms	65536kb	5
6-2	3000ms	65536kb
7	3000ms	65536kb	5
8	3000ms	65536kb	5
9-1	3000ms	65536kb	6
9-2	3000ms	65536kb
10-1	3000ms	65536kb	6
10-2	3000ms	65536kb
10-3	3000ms	65536kb
11-1	3000ms	65536kb	6
11-2	3000ms	65536kb
11-3	3000ms	65536kb
12-1	3000ms	65536kb	6
12-2	3000ms	65536kb
13-1	3000ms	65536kb	6
13-2	3000ms	65536kb
14	3000ms	65536kb	5
15	3000ms	65536kb	5
16-1	3000ms	65536kb	5
16-2	3000ms	65536kb
17-1	6000ms	65536kb	5
17-2	6000ms	65536kb
18-1	6000ms	65536kb	5
18-2	6000ms	65536kb
18-3	6000ms	65536kb
18-4	6000ms	65536kb
19-1	6000ms	65536kb	5
19-2	6000ms	65536kb
19-3	6000ms	65536kb
19-4	6000ms	65536kb