Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

PIKOTARO-ның әйгілі Pen-Pineapple-Apple-Pen (PPAP) вирустық хитінің рухында, тек кіші ағылшын әріптерінен тұратын берілген $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» сөзін білдіреді.
  • Үшінші ішкі жол екінші ішкі жолдың қатаң жұрнағы (strict suffix) болып табылады. Яғни $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$ болатындай $k_2$ ($i_2 < k_2 \le j_2$) бүтін саны табылады. Бұл «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.