Đường Đi Ngẫu Nhiên Trên DAG
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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
Community Discussion