Khử Gauss Trên Đồ Thị
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một đồ thị vô hướng liên thông gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $M$ cạnh (không có khuyên, không có cạnh song song).
Một chú chuột bắt đầu ở đỉnh $1$ và muốn chạy tới đỉnh $N$. Ở mỗi bước, nếu chưa đứng ở đỉnh $N$, chuột chọn ngẫu nhiên đều một trong các đỉnh kề với đỉnh hiện tại và di chuyển tới đó (mất $1$ bước). Khi tới đỉnh $N$, chuột dừng lại.
Hãy tính kỳ vọng số bước chuột cần đi để tới được đỉnh $N$, theo modulo $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($2 \le N \le 100$, $N - 1 \le M \le \frac{N(N-1)}{2}$).
- $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ủa đồ thị.
Dữ liệu ra
- In ra một số nguyên duy nhất là kỳ vọng số bước cần tìm theo modulo $10^9 + 7$.
Ví dụ
Input
3 3
1 2
2 3
1 3
Output
2
Giải thích
Trong tam giác đầy đủ, từ $1$ sang $3$ trực tiếp (xác suất $1/2$) hoặc sang $2$ (xác suất $1/2$). Ta có $E[1] = 1 + \frac{1}{2} E[2]$ và $E[2] = 1 + \frac{1}{2} E[1]$, giải ra $E[1] = E[2] = 2$.
Giới hạn
- $2 \le N \le 100$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion