Đếm mảng đơn đỉnh
Đề bài
Mô tả
Đếm số lượng mảng thỏa mãn đồng thời các điều kiện sau:
- Mảng có đúng phần tử;
- Mỗi phần tử là số nguyên trong đoạn từ đến ;
- Trong mảng có đúng một cặp phần tử bằng nhau (nghĩa là có đúng một giá trị xuất hiện hai lần, tất cả các giá trị còn lại đôi một khác nhau);
- Tồn tại một chỉ số sao cho mảng tăng ngặt trước vị trí và giảm ngặt sau vị trí đó. Cụ thể, với mảng : nếu , và nếu .
In ra số lượng mảng thỏa mãn, lấy phần dư khi chia cho .
Dữ liệu vào
Một dòng chứa hai số nguyên và .
Dữ liệu ra
In ra một số nguyên duy nhất: số lượng mảng thỏa mãn tất cả các điều kiện, lấy theo modulo .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 4 | 6 | Sáu mảng: [1,2,1], [1,3,1], [1,4,1], [2,3,2], [2,4,2], [3,4,3]. |
| 3 5 | 10 | Chọn hai giá trị phân biệt trong làm đỉnh và giá trị lặp, có cách. |
| 2 2 | 0 | Với không thể có mảng vừa tăng ngặt vừa giảm ngặt với một cặp bằng nhau. |
| 42 1337 | 806066790 |
Bình luận