Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Dans l'esprit du tube viral Pen-Pineapple-Apple-Pen (PPAP) de PIKOTARO, vous devez trouver le nombre de façons de sélectionner quatre sous-chaînes disjointes de gauche à droite dans la chaîne donnée $S = s_1 s_2 \ldots s_n$, composée uniquement de lettres minuscules de l'alphabet anglais, de sorte que les quatre sous-chaînes imitent la structure emblématique de PPAP :

pen pineapple apple pen

Plus précisément, il s'agit de choisir huit entiers $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$) tels que :

  • La première et la quatrième sous-chaînes sont identiques : $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Cela représente les « pen » identiques au début et à la fin.
  • La troisième sous-chaîne est un suffixe strict de la deuxième sous-chaîne. Autrement dit, il existe un entier $k_2$ ($i_2 < k_2 \le j_2$) tel que $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Cela traduit la relation entre « pineapple » et « apple », où le second est un suffixe strict du premier.

Vous devez déterminer le nombre de $8$-uplets $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ valides satisfaisant les conditions ci-dessus.

Entrée

Il n'y a qu'un seul cas de test dans chaque fichier de test.

La première et unique ligne contient une chaîne $S$ ($1 \le |S| \le 5 \times 10^3$) représentant la chaîne donnée, composée uniquement de lettres minuscules de l'alphabet anglais.

Sortie

Affichez une ligne contenant un entier, indiquant le nombre de sélections valides de type PPAP. Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$.

Exemples

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.