Robot Dò Tìm Địa Chất Trên Sườn Núi
Đề bài
Một robot tự hành khảo sát địa chất trên sườn núi chia thành lưới $R \times C$ ô, xuất phát từ ô $(1, 1)$ và hướng tới trạm thu hồi tại ô $(R, C)$. Tại mỗi ô $(i, j)$, robot thu được mẫu khoáng sản có giá trị $V_{i,j}$. Nếu đang ở hàng cuối $R$, robot bắt buộc đi sang phải $(i, j+1)$; nếu đang ở cột cuối $C$, robot bắt buộc đi xuống dưới $(i+1, j)$. Tại các ô còn lại, robot chọn đi sang phải với xác suất $P_{i,j} / 100$ và đi xuống dưới với xác suất $(100 - P_{i,j}) / 100$. Hãy tính kỳ vọng tổng giá trị khoáng sản thu được trên hành trình từ $(1, 1)$ đến $(R, C)$ theo modulo $10^9 + 7$.
Dữ liệu vào
Dòng 1 gồm hai số nguyên $R, C$ ($1 \le R, C \le 300$). $R$ dòng tiếp theo, mỗi dòng gồm $C$ số nguyên $V_{i,j}$ ($0 \le V_{i,j} \le 10^6$). $R$ dòng tiếp theo, mỗi dòng gồm $C$ số nguyên $P_{i,j}$ ($0 \le P_{i,j} \le 100$).
Dữ liệu ra
In ra kỳ vọng tổng giá trị khoáng sản theo modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 2 2 1 2 3 4 50 0 0 0 |
500000011 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion