trang chủ / bài tập / invcolor

Tô bảng đẹp

Đề bài

Mô tả

Cho một bảng vuông n×n ô. Mỗi ô được tô bằng một trong hai màu: trắng hoặc đen.

Một cách tô được gọi là đẹp nếu với mọi hai hàng kề nhau, hoặc hai hàng đó hoàn toàn giống nhau ở mọi cột, hoặc hoàn toàn khác nhau ở mọi cột. Điều kiện tương tự cũng được áp dụng cho mọi hai cột kề nhau.

Một cách tô được gọi là hợp lệ nếu nó đẹp và không tồn tại bất kỳ hình chữ nhật con đơn sắc (gồm các ô liên tiếp cùng màu, các cạnh song song với cạnh bảng) nào có diện tích lớn hơn hoặc bằng k ô.

Hãy đếm số cách tô hợp lệ của bảng đã cho. Vì kết quả có thể rất lớn, in ra phần dư của nó khi chia cho 998244353.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên nk — kích thước bảng và giới hạn diện tích hình chữ nhật đơn sắc.

Dữ liệu ra

In ra một số nguyên duy nhất là số cách tô hợp lệ modulo 998244353.

Ràng buộc

  • 1n500
  • 1kn2

Ví dụ

Input Output Giải thích
2 3 6 Trong tổng số 8 cách tô đẹp của bảng 2×2, có 6 cách mà mọi hình chữ nhật đơn sắc đều có diện tích nhỏ hơn 3. Hai cách bị loại là hai cách tô tất cả 4 ô cùng màu.
1 1 0 Bảng 1×1 luôn chứa một hình chữ nhật đơn sắc 1 ô, không thoả mãn diện tích nhỏ hơn 1.
49 1808 359087121 Kết quả lấy modulo 998244353.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0