Chuỗi Đối Xứng Kỳ Diệu

Buổi 64 — Contest Chặng 7
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved