Bàn Cờ Cổng Dịch Chuyển
Đề bài
Một bàn cờ gồm $N$ ô đánh số từ $1$ đến $N$. Người chơi bắt đầu ở ô $1$ và cần đi tới ô $N$.
Có $P$ cổng dịch chuyển một chiều; cổng thứ $i$ đặt tại ô $u_i$ ($1 < u_i < N$) và đưa người chơi ngay lập tức tới ô $v_i$ ($1 \le v_i \le N$, mỗi ô có tối đa một cổng và $v_i$ không có cổng).
Ở mỗi lượt, nếu chưa đứng ở ô $N$, người chơi tung một con xúc xắc đều $K$ mặt (ra các số $1, 2, \dots, K$ với xác suất $\frac{1}{K}$ mỗi mặt). Giả sử đang ở ô $x$ và tung được $d$:
- Nếu $x + d > N$, người chơi đứng yên tại $x$.
- Nếu $x + d \le N$, người chơi bước tới ô $x + d$; nếu tại $x + d$ có cổng dịch chuyển tới $v$, người chơi lập tức bị dịch chuyển tới $v$.
Hãy tính kỳ vọng số lượt tung xúc xắc để tới được ô $N$ (theo modulo $10^9 + 7$). Nếu không thể tới được ô $N$ hoặc có khả năng bị kẹt vô hạn mà không thể tới $N$, in ra -1. (Bảo đảm từ mọi ô có thể đi tới từ $1$, luôn tồn tại đường tới $N$, trừ trường hợp tổng thể không tới được $N$ thì in -1).
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, K, P$ ($2 \le N \le 100$, $1 \le K \le 6$, $0 \le P \le N - 2$).
- $P$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i$ ($1 < u_i < N$, $1 \le v_i \le N$).
Dữ liệu ra
- In ra kỳ vọng số lượt theo modulo $10^9 + 7$, hoặc
-1nếu không thể tới $N$.
Ví dụ
Input
4 2 1
3 1
Output
6
Giải thích
Từ 1 tung 1->2, tung 2->3(dịch chuyển về 1). Từ 2 tung 1->3(về 1), tung 2->4(đích). Hệ phương trình: $E[1] = 1 + \frac{1}{2} E[2] + \frac{1}{2} E[1]$, $E[2] = 1 + \frac{1}{2} E[1]$. Giải ra $E[1] = 6, E[2] = 4$.
Giới hạn
- $2 \le N \le 100$
- $1 \le K \le 6$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion