Đếm số cặp (a, b) sao cho a & b = n

2017-07-30
Bài gốc

Codeforces 677C

Đề bài

Cho số nguyên dương n, đếm số cặp số (a, b) sao cho a & b = n.

Giới hạn:

  • 0 ≤ a,b,n ≤ 2k
  • 1 ≤ k ≤ 30
Định dạng test

Input:

  • Chứa duy nhất một dòng là n.

Output:

  • In ra số cặp số (a, b): a & b = n chia lấy dư cho 109 + 7.

Ví dụ:

input:
5 3
output:
3

Có 3 cặp số (a, b) thoả mãn là: (5, 5), (7, 5), (5, 7).

Thuật toán

Duyệt qua k bit của n, tại bit thứ i:

  • Nếu bit = 0, có 3 khả năng để có kết quả là 0: 0&0, 1&0, 0&1. Nghĩa là có 3 khả năng cho bit thứ i của số a và b, nhân 3 vào kết quả.
  • Nếu bit = 1, có 1 khả năng để có kết quả là 1: 1 & 1. Tương tự, nhân 1 vào kết quả.
Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

const ll MOD = 1e9 + 7;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // input
    int n, k;
    cin >> n >> k;

    //solve
    ll res = 1;
    for(int i = 0; i < k; i++)
        if ((n&(1<<i)) == 0) (res *= 3) %= MOD;

    // ouput
    cout << res;

    return 0;
}
Độ phức tạp

O(k)