TLE-oj Cup Round 5 - MEX đoạn con
Xem PDF
Nộp bài
Điểm:
1700 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
SMEX.inp
Output:
SMEX.out
Tác giả:
Dạng bài
Cho a = a_1, a_2, ..., a_n là một dãy số nguyên không âm. Hãy đếm số cách chia dãy a thành các đoạn con liên tiếp, sao cho MEX của các đoạn con, theo thứ tự, tạo thành một dãy không giảm. Ở đây, MEX của đoạn con [i..j] là số nguyên không âm nhỏ nhất không xuất hiện trong \{a_i, a_{i + 1}, ..., a_j\}
Input, Output và Subtasks
Input: (SMEX.inp)
- Dòng đầu tiên chứa số nguyên dương n (n \le 5000).
- Dòng tiếp theo là n số nguyên a_1, a_2, ..., a_n (a_i \le 10^9).
Output: (SMEX.out)
- Một dòng duy nhất là kết quả bài toán. Vì kết quả có thể rất lớn nên chỉ cần in phần dư của số cách tìm được khi chia cho 10^9+7.
Subtasks
- Subtask 1 (25\%): n \le 100.
- Subtask 2 (25\%): a_i \le 100.
- Subtask 3 (25\%): n \le 2000.
- Subtask 4 (25\%): Không có giới hạn gì thêm.
Sample 1
Input (SMEX.inp)
8
3 0 2 1 0 1 3 2
Output (SMEX.out)
8
Bình luận