trang chủ / đề bài / icpc21_mb_h

Chia nhóm

Đề bài

Mô tả

Một trường học có 2n học sinh, được đánh số từ 1 đến 2n. Hãy đếm số cách chọn một nhóm gồm ít nhất 2 học sinh sao cho với mọi cặp học sinh a và b trong nhóm, |a−b|≠1 và |a−b|≠n+x.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên n và x (1≤n≤1018, 0≤x≤n).

Dữ liệu ra

In ra một số nguyên là số cách chọn nhóm, lấy phần dư khi chia cho 109+7.

Ràng buộc

  • 1≤n≤1018.
  • 0≤x≤n.

Ví dụ

Input Output Giải thích
2 1 2 Có 4 học sinh, các cặp bị cấm là các cặp có hiệu bằng 1 hoặc 3. Có thể chọn {1,3} hoặc {2,4}.
3 3 14 Ví dụ bổ sung (không có trong đề gốc). Hiệu n+x=6 không xảy ra giữa 6 học sinh, nên chỉ cần không chọn hai học sinh liên tiếp: có 21 tập như vậy (kể cả tập rỗng), trừ đi tập rỗng và 6 tập một phần tử còn 14.

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