Đấu Trường Sinh Tử
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Hai chiến binh A và B đối đầu trong đấu trường sinh tử. Chiến binh A có $A$ điểm máu, chiến binh B có $B$ điểm máu.
Trò chơi diễn ra theo từng hiệp. Trong mỗi hiệp:
- Với xác suất $p_1 = \frac{x_1}{s}$, chiến binh A đánh trúng B (máu của B giảm $1$).
- Với xác suất $p_2 = \frac{x_2}{s}$, chiến binh B đánh trúng A (máu của A giảm $1$).
- Với xác suất $p_0 = \frac{x_0}{s}$, cả hai đều đánh trượt (máu không đổi).
Trong đó $s = x_1 + x_2 + x_0$, với $x_1 + x_2 > 0$. Trò chơi kết thúc ngay khi một trong hai chiến binh có máu bằng $0$.
Hãy tính kỳ vọng số hiệp đấu cho đến khi trò chơi kết thúc, theo modulo $10^9 + 7$.
Dữ liệu vào
- Một dòng duy nhất chứa năm số nguyên $A, B, x_1, x_2, x_0$ ($1 \le A, B \le 2000$, $0 \le x_1, x_2, x_0 \le 10^6$, $x_1 + x_2 > 0$).
Dữ liệu ra
- In ra một số nguyên duy nhất là kỳ vọng số hiệp đấu theo modulo $10^9 + 7$.
Ví dụ
Input
1 1 1 1 1
Output
500000005
Giải thích
$p_1 = p_2 = p_0 = 1/3$. Khi máu là $(1, 1)$, xác suất kết thúc trong 1 hiệp là $2/3$, nên kỳ vọng là $\frac{3}{2} \equiv 500000005 \pmod{10^9+7}$.
Giới hạn
- $1 \le A, B \le 2000$
- $0 \le x_1, x_2, x_0 \le 10^6$, $x_1 + x_2 > 0$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion