Bước Đi Ngẫu Nhiên Trên Trục Số
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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
Community Discussion