Sưu Tập Thẻ Bài

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

Đề bài

Bộ sưu tập thẻ bài gồm $n$ loại thẻ khác nhau. Mỗi gói thẻ chứa đúng $1$ thẻ, và loại thẻ bên trong được chọn ngẫu nhiên đều trong $n$ loại (mỗi loại có xác suất $\frac{1}{n}$).

Hiện tại Minh đã có sẵn $k$ loại thẻ khác nhau. Minh muốn mua thêm các gói thẻ cho đến khi có ít nhất $m$ loại thẻ khác nhau. Hãy tính kỳ vọng số gói thẻ Minh cần mua thêm, theo modulo $10^9 + 7$.

Dữ liệu vào

  • Một dòng duy nhất chứa ba số nguyên $n, k, m$ ($1 \le n \le 10^6$, $0 \le k \le m \le n$).

Dữ liệu ra

  • In ra một số nguyên duy nhất là kỳ vọng số gói thẻ cần mua thêm theo modulo $10^9 + 7$.

Ví dụ

Input
3 0 3
Output
500000009

Giải thích

Với $n = 3, k = 0, m = 3$, kỳ vọng là $\frac{3}{3} + \frac{3}{2} + \frac{3}{1} = \frac{11}{2} \equiv 500000009 \pmod{10^9+7}$.

Giới hạn

  • $1 \le n \le 10^6$
  • $0 \le k \le m \le n$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved