Chuỗi Đối Xứng Kỳ Diệu
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một chuỗi S gồm N ký tự chữ cái thường. Tìm số lượng cặp (i, j) với 1 ≤ i ≤ j ≤ N sao cho chuỗi con S[i..j] là palindrome và có hash (theo công thức cho trước) chia hết cho K.
Hash của chuỗi T có độ dài L được tính: H(T) = (T[1]P^(L-1) + T[2]P^(L-2) + ... + T[L]*P^0) mod M, với P = 31, M = 10^9 + 7, và giá trị ký tự 'a' = 1, 'b' = 2, ..., 'z' = 26.
Dữ liệu vào
Dòng 1: Hai số nguyên N và K (1 ≤ N ≤ 3000, 1 ≤ K ≤ 10^9) Dòng 2: Chuỗi S gồm N ký tự chữ cái thường
Dữ liệu ra
Một số nguyên duy nhất — số cặp (i, j) thỏa mãn.
Ví dụ
| Input | Output |
|---|---|
| 5 1\nabcba | 7 |
Giới hạn
- 1 ≤ N ≤ 3000
- 1 ≤ K ≤ 10^9
- Chuỗi S chỉ gồm chữ cái thường
Community Discussion