Săn Kho Báu Bitmask

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

Đề bài

Có $N$ kho báu khác nhau được đánh số từ $0$ đến $N - 1$. Mỗi lượt, hệ thống sẽ tặng ngẫu nhiên một rương có chứa kho báu thứ $i$ với xác suất $p_i = \frac{w_i}{\sum_{j=0}^{N-1} w_j}$.

Nếu bạn chưa sở hữu kho báu thứ $i$, bạn sẽ giữ lấy nó. Nếu bạn đã có kho báu thứ $i$ rồi, rương đó trở thành vô dụng.

Hãy tính kỳ vọng số lượt để bạn thu thập đủ cả $N$ kho báu, theo modulo $10^9 + 7$.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 18$).
  • Dòng thứ hai chứa $N$ số nguyên dương $w_0, w_1, \dots, w_{N-1}$ ($1 \le w_i \le 10^6$).

Dữ liệu ra

  • In ra một số nguyên duy nhất là kỳ vọng số lượt cần thiết theo modulo $10^9 + 7$.

Ví dụ

Input
2
1 2
Output
500000007

Giải thích

$p_0 = 1/3, p_1 = 2/3$. Kỳ vọng là $1 + \frac{1}{3} \cdot \frac{3}{2} + \frac{2}{3} \cdot 3 = 1 + \frac{1}{2} + 2 = \frac{7}{2} \equiv 500000007 \pmod{10^9+7}$.

Giới hạn

  • $1 \le N \le 18$
  • $1 \le w_i \le 10^6$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved