Đường Đi Âm

Buổi 41 — SPFA & Bellman-Ford Buổi 52 — Mock Contest Phase 2
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Một trò chơi gồm N vòng. Ở vòng thứ i, xác suất thắng là p_i/100 (với p_i là số nguyên từ 1 đến 99). Người chơi thắng trò chơi nếu thắng ít nhất K vòng trong N vòng. Hãy tính xác suất thắng trò chơi, lấy modulo 1000000007.

Cụ thể, biểu diễn xác suất dưới dạng phân số P/Q với gcd(P,Q)=1. In ra P * Q^(-1) mod 1000000007.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên N K (1 ≤ K ≤ N ≤ 5000).

Dòng thứ hai chứa N số nguyên p_1, p_2, ..., p_N (1 ≤ p_i ≤ 99).

Dữ liệu ra

Input Output
4 5\n1 2 1\n2 3 -2\n3 4 3\n1 3 5\n2 4 4 0\n1\n-1\n2
Giới hạnIn ra xác suất thắng trò chơi modulo 1000000007.

Ví dụ
  • 1 ≤ N ≤ 5000
  • 1 ≤ M ≤ 10000
  • -10^6 ≤ w ≤ 10^6
Input Output
2 1\n50 50 750000006
Draft saved