TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

50.0% (1/2)

Tags

Description

前情提要

由於你的協助,提姆們進化成提姆提姆了!

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

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

Input Format

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

接下來會以數行代表一隻提姆提姆的資訊:
第一行有一個正整數$p_i$,代表這隻提姆提姆有幾種戰鬥模式(戰鬥模式由0編號到$p_i-1$);
接下來$p_i$行,每行第一個數字為非負整數$c_{ij}$,代表在第$j$種戰鬥模式中這隻提姆提姆能夠解決幾個任務;接下來有$c_{ij}$個以空白隔開的數字,代表這隻提姆提姆在這種戰鬥模式中能解決的任務編號。

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

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

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

Output Format

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

Sample Input

2 5
1
1 0
2
2 1 0
1 1

Sample Output

2
0 0
0 1

Hints

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

Problem Source

Problem Set / Description by Yihda Yol

Subtasks

For Testdata: 0 ~ 3, Score: 17
For Testdata: 0 ~ 7, Score: 13
For Testdata: 0 ~ 11, Score: 20
For Testdata: 12 ~ 15, Score: 18
For Testdata: 0 ~ 19, Score: 32
No. Time Limit (ms) Memory Limit (KiB)
0 1800 32768
1 1800 32768
2 1800 32768
3 1800 32768
4 1800 32768
5 1800 32768
6 1800 32768
7 1800 32768
8 1800 32768
9 1800 32768
10 1800 32768
11 1800 32768
12 2500 20480
13 2500 20480
14 2500 20480
15 2500 20480
16 2500 20480
17 2500 20480
18 2500 20480
19 2500 20480