CSES - Increasing Subsequence II | Dãy con tăng II
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho trước một mảng gồm \(n\) số nguyên, bạn cần tính số lượng dãy con tăng mà nó chứa. Nếu hai dãy con có các giá trị giống nhau nhưng ở những vị trí khác nhau trong mảng, chúng được tính là khác nhau.
Input
Dòng đầu tiên chứa số nguyên \(n:\) kích thước của mảng.
Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n:\) nội dung của mảng.
Output
In ra một số nguyên là số lượng dãy con tăng theo modulo \(10^9 + 7\).
Constraints
- \(1≤n≤2⋅10^5\)
- \(1≤x_i≤10^9\)
Example
Sample Input:
3
2 1 3
Sample Output:
5
Note
Các dãy con tăng là \([2], [1], [3], [2,3]\) và \([1,3]\).
Bình luận
CSES - Increasing Subsequence II | Dãy con tăng II
Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tính số dãy con tăng khác nhau của mảng. Hai dãy con tăng chứa các giá trị giống nhau nhưng ở các vị trí khác nhau cũng được coi là hai dãy khác nhau.
Input
Output
Test 1
Input
Output
Note
Các dãy con tăng là \([2]\), \([1]\), \([3]\), \([2,3]\) và \([1,3]\).
2 bình luận nữa