Tối ưu mã dữ liệu

Xem dạng PDF

Gửi bài giải

Điểm: 800 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, Scratch, Sed, Swift, TCL, Turing, VB, Zig

TaThanHungbc là một lập trình viên tài ba. Thành tựu về lập trình của anh thật sự rất đáng ngưỡng mộ, tiêu biểu là thuật toán ~\texttt{luồng LogN}~(đưa mọi bài toán về luồng và giải quyết chúng với độ phức tạp ~\texttt{O(Log N)}~), ~\texttt{công nghệ nhập xuất tiên tiến}~ (nhập xuất file trên ~10^9~ số với độ phức tạp ~\texttt{O(1)}~)...

Gần đây anh đã nghiên cứu(tự nghĩ) một vài mã dữ liệu cho thuật toán mới của anh. Tuy nhiên, một vài chuyên gia nhận định rằng những mã dữ liệu này khá dài dòng và cần được rút gọn bởi vì: ~\texttt{"Code càng ngắn thì càng tối ưu"}~. Anh nhận thấy rằng những kí tự liên tiếp giống nhau hoàn toàn có thể lược bỏ bớt còn lại ~1~ hoặc ~2~ kí tự (có thể không xóa kí tự nào) thì mã dữ liệu này vẫn hoạt động tốt.

Ngoài việc tối ưu mã dữ liệu này, anh còn quan tâm đến có bao nhiêu cách rút gọn mã dữ liệu. Vì còn bận rộn với rất nhiều thuật toán khác nhau, bạn hãy giúp TaThanHungbc thực hiện việc này.

~\texttt{Input}~

  • Dòng đầu tiên chứa xâu ~S~ mô tả đoạn mã dữ liệu.

~\texttt{Output}~

  • Gồm một số nguyên duy nhất là số cách tối ưu mã dữ liệu (lược bỏ các kí tự ở vị trí khác nhau là cách tối ưu khác nhau).
  • Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho ~\texttt{998244353}~.

~\texttt{Constraint}~

  • ~1 \leq |S| \leq 10^6~

~\texttt{Subtask}~

  • Subtask ~1~ (~50\%~ số điểm): Đoạn mã dữ liệu ban đầu đã được tối ưu (TaThanHungbc cực kì khủng).
  • Subtask ~2~ (~50\%~ số điểm): Không có giới hạn gì thêm (TaThanHungbc vẫn cực kì khủng nhưng muốn đặt ra thách thức cho bạn).

~\texttt{Sample Input 1}~

aabb

~\texttt{Sample Output 1}~

9

~\texttt{Sample Input 2}~

xxzzzz

~\texttt{Sample Output 2}~

30

~\texttt{Notes}~

~\texttt{Sample Test 1}~

  • aabb
  • ~~a~~abb
  • a~~a~~bb
  • aa~~b~~b
  • ~~a~~a~~b~~b
  • a~~ab~~b
  • aab~~b~~
  • ~~a~~ab~~b~~
  • a~~a~~b~~b~~

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.