Universal Cup Judging System

Universal Cup

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

PIKOTAROn viraalihitin Pen-Pineapple-Apple-Pen (PPAP) hengessä tehtäväsi on laskea, kuinka monella tavalla annetusta vain pieniä englantilaisia kirjaimia sisältävästä merkkijonosta $S = s_1 s_2 \ldots s_n$ voidaan valita vasemmalta oikealle neljä toisiaan leikkaamatonta osamerkkijonoa siten, että nämä neljä osamerkkijonoa jäljittelevät ikonista PPAP-rakennetta:

pen pineapple apple pen

Tarkemmin sanottuna valitaan kahdeksan kokonaislukua $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$) siten, että:

  • Ensimmäinen ja neljäs osamerkkijono ovat samat: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Tämä vastaa alussa ja lopussa täsmäävää sanaa "pen".
  • Kolmas osamerkkijono on toisen osamerkkijonon aito loppuosa (strict suffix). Toisin sanoen on olemassa sellainen kokonaisluku $k_2$ ($i_2 < k_2 \le j_2$), että $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Tämä kuvaa sanojen "pineapple" ja "apple" välistä suhdetta, jossa jälkimmäinen on edellisen aito loppuosa.

Tehtäväsi on löytää edellä mainitut ehdot täyttävien kelvollisten $8$-monikkojen $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ lukumäärä.

Syöte

Jokaisessa testitiedostossa on vain yksi testitapaus.

Ensimmäinen ja ainoa rivi sisältää merkkijonon $S$ ($1 \le |S| \le 5 \times 10^3$), joka koostuu vain pienistä englantilaisista kirjaimista.

Tuloste

Tulosta yksi rivi, joka sisältää yhden kokonaisluvun: kelvollisten PPAP-tyylisten valintojen lukumäärän. Koska vastaus voi olla suuri, tulosta se modulo $998\,244\,353$.

Esimerkit

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.