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