Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓
الإحصائيات

W duchu wiralowego hitu Pen-Pineapple-Apple-Pen (PPAP) autorstwa PIKOTARO musisz znaleźć liczbę sposobów wyboru czterech nienachodzących na siebie podciągów spójnych (podsłów) od lewej do prawej w danym napisie $S = s_1 s_2 \ldots s_n$, składającym się wyłącznie z małych liter alfabetu angielskiego, tak aby te cztery podsłowa naśladowały kultową strukturę PPAP:

pen pineapple apple pen

Dokładniej mówiąc, należy wybrać osiem liczb całkowitych $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$) takich, że:

  • Pierwsze i czwarte podsłowo są identyczne: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Odpowiada to pasującym słowom „pen” na początku i na końcu.
  • Trzecie podsłowo jest właściwym sufiksem drugiego podsłowa. Oznacza to, że istnieje liczba całkowita $k_2$ ($i_2 < k_2 \le j_2$) taka, że $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Oddaje to zależność między „pineapple” oraz „apple”, gdzie drugie słowo jest właściwym sufiksem pierwszego.

Musisz wyznaczyć liczbę poprawnych $8$-krotek $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ spełniających powyższe warunki.

Wejście

W każdym pliku testowym znajduje się tylko jeden przypadek testowy.

Pierwszy i jedyny wiersz zawiera napis $S$ ($1 \le |S| \le 5 \times 10^3$) oznaczający dany napis składający się wyłącznie z małych liter alfabetu angielskiego.

Wyjście

Wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą liczbę poprawnych wyborów w stylu PPAP. Ponieważ odpowiedź może być duża, wypisz ją modulo $998\,244\,353$.

Przykład

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.