Số lượng dãy con tăng dài nhất
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho mảng $A$ gồm $N$ số nguyên. Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất (LIS) và số lượng dãy con tăng nghiêm ngặt có độ dài lớn nhất đó (lấy phần dư cho $10^9 + 7$). Hai dãy con được coi là khác nhau nếu tập hợp các chỉ số của chúng khác nhau.
Dữ liệu vào
- Dòng đầu tiên 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
- In ra hai số nguyên cách nhau bởi dấu cách: độ dài LIS và số lượng LIS modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 5 1 3 5 4 7 |
4 2 |
Giới hạn
- $1 \le N \le 10^5, |A_i| \le 10^9$
Community Discussion