D. Тэмдэгт мөр

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

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

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

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

Танд $s$ тэмдэгт мөр өгөгдсөн. $1 ≤ l ≤ r ≤ |s|$ нөхцөлийг хангах $l$, $r$ хос бүрийн хувьд $l$-ээс $r$ хүртэл ($l$, $r$ орно) тэмдэгтүүдээс бүтэх тэмдэгт мөрийг дэд-тэмдэгт мөр гэнэ.

$x$, $y$ хоёр тэмдэгт мөрийн хувьд $F(x,y)$-ээр дараах утгыг тэмдэглэе.

Эхлээд бид $y$-тэй тэнцүү байх $x$-н дэд-тэмдэгт мөрүүдийг олох ба энэ дэд-тэмдэгт бүр хос тоогоор ($l$, $r$) илэрхийгдэнэ. Одоо энэ хосуудаар хосын эхний утга нь өсөж байхаар дарааллууд байгуулъя. Энэ дарааллуудын нийт тоо нь $F(x,y)$-н утга болно.

Жишээ нь: $F(babbabbababbab,babb) = 6$. Дараах дэд-тэмдэгт мөрийн хосууд олдоно:

($1,4$), ($4,7$), ($9,12$)

Энэ нь хосуудаар дараах дарааллуудыг байгуулж болно:

  • $(1,4)$
  • $(4,7)$
  • $(9,12)$
  • $(1,4)$, $(4,7)$
  • $(4,7)$, $(9,12)$
  • $(1,4)$, $(4,7)$, $(9,12)$

Таны даалгавар бол өгөгдсөн $s$ тэмдэгт мөрийн хувьд $s$-н бүх боломжит дэд-тэмдэгт мөр $x$-н хувьд $F(s,x)$ утгуудын нийлбэрийг олно.

Оролт

Латин цагаан толгойн жижиг үсгүүдээс тогтох $s$ тэмдэгт мөр ($1 ≤ |s| ≤ 10^5$).

Гаралт

Хариу болох боломжит бүх утгуудын нийлбэр.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: gmunkhbaatarmn

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

Оролт
aaaa
Гаралт
20
Оролт
abcdef
Гаралт
21
Оролт
abacabadabacaba
Гаралт
188

Тэмдэглэл

Эхний жишээн дээр $x$ нь $a$, $aa$, $aaa$, $aaaa$ байж болох ба $F(s, x)$-н утга харгалзан $10$, $6$, $3$, $1$ байна.

Хоёр дахь жишээн дээр бүх боломжит $x$-н хувьд $F(s,x)$-н утга $1$ байна.

Сэтгэгдлүүдийг ачааллаж байна...