Matrix Exponentiation - Count path

Xem dạng PDF

Gửi bài giải


Điểm: 0,40
Giới hạn thời gian: 1.5s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Matrix Exponentiation
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bạn được cho một đồ thị có hướng gồm ~n~ đỉnh và ~m~ cạnh, các đỉnh được đánh số từ ~1~ tới ~n~. Hãy đếm số đường đi có ~k~ bước (cạnh) và in ra kết quả theo modulo ~10^9 + 7~. Một đường đi có thể có ghé thăm các đỉnh và cạnh nhiều lần.

Input

  • Dòng đầu là ~3~ số nguyên ~n,\ m,\ k~ ~(1 \le n \le 100,\ 0 \le \ m \le n\cdot (n-1),\ 1 \le k \le 10^9)~ lần lượt là số đỉnh, số cạnh và số bước của đường đi.

  • ~m~ dòng tiếp theo mô tả các cạnh của đồ thị. Dòng thứ ~i~ gồm ~2~ số nguyên ~a_i,\ b_i~ ~(1 \le a_i,\ b_i \le n, a_i \neq b_i)~ thể hiện đường đi từ đỉnh ~a_i~ tới đỉnh ~b_i~. Đồ thị đã cho đảm bảo không có khuyên và mỗi cạnh không xuất hiện quá một lần.

Output

In ra một dòng chứa số đường đi thoả mãn yêu cầu input theo modulo ~1000000007~.

Sample Input 1

3 4 2
1 2
2 3
3 1
2 1

Sample Output 1

5

Sample Input 2

5 10 11
2 3
4 2
2 1
2 4
1 5
5 2
3 2
3 1
3 4
1 2

Sample Output 2

21305

Giải thích

Ở ví dụ này, ta được cho đồ thị chứa ~3~ đỉnh và ~4~ cạnh như sau:

Có ~5~ đường đi với số bước ~k = 2~:

  • ~1\rightarrow2\rightarrow1~
  • ~1\rightarrow2\rightarrow3~
  • ~2\rightarrow1\rightarrow2~
  • ~2\rightarrow3\rightarrow1~
  • ~3\rightarrow1\rightarrow2~

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.