Universal Cup Judging System

Universal Cup

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

피코타로(PIKOTARO)의 인기 히트곡 펜-파인애플-애플-펜(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.