Đường Đi Ngẫu Nhiên Trên DAG

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

Đề bài

Cho một đồ thị có hướng không chu trình (DAG) gồm $N$ đỉnh đánh số từ $1$ đến $N$ và $M$ cạnh có hướng.

Một người chơi xuất phát tại đỉnh $1$. Tại mỗi bước, nếu người chơi đang đứng ở đỉnh $u$ có bậc ra $d(u) > 0$, người chơi sẽ chọn ngẫu nhiên đều một trong $d(u)$ cạnh đi ra từ $u$ và di chuyển theo cạnh đó (mất $1$ bước). Nếu người chơi đứng ở đỉnh có bậc ra bằng $0$, trò chơi kết thúc.

Hãy tính kỳ vọng số bước đi từ khi bắt đầu tại đỉnh $1$ cho đến khi trò chơi kết thúc, theo modulo $10^9 + 7$.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$, $u \ne v$) mô tả một cạnh có hướng từ $u$ đến $v$. Dữ liệu bảo đảm đồ thị là DAG (có thể có nhiều cạnh song song giữa hai đỉnh).

Dữ liệu ra

  • In ra một số nguyên duy nhất là kỳ vọng số bước đi theo modulo $10^9 + 7$.

Ví dụ

Input
4 4
1 2
1 3
2 4
3 4
Output
2

Giải thích

Mọi đường đi từ $1$ tới đỉnh bậc ra $0$ (đỉnh $4$) đều có độ dài $2$, nên kỳ vọng bằng $2$.

Giới hạn

  • $1 \le N \le 10^5$
  • $0 \le M \le 2 \cdot 10^5$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved