1985 . 提姆提姆

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

50.0% (1/2)

Tags

DP

Description

前情提要。

由於你的協助，提姆們進化成提姆提姆了！

雖然提姆提姆是由提姆進化來的，但是它們實際上有很大的差別。提姆提姆擁有更強的能力，可以切換成許多種不同的戰鬥模式，每種戰鬥模式能解決的敵人類型都不同。但是提姆提姆不喜歡團隊合作，它們喜歡單打獨鬥。
小向有N隻提姆提姆，理所當然地，她準備了N個不同的任務，由0編號到N−1，希望N隻提姆提姆每隻各解決一個任務，把這N個任務全部完成。然而因為提姆提姆們的戰鬥模式實在是太多了，小向不知道要怎麼安排任務會比較好。

於是小向找到了你。現在給你一堆提姆提姆、一堆任務，還有提姆提姆們在不同模式下能夠解決的任務列表，請你幫小向找到一種安排任務的方法，順便算一下小向總共有幾種不同的方法安排任務。
喔對了，由於安排任務的方法數可能是凡人無法理解的魔法數字，你只要計算答案模109+9的餘數就好了。
（一隻提姆提姆用不同戰鬥模式解決同一個任務要算是不同的安排。）

Input Format

第一行有兩個正整數N,sub，分別代表提姆提姆的數量與子任務編號。

接下來會以數行代表一隻提姆提姆的資訊：
第一行有一個正整數pi，代表這隻提姆提姆有幾種戰鬥模式（戰鬥模式由0編號到pi−1）；
接下來pi行，每行第一個數字為非負整數cij，代表在第j種戰鬥模式中這隻提姆提姆能夠解決幾個任務；接下來有cij個以空白隔開的數字，代表這隻提姆提姆在這種戰鬥模式中能解決的任務編號。

這個格式會重複N次，直到所有提姆提姆都被描述完畢為止。

以下以C代表提姆提姆的戰鬥模式數量上限。
對於所有測資，N≤24,C≤1000。保證一定有方法可以安排任務。

子任務（測資） 額外限制 分數
1 (0~3) N,C≤10 17
2 (0~7) N,C≤15 13
3 (0~11) N≤20 20
4 (12~15) 無限制；方法數量錯誤不影響得分 18
5 (0~19) 無限制 32

Output Format

第一行輸出一個數字，代表安排任務的方法數模109+9的餘數。
接下來N行，請輸出一種可行的安排方法。每行輸出兩個非負整數pi,qi，代表這隻提姆提姆應該用第pi種戰鬥模式完成第qi個任務。輸出的提姆提姆順序需與輸入順序相同。

Sample Input 1

2 5
1
1 0
2
2 1 0
1 1

Sample Output 1

2
0 0
0 1

Hints

範例測資中，由於第一隻提姆提姆必須做編號0的任務，因此第二隻只能做編號1的任務；而第二隻可以用兩種不同的戰鬥模式做編號1的任務。

Problem Source

Problem Set / Description by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~3 17
2 0~7 13
3 0~11 20
4 12~15 18
5 0~19 32

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1800 32768 262144 1 2 3 5
1 1800 32768 262144 1 2 3 5
2 1800 32768 262144 1 2 3 5
3 1800 32768 262144 1 2 3 5
4 1800 32768 262144 2 3 5
5 1800 32768 262144 2 3 5
6 1800 32768 262144 2 3 5
7 1800 32768 262144 2 3 5
8 1800 32768 262144 3 5
9 1800 32768 262144 3 5
10 1800 32768 262144 3 5
11 1800 32768 262144 3 5
12 2500 20480 262144 4 5
13 2500 20480 262144 4 5
14 2500 20480 262144 4 5
15 2500 20480 262144 4 5
16 2500 20480 262144 5
17 2500 20480 262144 5
18 2500 20480 262144 5
19 2500 20480 262144 5
Submit
Back to Top