Lưới Ô Vuông Xác Suất
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một bảng lưới kích thước $H \times W$ (các hàng đánh số từ $1$ đến $H$, các cột đánh số từ $1$ đến $W$). Một người chơi bắt đầu ở ô $(1, 1)$ và muốn đi tới ô $(H, W)$.
Tại mỗi ô $(i, j) \ne (H, W)$, mỗi bước đi mất $1$ giây và người chơi sẽ:
- Đi sang phải tới $(i, j+1)$ với xác suất $p_R$,
- Đi xuống dưới tới $(i+1, j)$ với xác suất $p_D$,
- Ở lại ô $(i, j)$ với xác suất $p_S = 1 - p_R - p_D$.
Các xác suất tại ô $(i, j)$ được cho qua ba số nguyên không âm $a_{i,j}, b_{i,j}, c_{i,j}$ với tổng $s = a_{i,j} + b_{i,j} + c_{i,j} > 0$, trong đó $p_R = \frac{a_{i,j}}{s}$, $p_D = \frac{b_{i,j}}{s}$, $p_S = \frac{c_{i,j}}{s}$. Bảo đảm $a_{i,j} + b_{i,j} > 0$ tại mọi ô khác $(H, W)$, $a_{i,W} = 0$ với mọi $i$, và $b_{H,j} = 0$ với mọi $j$.
Hãy tính kỳ vọng số giây để đi từ $(1, 1)$ tới $(H, W)$, theo modulo $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $H, W$ ($1 \le H, W \le 500$).
- Tiếp theo là $H \times W$ bộ ba số nguyên $(a_{i,j}, b_{i,j}, c_{i,j})$ ($0 \le a_{i,j}, b_{i,j}, c_{i,j} \le 10^4$), mô tả từng hàng từ $1$ đến $H$, mỗi hàng gồm $W$ bộ ba. Tại $(H, W)$, bộ ba luôn là
0 0 1.
Dữ liệu ra
- In ra một số nguyên duy nhất là kỳ vọng số giây cần tìm theo modulo $10^9 + 7$.
Ví dụ
Input
2 2
1 1 2 0 1 1
1 0 1 0 0 1
Output
4
Giải thích
- Tại $(1, 2)$: $p_D = 1/2, p_S = 1/2 \Rightarrow E[1][2] = 2$.
- Tại $(2, 1)$: $p_R = 1/2, p_S = 1/2 \Rightarrow E[2][1] = 2$.
- Tại $(1, 1)$: $p_R = 1/4, p_D = 1/4, p_S = 1/2 \Rightarrow \frac{1}{2} E[1][1] = 1 + \frac{1}{4}(2) + \frac{1}{4}(2) = 2 \Rightarrow E[1][1] = 4$.
Giới hạn
- $1 \le H, W \le 500$
- $0 \le a_{i,j}, b_{i,j}, c_{i,j} \le 10^4$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion