Đếm cặp có AND bằng x

Đề bài

Mô tả

Cho mảng a1,a2,…,an với 0≤ai<2B. Tiếp theo có q truy vấn: với mỗi truy vấn cho trước x (0≤x<2B), hãy đếm số cặp có thứ tự (i,j) với i≠j thoả mãn aiANDaj=x.

Dữ liệu vào

  • Dòng đầu: ba số nguyên n, B, q.
  • Dòng thứ hai: n số nguyên a1,…,an.
  • Dòng thứ ba: q số nguyên — các giá trị x của các truy vấn.

Dữ liệu ra

In q số nguyên, mỗi số trên một dòng — số cặp có thứ tự cho truy vấn tương ứng.

Ràng buộc

  • 1≤n≤105
  • 1≤B≤20 và 0≤ai<2B
  • 1≤q≤2·105 và 0≤x<2B
  • Đáp số mỗi truy vấn ≤ n(n−1)≤1010 vừa kiểu nguyên 64-bit.

Ví dụ

Input Output Giải thích
4 3 3
5 3 7 1
1 0 5
8
0
2
a=(5,3,7,1). Các giá trị AND của các cặp (i,j) với i<j: 5&3=1, 5&7=5, 5&1=1, 3&7=3, 3&1=1, 7&1=1. Với cặp có thứ tự (nhân 2): AND =1 có 4 cặp không sắp thứ tự ⇒8. AND =5 có 1 cặp ⇒2. AND =0: không cặp nào.
3 2 4
3 3 3
3 2 1 0
6
0
0
0
a=(3,3,3). Mọi cặp i≠j có AND =3 ⇒ 6 cặp với x=3. Còn lại 0.
5 4 2
0 0 0 0 0
0 7
20
0
5 số 0. Mọi cặp có AND =0, có 5·4=20 cặp có thứ tự.

Ghi chú

  • (i,j) và (j,i) với i≠j được coi là hai cặp khác nhau (cặp có thứ tự).
  • B tối đa 20 ⇒ miền giá trị 0..220−1 có khoảng một triệu giá trị.

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