trang chủ / đề bài / icpc19_nat_h

Thợ săn x Liên lạc

Đề bài

Mô tả

Sau khi vượt qua Kỳ thi Thợ săn, Gon giờ đã chính thức là một Thợ săn! Gon đang chia tay người bạn thân nhất, Killua, vì Gon muốn về thăm nhà ở "Đảo While".

Gon và Killua định dùng ứng dụng nhắn tin trực tuyến Olaz để giữ liên lạc. Tuy nhiên, họ không tin tưởng lắm vào độ bảo mật của Olaz: kẻ mạo danh có thể đăng nhập vào tài khoản của Gon và gửi tin nhắn cho Killua! Để ngăn chặn điều này, họ quyết định dùng cách sau:

  • Trước khi bắt đầu một cuộc trò chuyện, Gon phải gửi cho Killua một số X có đúng n chữ số.
  • Killua phải trả lời bằng một số nguyên Y có đúng n chữ số, sao cho X và Y tạo thành một cặp bạn thân.
  • Mỗi lần bắt đầu một cuộc trò chuyện, họ phải dùng một cặp bạn thân khác. Điều này giúp tránh việc kẻ mạo danh dùng lại các cặp bạn thân trước đó.

Để định nghĩa cặp bạn thân, trước hết ta định nghĩa một thao tác thân thiện trên số X như sau:

  • Chọn hai chữ số kề nhau của X.
  • Hoặc cộng 1 vào cả hai chữ số, hoặc trừ 1 khỏi cả hai chữ số.
  • Không được cộng 1 vào chữ số 9, hay trừ 1 khỏi chữ số 0.
  • Cũng không được trừ 1 khỏi chữ số đầu tiên của X nếu chữ số đầu tiên đó là 1.

Hai điều kiện cuối đảm bảo số mới hợp lệ và không có chữ số 0 ở đầu. Số mới và số cũ cũng có cùng độ dài.

Hai số X và Y không có chữ số 0 ở đầu được gọi là bạn thân nếu ta có thể thu được Y từ X sau một số hữu hạn thao tác thân thiện. Lưu ý mỗi số X là bạn thân của chính nó.

Ví dụ, 666 và 875 là bạn thân vì ta có thể thực hiện các thao tác:

  • 666→776
  • 776→886
  • 886→875

Gon muốn biết họ có thể trò chuyện bao nhiêu lần trước khi dùng hết các cặp bạn thân.

Dữ liệu vào

Dữ liệu vào gồm đúng một số nguyên n (1≤n≤105).

Dữ liệu ra

In ra đúng một số nguyên là số cặp số bạn thân (X,Y) có đúng n chữ số, lấy phần dư khi chia cho 998244353.

Ràng buộc

  • 1≤n≤105

Ví dụ

Input Output Giải thích
1 10 Có 10 số có một chữ số (0 đến 9) và không thể thực hiện thao tác nào, nên mỗi số chỉ là bạn thân của chính nó.
2 570 Chẳng hạn (10,32) là một cặp bạn thân vì 10→21→32.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0