Đếm số lượng dãy con tăng dài nhất
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho dãy số nguyên $A$ gồm $N$ phần tử. Hãy đếm xem có bao nhiêu dãy con tăng ngặt (không nhất thiết liên tiếp) có độ dài bằng với độ dài của dãy con tăng dài nhất (LIS). Hai dãy con được coi là khác nhau nếu tập hợp các chỉ số được chọn là khác nhau.
Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($|A_i| \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là số lượng LIS modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 5 1 3 5 4 7 |
2 |
Giới hạn
- $1 \le N \le 10^5, |A_i| \le 10^9$
Community Discussion