Hiểu bài toán

Cho hai số nguyên không âm $N$ và $X$ ($0 \leq X \leq N$). Đếm số lượng giá trị $X$ thỏa mãn điều kiện $N + X = N \oplus X$.

Phân tích điều kiện:

• $N + X = N \oplus X + 2 \cdot (N \& X)$. Do đó, điều kiện đề bài tương đương với $N \& X = 0$ (tức là $N$ và $X$ không có bit nào cùng bằng 1).
• Vì $X \leq N$, các bit của $X$ chỉ có thể là 1 ở những vị trí mà tại đó bit của $N$ là 0. Nếu $N$ có bit 1 tại vị trí $k$ ($Nk=1$) thì $X$ bắt buộc phải có bit 0 tại vị trí đó ($Xk=0$). Nếu $N$ có bit 0 ($N_k=0$) thì $X$ có thể chọn bit 0 hoặc 1.

Vậy, bài toán quy về: Với mỗi bit 0 của $N$, ta có 2 lựa chọn (0 hoặc 1) cho bit tương ứng của $X$. Nếu $N$ có $k$ bit 0 (từ bit 0 đến bit cao nhất của $N$), số lượng giá trị $X$ là $2^k$.

Các cách tiếp cận

Cách Duyệt qua các bit

#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int ti = 1; ti <= T; ti++) {
        u64 N;
        cin >> N;
        u64 cnt0 = 0;
        u64 x = N;
        while (x > 0) {
            if ((x & 1ULL) == 0) cnt0++;
            x >>= 1;
        }
        u64 res = 1ULL << cnt0;
        cout << "Case #" << ti << ": " << res << "\n";
    }
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Hàm main xử lý từng test case. Biến cnt0 đếm số bit 0 của $N$. Vòng lặp while chạy cho đến khi $N$ trở về 0. Ở mỗi bước, nó kiểm tra bit cuối cùng của $N$ (dùng x & 1). Nếu bit đó là 0, tăng cnt0 lên 1. Sau đó dịch $N$ sang phải 1 bit (>> 1) để kiểm tra bit tiếp theo. Kết quả là $2^{cnt0}$.

Cách Quy hoạch động tính lũy thừa

#include <bits/stdc++.h>
using namespace std;

int dem_bit_0(long long n){
    int dem=0;
    while (n){
        dem+= ((n&1)==0?1:0);
        n=n>>1;
    }
    return dem;
}

long long luy_th(int n){
    if (n==1) return 2;
    else if (n==0) return 1;

    long long a= luy_th(n/2);
    if (n%2==0) return a*a;
    else return a*a*2;
}
int main(){
    int t;
    cin>>t;
    long long n;
    for (int i=1; i<=t; i++){
        cin>>n;
        cout<<"Case #"<<i<<": ";
        int bit0=dem_bit_0(n);
        cout<<luy_th(bit0)<<'\n';
    }
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(log N)

Phương pháp này có hai phần:

1. dem_bit_0: Tính số bit 0 của $N$ tương tự như cách 1.
2. luy_th: Tính $2^n$ bằng cách chia đôi (binary exponentiation) đệ quy. Thay vì dùng phép dịch bit 1ULL << cnt0 trực tiếp (có thể bị tràn số nếu cnt0 quá lớn so với unsigned long long nhưng trong giới hạn đề bài $N \le 10^{16$ thì cnt0 tối đa ~54, đủ dùng), phương pháp này tính lũy thừa an toàn hơn cho các số lớn hoặc nếu muốn tránh tràn số bit.

Cách Công thức trực tiếp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        unsigned long long n;
        cin >> n;
        // Đếm số bit 0 của n
        int cnt = 0;
        while (n) {
            if ((n & 1) == 0) cnt++;
            n >>= 1;
        }
        // In ra 2^cnt
        cout << "Case #" << i << ": " << (1ULL << cnt) << "\n";
    }
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Đây là cách tối ưu và ngắn gọn nhất của Solution 1. Nó kết hợp đếm bit 0 và tính lũy thừa bằng phép dịch bit (1ULL << cnt). Với $N \le 10^{16}$, số bit 0 tối đa khoảng 54 (vì $2^{54} > 10^{16}$), nên phép dịch bit này an toàn tuyệt đối với unsigned long long (64 bit).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Điều kiện $N + X = N \oplus X$ tương đương với việc $N$ và $X$ không có bit nào cùng bằng 1 (tức $N \& X = 0$).
• Với mỗi bit 0 của $N$, ta có 2 sự lựa chọn cho bit của $X$ (0 hoặc 1). Do đó, kết quả là $2^{\text{số bit 0 của } N}$.
• Nếu $N$ là số lũy thừa của 2 (ví dụ 8 là 1000), nó chỉ có 1 bit 0 (ở vị trí bit 0), do đó kết quả là $2^1 = 2$? Sai. $N=8$ (1000) có các bit từ 0 đến 3. Bit 0,1,2 là 0 (3 bit 0). Kết quả là $2^3 = 8$. Cần đếm tất cả các bit 0 nằm trong phạm vi từ bit 0 đến bit cao nhất của $N$. Ví dụ $N=5$ (101) có bit 1 là 0, bit 0 là 1. Đếm bit 0: bit 1 là 0 -> 1 bit 0. Kết quả $2^1 = 2$. Ví dụ $N=8$ (1000, 4 bit): các bit 0 là bit 0, 1, 2 -> 3 bit 0 -> $2^3 = 8$. Ví dụ $N=10$ (1010, 4 bit): các bit 0 là bit 0, 2 -> 2 bit 0 -> $2^2 = 4$.

Lỗi thường gặp

• Quên đếm các bit 0 ở các vị trí thấp hơn bit 1 cao nhất của $N$.
• Sử dụng số có dấu (long long) khi dịch bit phải算术 shift (giữ nguyên bit dấu) thay vì logic shift (dùng unsigned long long).
• Tràn số khi tính $2^k$ nếu dùng mảng hoặc biến quá nhỏ, nhưng với unsigned long long và $N \le 10^{16}$ thì 1ULL << cnt là an toàn.