Bàn Cờ Cổng Dịch Chuyển

Buổi 51 — Probability DP
Points
70
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions

Đề 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 -1 nế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
Draft saved