E. Огтлолцсон палиндромууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 128 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Англи хэлний хичээл дээр Никд хийх зүйл тийм ч их байсангүй тул палиндром хэмээх гайхалтай тэмдэгт мөрийн талаар бодож суув. Хэрэв тэмдэгт мөрийг зүүнээс баруун, баруунаас зүүн тийш аль ч чиглэлд уншиж болдог бол үүнийг Палиндром тэмдэгт мөр гэнэ. Жишээлбэл: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Ник хичээл дээрээ уншиж байсан текстэн дэх бүх палиндромуудыг анхааралтай ажиглаж эхлэв. Текстэн дэх палиндромын тохиолдол бүрт тэрээр текстэн дэх уг палиндромын эхний тэмдэгтийн болон төгсгөлийн тэмдэгтийн байрлалыг бичиж авч байлаа. Ник текстэн дундаас олсон палиндром бүрийгээ дэд палиндром гэж нэрлэв. Тэр бүх дэд палиндромуудыг олоод эдгээр дэд палиндромуудын зарим нь хоорондоо огтлолцож байгааг анзаарч, эдгээр хосын тоог мэдэхийг хүсчээ. Текстэн дэхь аль нэг үсэг уг хоёр дэд палиндромд хоёуланд нь байдаг бол уг $2$ палиндромыг огтлолцдог гэнэ. Ямар ч палиндром өөртэйгээ огтлолцохгүй.

Жишээ болгон, Никийн «babb» текстэн дээр гүйцэтгэсэн үйлдлүүдийг харцгаая. Эхлээд тэр бүх дэд палиндромуудыг бичжээ: $\cdot$

  • «b...» Байрлалууд: $1..1$
  • «bab.» Байрлалууд: $1..3$
  • «.a..» Байрлалууд: $2..2$
  • «..b.» Байрлалууд: $3..3$
  • «..bb» Байрлалууд: $3..4$
  • «...b» Байрлалууд: $4..4$

Дараа нь тэр эдгээр огтлолцдог дэд палиндромууд дунд хоорондоо огтлолцдог хосуудыг тоолно. Ийм хослол 6 байна:

  • $1..1$ нь $1..3$-тэй
  • $1..3$ нь $2..2$-тэй
  • $1..3$ нь $3..3$-тэй
  • $1..3$ нь $3..4$-тэй
  • $3..3$ нь $3..4$-тэй
  • $3..4$ нь $4..4$-тэй тус тус огтлолцоно.

Дээрх үйл явцуудыг бүгдийг гараар хийж гүйцэтгэнэ гэдэг үнэхээр ядармаар ажил тул Ник таныг хоорондоо огтлолцдог дэд палиндромуудын хосын тоог олох програм бичиж өгнө үү гэж хүсч байна.

Оролт

Эхний мөрөнд текстийн уртыг харуулах бүхэл тоо $n$ ($1 ≤ n ≤ 2 \cdot 10^{6}$) байна. Дараагийн мөрөнд $n$ ширхэг Латин жижиг үсэг байна.

Гаралт

Хоорондоо огтлолцдог дэд палиндромын хосын тоог $51123987$-д хуваасан үлдэгдлийг хэвлээрэй.

Орчуулсан: Солонго

Жишээ тэстүүд

Оролт
4
babb
Гаралт
6
Оролт
2
aa
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...