Chuỗi Thắng Liên Tiếp Trong Giải Cờ Chớp
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Một kỳ thủ tham gia chuỗi $N$ ván cờ chớp liên tiếp. Ở ván thứ $i$, xác suất kỳ thủ giành chiến thắng là $P_i / 100$ (nếu không thắng thì chuỗi thắng liên tiếp hiện tại bị đặt lại về $0$). Ban tổ chức trao giải thưởng đặc biệt cho kỳ thủ nếu trong suốt $N$ ván có ít nhất một thời điểm đạt được chuỗi $K$ ván thắng liên tiếp trở lên. Hãy tính xác suất kỳ thủ nhận được giải thưởng đặc biệt theo modulo $10^9 + 7$.
Dữ liệu vào
Dòng 1 gồm hai số nguyên $N, K$ ($1 \le K \le N \le 2000$). Dòng 2 gồm $N$ số nguyên $P_1, P_2, \dots, P_N$ ($0 \le P_i \le 100$).
Dữ liệu ra
In ra xác suất đạt chuỗi ít nhất $K$ ván thắng liên tiếp theo modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 3 2 50 50 50 |
375000003 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion