Truyền Gói Tin Qua Chuỗi Trạm Vi Ba
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Một gói tin được truyền tuần tự qua $N$ trạm vi ba từ trạm $1$ đến trạm $N$. Tại trạm thứ $i$, xác suất truyền thành công ngay ở lần phát đầu tiên là $P_i / 100$. Nếu thất bại, trạm sẽ tự động phát lại cho đến khi thành công, nhưng mỗi lần phát tại trạm $i$ tiêu tốn $C_i$ mili-giây. Giả sử kết quả của các lần phát là độc lập với nhau, hãy tính kỳ vọng tổng thời gian (mili-giây) để gói tin đi qua hết cả $N$ trạm theo modulo $10^9 + 7$.
Dữ liệu vào
Dòng 1 chứa số nguyên $N$ ($1 \le N \le 10^5$). $N$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên $P_i, C_i$ ($1 \le P_i \le 100, 1 \le C_i \le 10^6$).
Dữ liệu ra
In ra kỳ vọng tổng thời gian tính theo modulo $10^9 + 7$ (tức là $P \cdot Q^{-1} \pmod{10^9+7}$).
Ví dụ
| Input | Output |
|---|---|
| 3 50 10 100 5 25 8 |
57 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion