Bài tập | NEU OJ

Cho đồ thị có hướng với $n$ đỉnh, biểu diễn bằng ma trận kề $A$ ( $A_{ij}=1$ nếu có cung từ $i$ tới $j$ ). Số đường đi (đi lại cạnh, lặp đỉnh được phép) độ dài đúng $k$ từ đỉnh $s$ tới đỉnh $t$ chính là phần tử $(s,t)$ của ma trận $A^k$ .

Cho ma trận kề, $k$ , và cặp $(s,t)$ , hãy tính số đường đi độ dài $k$ từ $s$ tới $t$ , lấy $\bmod (10^9+7)$ .

Định dạng đầu vào:
Dòng đầu chứa $n$ và $k$ . $n$ dòng tiếp theo, mỗi dòng $n$ số mô tả ma trận kề. Dòng cuối chứa $s$ và $t$ (đánh số từ $1$ ).
Ràng buộc đầu vào:
$1 \le n \le 60$ , $0 \le k \le 10^9$ , $1 \le s,t \le n$ .
Định dạng đầu ra:
Một số nguyên là số đường đi độ dài $k$ từ $s$ tới $t$ $\bmod (10^9+7)$ .

solution

Đề bài: [Toán rời rạc] Đếm đường đi độ dài k bằng lũy thừa ma trận kề