Đếm số lượng dãy con tăng dài nhất

Buổi 71-72 — Ôn tập Dynamic Programming
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved