[ClueOJ x QTOJ] Thi thử TS10 2025 - Đối xứng đôi
Xem dạng PDFhôm nay được học về xâu đối xứng (palindrome).
Nhắc lại: Xâu đối xứng (palindrome) là một xâu mà khi đọc từ trái qua phải hay từ phải qua trái đều giống nhau.
Hôm nay, cô ấy quyết định chế một định nghĩa mới liên quan tới kiểu xâu này - đối xứng đôi. Một xâu được gọi là xâu đối xứng đôi nếu chúng có thể tách thành hai xâu đối xứng nhỏ hơn (một trong hai xâu có thể là xâu rỗng).
Ví dụ: asdfdsa, aabb là xâu đối xứng đôi, nhưng noodles không phải là xâu đối xứng đôi.
Hãy đếm số xâu đối xứng đôi có độ dài trong khoảng từ ~l~ đến ~r~, chỉ chứa các ký tự latin in thường nằm trong ~k~ ký tự đầu tiên của bảng chữ cái.
INPUT: Nhập từ file DPALIND.INP
Nhập vào dòng duy nhất ba số nguyên ~l~, ~r~ và ~k~ (~1 \le l \le r \le 10^5~, ~1 \le k \le 26~)
OUTPUT: Xuất ra file DPALIND.OUT
In ra dòng duy nhất là đáp số bài toán khi chia dư cho ~10^9 + 7~
SAMPLE INPUT 1
1 4 2
SAMPLE OUTPUT 1
30
Các xâu bất kỳ có độ dài từ ~1~ đến ~4~ đều thỏa mãn (có ~30~ xâu như vậy).
SAMPLE INPUT 2
1 2 26
SAMPLE OUTPUT 2
702
Có ~26~ xâu độ dài ~1~ và ~676~ xâu độ dài ~2~ thỏa mãn.
SUBTASKS
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~10~ | ~k \le 3, r \le 10~. |
| 2 | ~10~ | ~r \le 10~. |
| 3 | ~15~ | ~r \le 1000~. |
| 4 | ~5~ | ~k = 1~. |
| 5 | ~15~ | ~k = 2~. |
| 6 | ~45~ | Không có giới hạn gì thêm |
Cảm ơn các bạn đã tham gia contest. Các bạn có thể ủng hộ chúng mình bằng cách feedback về contest ngày hôm nay tại đây nha! Chúng mình cảm ơn các bạn rất nhiều!
P/s: nếu bạn có nhu cầu sử dụng tính năng offline như hôm nay, có thể sử dụng Tính năng tổ chức nha.
Bình luận