TopCoder

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

User's AC Ratio

100.0% (53/53)

Submission's AC Ratio

54.6% (142/260)

Tags

Description

在某個小島上,有 $n$ 個城市(編號為 $0$ 到 $n-1$)用 $m$ 條單向道路連結。然而為了疏運,從一個城市出發到另一個城市之間可能會連有許多條單向道路,也可能會有從某個城市出發回到同一個城市的道路(這樣才不會塞車塞得太無聊)。

冥銋,剛當上警察,意氣風發的程式設計師(咦),正試圖分析著小島上搶劫案經過的模式。為此,他找來了 $Q$ 起已偵結的搶劫案,試圖從中摸索出一個搶劫犯應該會具有的紳士風度。然而這些紀錄並不完全,只記錄了 $(a_i, b_i)$,其中 $a_i$ 是搶劫案發生的城市,$b_i$ 是搶匪遭到逮捕的城市,而且這些搶案有個共同之處:搶匪在逃亡過程經過的邊數皆恰為$L$(如果某條邊被經過多次,那麼他對 $L$ 的貢獻會重複計算)。冥銋想要走過所有可能的路徑,但是憑他一己之力實在很難在短時間內暴搜完所有可能路徑。好險,身為一個程式設計師,他還會「多重影分身之術」(一種將多執行緒實現於現實(?)的演算法),所以可以同時探索多條路徑。

然而,要知道,「多重影分身之術」是非常消耗查克拉…呃…我是說…CPU的。所以冥銋想製造出和路徑可能總數一樣多的影分身,讓他可以在最短的時間耗最少的CPU完成他的任務。雖然他是一名很厲害的程式設計師,不過他還必需要準備多重影分身之術的執行,所以他將計算出路徑可能總數的任數交給了你。

Input Format

第一行含有四個正整數 $n\leq 150,m\leq 10^ 6,Q\leq 20000, L\leq 10^ 9$,代表城市個數,單向道路個數、案件個數以及過程中搶匪經過的邊數(重複計算)。
接下來的 $m$ 行,每行含有兩個整數 $0\leq s_i, e_i\leq n-1$,代表有一條道路從第 $s_i$ 號城市到第 $e_i$ 城市。
接下來的 $Q$ 行,每行含有兩個整數 $0\leq a_i, b_i \leq n-1$,分別代表這起搶劫案的發生地點以及搶匪落網的地點。

子任務(測資) 額外限制 分數
1 (0~2) $L\leq 30$ 40
2 (0~4) 無限制 60

Output Format

對於每起搶案,請輸出可能路徑的個數。由於答案可能很大,請將答案模 1000000009 後輸出。

Sample Input 1

4 7 2 2
0 1
1 2
0 3
3 2
0 2
0 2
0 0
0 2
2 0

Sample Output 1

4
0

Hints

對於第一種案件:
0→1→2一種
0→3→2一種
0→0→2兩種

Problem Source

Problem set / Description by Paupière

Subtasks

No. Testdata Range Score
1 0~2 40
2 0~4 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2
1 1000 65536 262144 1 2
2 1000 65536 262144 1 2
3 1500 65536 262144 2
4 1500 65536 262144 2