Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Im Geiste des viralen Hits Pen-Pineapple-Apple-Pen (PPAP) von PIKOTARO musst du die Anzahl der Möglichkeiten bestimmen, in der gegebenen Zeichenkette $S = s_1 s_2 \ldots s_n$, die nur aus englischen Kleinbuchstaben besteht, von links nach rechts vier sich nicht überlappende Teilstrings auszuwählen, sodass die vier Teilstrings die ikonische PPAP-Struktur nachahmen:

pen pineapple apple pen

Genauer gesagt wählst du acht ganze Zahlen $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$), sodass gilt:

  • Der erste und der vierte Teilstring sind identisch: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Dies steht für das übereinstimmende „pen“ am Anfang und am Ende.
  • Der dritte Teilstring ist ein echtes Suffix des zweiten Teilstrings. Das heißt, es existiert eine ganze Zahl $k_2$ ($i_2 < k_2 \le j_2$), sodass $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$ gilt. Dies erfasst die Beziehung zwischen „pineapple“ und „apple“, wobei Letzteres ein echtes Suffix von Ersterem ist.

Du musst die Anzahl der gültigen $8$-Tupel $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ bestimmen, die die obigen Bedingungen erfüllen.

Eingabe

In jeder Testdatei gibt es nur einen einzigen Testfall.

Die erste und einzige Zeile enthält eine Zeichenkette $S$ ($1 \le |S| \le 5 \times 10^3$), die die gegebene Zeichenkette aus englischen Kleinbuchstaben angibt.

Ausgabe

Gib eine Zeile mit einer ganzen Zahl aus, die die Anzahl der gültigen Auswahlen im PPAP-Stil angibt. Da die Antwort groß sein kann, gib sie modulo $998\,244\,353$ aus.

Beispiele

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.