Universal Cup Judging System

Universal Cup

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

انطلاقاً من روح الأغنية الشهيرة Pen-Pineapple-Apple-Pen (PPAP) للفنان PIKOTARO، عليك إيجاد عدد طرق اختيار أربع سلاسل فرعية غير متداخلة من اليسار إلى اليمين في السلسلة المعطاة $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) للسلسلة الفرعية الثانية. أي أنه يوجد عدد صحيح $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)$ التي تحقق الشروط المذكورة أعلاه.

الإدخال

توجد حالة اختبار واحدة فقط في كل ملف اختبار.

يحتوي السطر الأول والوحيد على سلسلة نصية $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.