Số lượng dãy con tăng dài nhất

Buổi 26 — Fenwick Tree Data-structures Dynamic Programming
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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$
Draft saved