Đấu Trường Sinh Tử

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

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