trang chủ / đề bài / icpc24_mb_k

Dãy đối xứng

Đề bài

Mô tả

Trong một kỳ thi cuối kỳ, thí sinh được yêu cầu giải một Thử thách Thú vị về Đếm Dãy Đối xứng (ICPC). Thử thách này yêu cầu đếm các dãy đối xứng chứa K: các dãy không chỉ có tính đối xứng mà còn phải tuân theo một quy tắc quan trọng: tổng các phần tử của dãy phải bằng một giá trị N cho trước.

Một dãy được gọi là dãy đối xứng nếu đọc từ trái sang phải giống như đọc từ phải sang trái. Cụ thể, dãy S=(s1,s2,…,sn) độ dài n là dãy đối xứng nếu si=sn−i+1 với mọi 1≤i≤n. Ví dụ, (1,2,1) và (4,4) là các dãy đối xứng, còn (1,2) và (3,4,5) thì không. Một dãy đối xứng được gọi là dãy đối xứng chứa K nếu có ít nhất một phần tử của dãy bằng K.

Cho hai số nguyên N và K, hãy đếm số dãy đối xứng chứa K gồm các số nguyên dương có tổng các phần tử bằng N. Hai dãy được coi là khác nhau nếu chúng có độ dài khác nhau hoặc khác nhau ở ít nhất một vị trí. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho 998244353.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên T (1≤T≤100): số bộ test.
  • Mỗi dòng trong T dòng tiếp theo chứa hai số nguyên N và K (1≤N≤1018, 1≤K≤20) mô tả một bộ test.

Dữ liệu ra

Với mỗi bộ test, in ra trên một dòng phần dư của kết quả khi chia cho 998244353.

Ràng buộc

  • 1≤T≤100
  • 1≤N≤1018
  • 1≤K≤20

Ví dụ

Input Output Giải thích
3
6 2
10 3
40 1
4
8
1037630
Ví dụ của đề gốc. Với N=6, K=2 có 4 dãy: (2,2,2), (1,2,2,1), (2,1,1,2), (1,1,2,1,1).
4
1 1
3 2
5 1
4 3
1
0
3
0
Ví dụ bổ sung, tính bằng lời giải mẫu. Với N=3, K=2, các dãy đối xứng tổng 3 là (3) và (1,1,1), không dãy nào chứa 2. Với N=5, K=1 có (1,3,1), (2,1,2), (1,1,1,1,1).

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