Khử Gauss Trên Đồ Thị

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

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