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

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 (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