trang chủ / đề bài / icpc22_mt_m

Nhị phân

Đề bài

Mô tả

Hệ nhị phân là hệ đếm cơ số 2, dùng hai trạng thái 0 (bit 0) và 1 (bit 1) để biểu diễn một số. Hiếu đang tìm hiểu về biểu diễn nhị phân, cụ thể là tính chất của những số có số lượng bit 1 trong biểu diễn nhị phân là số lẻ. Để hiểu rõ hơn, bạn ấy đặt ra bài toán sau.

Cho n và m, hãy tính tổng

∑x=02n−1xm

trong đó chỉ lấy những x có số lượng bit 1 trong biểu diễn nhị phân là số lẻ.

Bài toán này hóa ra khó hơn vẻ ngoài của nó, bạn hãy giúp Hiếu giải nhé.

Dữ liệu vào

  • Dòng đầu tiên gồm số nguyên T (1≤T≤104): số bộ test.
  • Mỗi bộ test gồm một dòng chứa hai số nguyên n và m (1≤n≤106, 1≤m≤5000, m≤n).

Dữ liệu ra

Với mỗi bộ test, in ra kết quả theo modulo 109+7 trên một dòng.

Ràng buộc

  • 1≤T≤104
  • 1≤n≤106
  • 1≤m≤5000, m≤n

Ví dụ

Input Output Giải thích
1
3 3
416 Với n=3, có 4 số có số bit 1 lẻ: 1, 2, 4, 7. Kết quả là 13+23+43+73=1+8+64+343=416.
3
1 1
2 1
4 2
1
3
620
Ví dụ bổ sung (không có trong đề gốc). Với n=2: các số 1, 2 có tổng 3. Với n=4: các số 1,2,4,7,8,11,13,14 có tổng bình phương 620.

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