Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

תיאור

נתונה מחרוזת $S$ באורך $N$ המורכבת מאותיות אנגליות גדולות. באפשרותכם לבצע את הפעולה הבאה על $S$ מספר כלשהו של פעמים:

  • בחרו רביעיית מספרים שלמים $(i, j, k, l)$ כך ש-$1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ ו-$S_l = \text{C}$. החליפו את כל $S_i, S_j, S_k, S_l$ ב-$\text{X}$, והרוויחו $(i \times j \times k \times l)$ ין.

מצאו את סכום הכסף המרבי שניתן להרוויח בסך הכול, מודולו $998244353$.

קלט

השורה הראשונה מכילה מספר שלם $N$ ($1 \le N \le 5 \times 10^5$). השורה השנייה מכילה מחרוזת $S$ באורך $N$ המורכבת מאותיות אנגליות גדולות.

פלט

הדפיסו את התשובה.

דוגמאות

קלט 1

10
KKUPCUCAPC

פלט 1

1164

קלט 2

4
TUNA

פלט 2

0

קלט 3

30
KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK

פלט 3

619704

הערה

שימו לב שאתם מתבקשים למצוא את השארית של הערך המרבי, ולא את השארית המרבית האפשרית. עבור הדוגמה הראשונה, ניתן להרוויח 1164 ין על ידי ביצוע הפעולות הבאות:

  • בחרו $(i, j, k, l) = (1, 3, 4, 7)$. תרוויחו $1 \times 3 \times 4 \times 7 = 84$ ין. אז $S = \text{XKXXCUXAPC}$.
  • בחרו $(i, j, k, l) = (2, 6, 9, 10)$. תרוויחו $2 \times 6 \times 9 \times 10 = 1080$ ין. אז $S = \text{XXXXCXXXAXX}$.

ניתן להוכיח שאי אפשר להרוויח יותר מ-1164 ין, לכן הדפיסו 1164. עבור הדוגמה השנייה, לא ניתן לבצע אף פעולה ולו פעם אחת, לכן הדפיסו 0.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1533EditorialOpen题解jianglyView

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.