Đếm Đường Tăng Dài Nhất

Buổi 39 — DP + Data Structures Dynamic Programming
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved