Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Theo tinh thần của bản hit đình đám Pen-Pineapple-Apple-Pen (PPAP) của PIKOTARO, bạn cần tìm số cách chọn bốn xâu con không giao nhau từ trái sang phải trong xâu đã cho $S = s_1 s_2 \ldots s_n$ chỉ gồm các chữ cái tiếng Anh viết thường, sao cho bốn xâu con này mô phỏng cấu trúc PPAP kinh điển:

pen pineapple apple pen

Cụ thể hơn, hãy chọn tám số nguyên $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$) sao cho:

  • Xâu con thứ nhất và xâu con thứ tư giống hệt nhau: $s_{i_1} s_{i_1+1} \ldots s_{j_1} = s_{i_4} s_{i_4+1} \ldots s_{j_4}$. Điều này biểu thị từ "pen" trùng khớp ở đầu và cuối.
  • Xâu con thứ ba là một hậu tố thực sự (strict suffix) của xâu con thứ hai. Nghĩa là tồn tại một số nguyên $k_2$ ($i_2 < k_2 \le j_2$) sao cho $s_{k_2} s_{k_2+1} \ldots s_{j_2} = s_{i_3} s_{i_3+1} \ldots s_{j_3}$. Điều này thể hiện mối quan hệ giữa "pineapple" và "apple", khi từ sau là hậu tố thực sự của từ trước.

Bạn cần tìm số bộ $8$ số $(i_1, j_1, i_2, j_2, i_3, j_3, i_4, j_4)$ hợp lệ thỏa mãn các điều kiện trên.

Dữ liệu vào

Mỗi tệp dữ liệu chỉ có duy nhất một bộ dữ liệu.

Dòng đầu tiên và duy nhất chứa một xâu $S$ ($1 \le |S| \le 5 \times 10^3$) biểu thị xâu đã cho chỉ gồm các chữ cái tiếng Anh viết thường.

Dữ liệu ra

In ra một dòng chứa một số nguyên, biểu thị số cách chọn hợp lệ theo kiểu PPAP. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho $998\,244\,353$.

Ví dụ

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.