trang chủ / đề bài / icpc25_mb_i

Nhảy cầu thang

Đề bài

Mô tả

Misdeed đang nghĩ đến chuyện nhảy. Nhảy xuống cầu thang.

Cầu thang của Misdeed có n bậc và anh ấy đang đứng ở bậc n. Anh ấy định nhảy tổng cộng k lần, mỗi lần có thể nhảy xuống bao nhiêu bậc cũng được (kể cả không nhảy bậc nào), miễn là không vượt quá chân cầu thang, tức là không đáp xuống thấp hơn bậc 0. Hãy đếm giúp Misdeed số cách nhảy thành công.

Đó là đề bài lúc đầu. Tuy nhiên, Misdeed vừa xấu tính vừa khó chịu.

Gọi dãy các lần nhảy là a1,a2,…,ak (các số nguyên không âm). Bây giờ, ở lượt thứ i, Misdeed sẽ nhảy ai·i bậc. Do đó a1·1+a2·2+…+ak·k≤n. Ngoài ra, phải có a1&a2&…&ak=x (với & là phép AND theo bit); nếu không, Misdeed sẽ trượt chân và đập đầu vào mép bậc thang.

Yêu cầu: Đếm số dãy a1,a2,…,ak thỏa mãn cả hai điều kiện trên, lấy phần dư khi chia cho 109+7.

Dữ liệu vào

Một dòng gồm ba số nguyên n, k, x: số bậc của cầu thang, số lần nhảy và giá trị AND yêu cầu.

Dữ liệu ra

In ra số dãy thỏa mãn, lấy phần dư khi chia cho 109+7.

Ràng buộc

  • 0≤n,x≤1018
  • 1≤k≤60

Ví dụ

Input Output Giải thích
11 3 1 4 Các dãy thỏa mãn là [1,1,1], [3,1,1], [1,3,1], [5,1,1].
10 2 0 26 Ví dụ bổ sung. Cần a1+2a2≤10 và a1&a2=0; chẳng hạn a2=0 cho 11 dãy (a1=0..10).

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