Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

В духе вирусного хита Pen-Pineapple-Apple-Pen (PPAP) исполнителя PIKOTARO вам нужно найти количество способов выбрать четыре непересекающиеся подстроки слева направо в заданной строке $S = s_1 s_2 \ldots s_n$, состоящей только из строчных латинских букв, так, чтобы эти четыре подстроки повторяли знаменитую структуру PPAP:

pen pineapple apple pen

Более формально, требуется выбрать восемь целых чисел $i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4$ ($1 \le i_1 \le j_1 < i_2 \le j_2 < i_3 \le j_3 < i_4 \le j_4 \le n$) таких, что:

  • Первая и четвёртая подстроки совпадают: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Это соответствует совпадающему слову «pen» в начале и в конце.
  • Третья подстрока является строгим суффиксом второй подстроки. То есть существует целое число $k_2$ ($i_2 < k_2 \le j_2$), при котором $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Это отражает связь между «pineapple» и «apple», где второе слово является строгим суффиксом первого.

Вам необходимо найти количество корректных кортежей из $8$ чисел $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$, удовлетворяющих описанным выше условиям.

Входные данные

В каждом тестовом файле содержится только один набор входных данных.

Первая и единственная строка содержит строку $S$ ($1 \le |S| \le 5 \times 10^3$), состоящую только из строчных латинских букв.

Выходные данные

Выведите одну строку, содержащую одно целое число — количество корректных выборов в стиле PPAP. Так как ответ может быть большим, выведите его по модулю $998\,244\,353$.

Примеры

ppaap
1
ppapppap
16
penpineappleapplepen
1502

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#3312EditorialOpen题解:#14808. Pen Pineapple Apple PenDerRichterView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.