Universal Cup Judging System

Universal Cup

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

ピコ太郎の大ヒット曲「ペンパイナッポーアッポーペン(PPAP)」の精神に則り、英小文字のみからなる与えられた文字列 $S = s_1 s_2 \ldots s_n$ から、左から右へ互いに重ならない 4 つの部分文字列を選ぶ方法のうち、それら 4 つの部分文字列が象徴的な PPAP の構造を模倣するようなものの個数を求めてください。

pen pineapple apple pen

より具体的には、次の条件を満たす 8 つの整数 $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$)を選びます。

  • 1 番目と 4 番目の部分文字列が一致する:$s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$。これは先頭と末尾で一致する「pen」を表します。
  • 3 番目の部分文字列が 2 番目の部分文字列の真の接尾辞(strict suffix)である。すなわち、ある整数 $k_2$($i_2 < k_2 \le j_2$)が存在して $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$ を満たす。これは後者が前者の真の接尾辞であるという「pineapple」と「apple」の関係を表します。

上記の条件を満たす有効な $8$ つ組 $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ の個数を求めてください。

入力

各テストファイルには 1 つのテストケースのみが含まれます。

唯一の行には、英小文字のみからなる与えられた文字列を表す文字列 $S$($1 \le |S| \le 5 \times 10^3$)が与えられます。

出力

有効な PPAP 型の選び方の個数を表す 1 つの整数を 1 行に出力してください。答えは非常に大きくなる可能性があるため、$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.