傳說,從前有一個人,他姓「羅」,但是又冠母姓「龔」(可能是i度空間的習俗),全名是:
你沒看錯,他的全名寫起來總共有153劃!因為實在是太難寫了,每次考試他還沒寫完姓名,別人就已經交卷了。
他覺得很不高興,恰好他聽說有一種樂器叫做「環保革胡」。這種樂器非常環保,不像每次考試寫名字一樣浪費墨水,所以他決定去欣賞這種樂器的演奏會。
到了演奏會,才發現原來環保革胡源自於一種中國傳統樂器叫做革胡。中國政府為了讓13億人都驚呆,籌組了一個13億人的樂團,可是龔羅Biángbiáng眼睛不好、數學也不好,他把總人數數成了G人。
(註:以上「13億」是一個虛數。)
因為他覺得G人樂團實在是太壯觀了,他決定認真聽這場演奏會,其中有一個樂段吸引了它的注意。
他發現在這個樂段當中,對於任兩個樂團成員的旋律,都會有「和諧」或「不和諧」其中一種關係。
龔羅Biángbiáng決定用演奏會發的問卷把每兩個樂團成員旋律的關係記下來。但是他的聽寫能力很弱,一次只能判斷一對旋律的關係。(事實上,他並沒有通過「瘋狂聽寫考試」。)
很不幸的,在他還沒有記錄完樂段中所有的關係時,這個樂段已經結束了。
不幸中的大幸是,他的樂理還不弱,知道「國樂基本定理」的表述:
一、考慮任兩個樂團成員的旋律A, B,A, B和諧若且唯若B, A和諧。(又稱國樂交換律)
二、考慮任三個樂團成員的旋律A, B, C,那麼A, B、B, C、C, A三對關係中,不和諧的對數必須是零對或兩對。
龔羅Biángbiáng對自己聽寫的結果非常有信心,因此他相信如果他記錄的結果違反了「國樂基本定理」,那創作這首「環保革胡協奏曲」的人一定是濫竽充數,連這麼基本的定理都不知道。
但是如果記錄的結果沒有違反「國樂基本定理」,他也想要知道,對於他沒有記錄下來的關係當中,有幾種不同的安排方法(也就是對每一對未知的關係都安排「和諧」或「不和諧」),使得最後的結果會滿足「國樂基本定理」。
第一行有兩個正整數$N, M \leq 10^ 6$,分別代表實際上樂團中有幾個人(編號為0~N-1),以及龔羅Biángbiáng總共記錄了幾對結果。
接下來有$M$行,每一行有三個非負整數$A_i, B_i, D_i$。
如果$D_i=0$,代表編號$A_i, B_i$的人的旋律互相不和諧;
如果$D_i=1$,代表編號$A_i, B_i$的人的旋律互相和諧。
保證$A_i<B_i$且紀錄不會重複。
子任務(測資) | 額外限制 | 分數 |
1 (0~3) | $N, M \leq 15$ | 13 |
2 (0~7) | $N, M \leq 500$ | 30 |
3 (9~10) | $M \leq 5\times 10^ 5$ | 21 |
4 (0~11) | 無限制 | 36 |
如果龔羅Biángbiáng記錄的結果違反了「國樂基本定理」,請輸出一行0;
否則請輸出一行非負整數,代表不違反「國樂基本定理」的關係安排方法總數。因為答案可能很大,你只要輸出答案$\mod 10^ 9+7$的結果就可以了。
範例測資的唯一解是1, 3和諧、0, 2不和諧。
Problem set / Description by Yihda Yol
建國中學105學年度校內第二次模擬賽 pB
No. | Testdata Range | Score |
---|---|---|
1 | 0~3 | 13 |
2 | 0~7 | 30 |
3 | 9~10 | 21 |
4 | 0~11 | 36 |