NTUCPC Speed Run! #1 NTUCPC Speed Run! #1 將於 2024-10-05 14:00 ~ 17:00 舉行
APCSCamp 海量題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
APCSCamp 海量題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
831 . 路徑數
TopCoder
Description
給定一張 $N$ 個點 $M$ 條邊的有向圖，請問有幾種從點 1 出發到點 $N$ 的路徑，且剛好經過 $K$ 條邊？由於數量可能很多，請輸出該數除以 $10^ 9 + 7$ 後的餘數。
兩條路徑若存在一個 $i$ 使得路徑的第 $i$ 條邊不一樣，則兩條路徑是不同的。注意路徑是可以經過重複的點或邊的。
Input Format
輸入第一行有三個正整數 $N, M, K$，分別代表節點數量、邊的數量以及所需路徑的長度。
接下來的 $M$ 行每行有兩個正整數 $u, v$，代表有一條從節點 $u$ 到節點 $v$ 的有向邊。
- $2 \leq N \leq 100$
- $0 \leq M \leq N^ 2$
- $1 \leq K \leq 10^ {18}$
- $1 \leq u, v \leq N$
- 保證圖沒有重邊
Output Format
輸出一行一個整數，代表從節點 1 到節點 $N$ 長度為 $K$ 的路徑數量，除以 $10^ 9 + 7$ 後的餘數。
Sample Input 1
4 5 2
1 2
2 3
3 4
4 1
2 4
1 2
2 3
3 4
4 1
2 4
Sample Output 1
1
Sample Input 2
4 9 56562
1 4
4 4
1 1
4 2
2 2
2 1
2 3
3 2
3 1
1 4
4 4
1 1
4 2
2 2
2 1
2 3
3 2
3 1
Sample Output 2
184918815
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~21 | 無額外限制 | 100 |