Bước Đi Ngẫu Nhiên Trên Trục Số

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

Đề bài

Trên trục số có các vị trí nguyên từ $0$ đến $n$. Một chú robot bắt đầu tại vị trí $x$ ($0 < x < n$).

Ở mỗi bước, nếu robot chưa chạm tới vị trí $0$ hoặc $n$, nó sẽ bước sang phải $1$ đơn vị ($+1$) với xác suất $p = \frac{u}{v}$, hoặc bước sang trái $1$ đơn vị ($-1$) với xác suất $1 - p$. Nếu robot chạm tới $0$ hoặc $n$, quá trình dừng lại ngay lập tức.

Hãy tính xác suất để robot chạm tới vị trí $n$ trước khi chạm tới vị trí $0$, theo modulo $10^9 + 7$.

Dữ liệu vào

  • Một dòng duy nhất chứa bốn số nguyên $n, x, u, v$ ($2 \le n \le 10^9$, $1 \le x < n$, $1 \le u < v \le 10^9$, $v$ không chia hết cho $10^9 + 7$).

Dữ liệu ra

  • In ra một số nguyên duy nhất là xác suất cần tìm theo modulo $10^9 + 7$. (Nếu $p = \frac{1}{2}$, xác suất là $\frac{x}{n}$; bảo đảm $n$ không chia hết cho $10^9 + 7$ khi $p = \frac{1}{2}$, và $p^n \ne (1-p)^n \pmod{10^9+7}$).

Ví dụ

Input
4 1 1 2
Output
250000002

Giải thích

Với $n = 4, x = 1, p = \frac{1}{2}$, xác suất chạm $4$ trước $0$ là $\frac{1}{4} \equiv 250000002 \pmod{10^9+7}$.

Giới hạn

  • $2 \le n \le 10^9$
  • $1 \le x < n$
  • $1 \le u < v \le 10^9$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved