trang chủ / đề bài / icpc22_nat_h

Lát hành lang

Đề bài

Mô tả

Trong cuộc thi Sáng tạo Hoa văn Trong nhà (ICPC) năm nay, các đội cần trang trí một hành lang dài. Sàn hành lang có dạng hình chữ nhật, có thể xem như một lưới gồm 2×n ô.

Thông thường, người ta dùng các viên gạch 1×1 hoặc 2×2 để lát sàn. Tuy nhiên, để đảm bảo tính sáng tạo của cuộc thi, ban giám khảo ICPC yêu cầu mọi đội phải dùng gạch hình chữ L. Gạch hình chữ L là viên gạch nằm gọn trong một lưới 2×2 và phủ đúng 3 trong 4 ô của lưới đó; có 4 hình dạng, tương ứng với ô bị bỏ trống là ô trên trái, trên phải, dưới trái hoặc dưới phải:

##   ##   #.   .#
#.   .#   ##   ##

Mỗi đội có thể dùng một số viên gạch chữ L để lát hành lang. Một đội có thể chọn không dùng viên gạch nào nếu cho rằng hành lang đã đủ đẹp và không cần trang trí thêm. Mọi đội phải đặt gạch lên sàn sao cho:

  • Mỗi viên gạch chữ L phủ đúng ba ô trên sàn.
  • Không có ô nào trên sàn bị phủ bởi nhiều hơn một viên gạch.

Định nghĩa độ phủ của một hành lang đã lát là số ô được phủ trong hành lang. Ban giám khảo ICPC muốn đưa ra một số dự đoán trước cuộc thi, vì vậy họ muốn biết tổng độ phủ của tất cả các cách lát hành lang.

Hai cách lát hành lang được coi là khác nhau khi và chỉ khi ít nhất một trong hai điều sau đúng:

  • Có một ô được phủ trong cách lát này nhưng không được phủ trong cách lát kia.
  • Có một cặp ô được phủ bởi cùng một viên gạch chữ L trong cách lát này, nhưng bởi hai viên gạch khác nhau trong cách lát kia.

Cho n là số cột của sàn hành lang. Hãy tính tổng độ phủ của tất cả các cách lát hành lang, lấy phần dư khi chia cho 998244353.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên n (2≤n≤1018), số cột của sàn hành lang.

Dữ liệu ra

In ra tổng độ phủ của tất cả các cách lát hành lang, lấy phần dư khi chia cho 998244353.

Ràng buộc

  • 2≤n≤1018.

Ví dụ

Input Output Giải thích
2 12 Sàn có kích thước 2×2: có 1 cách lát với độ phủ 0 (không dùng gạch) và 4 cách lát với độ phủ 3 (dùng một viên gạch, có 4 hình dạng). Tổng độ phủ là 1·0+4·3=12.
3 36 Sàn có kích thước 2×3: có 1 cách lát với độ phủ 0, 8 cách lát với độ phủ 3 và 2 cách lát với độ phủ 6. Tổng độ phủ là 1·0+8·3+2·6=36.
177013 912417795

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