Hiểu bài toán

Bài toán yêu cầu tính tổng phức tạp: $$\sum^{N}_{i=1}\sum^{N}_{j=1} (A_i \text{or} A_j) \text{xor} (A_j \text{and} A_i)$$ Tuy nhiên, theo các giải pháp và mẫu thử, công thức thực tế được sử dụng là: $$\sum^{N}_{i=1}\sum^{N}_{j=1} (A_i \text{or} A_j) \oplus (A_i \text{and} A_j)$$ hoặc một biến thể tương tự cho cặp $(i, j)$ với $i \le j$. Ta có nhận xét bitwise:

• $Ai \text{or} Aj = (Ai \text{and} Aj) + (Ai \text{xor} Aj)$
• Do đó: $(Ai \text{or} Aj) \oplus (Ai \text{and} Aj) = ((Ai \text{and} Aj) + (Ai \text{xor} Aj)) \oplus (Ai \text{and} Aj)$. Vì bitwise sum không đơn giản bằng XOR, ta xét từng bit.
• Bit của $(Ai \text{or} Aj)$ là 1 nếu ít nhất một trong hai bit của $Ai, Aj$ là 1.
• Bit của $(Ai \text{and} Aj)$ là 1 nếu cả hai bit đều là 1.
• Bit của phép XOR này là 1 nếu bit của $(Ai \text{or} Aj)$ khác bit của $(Ai \text{and} Aj)$.
  • Trường hợp 1: Cả hai bit đều 0. OR=0, AND=0. XOR=0.
  • Trường hợp 2: Một bit 0, một bit 1. OR=1, AND=0. XOR=1.
  • Trường hợp 3: Cả hai bit đều 1. OR=1, AND=1. XOR=0.
• Kết luận: Kết quả chỉ có bit tại vị trí $k$ là 1 nếu chính xác một trong hai số $Ai, Aj$ có bit $k$ là 1.
• Với mỗi vị trí bit $k$, số lượng cặp $(i, j)$ thỏa mãn là $cnt1[k] \times cnt0[k]$ (chọn 1 số có bit 1 và 1 số có bit 0).
• Tổng giá trị đóng góp của bit $k$ là $cnt1[k] \times cnt0[k] \times 2^k$.
• Với tổng $i \le j$, ta có thể tính tổng toàn bộ $i, j$ rồi trừ đi các phần tử chéo (i=j) hoặc điều chỉnh. Tuy nhiên, các solution bên dưới tính tổng $i, j$ không giới hạn $i \le j$ (tức là $N^2$ cặp). Nếu $N$ lớn, tổng này sẽ rất lớn.

Giả sử bài toán yêu cầu tính tổng cho tất cả các cặp $(i, j)$ (hoặc $\frac{1}{2}$ tổng này), giải pháp tập trung vào việc đếm bit.

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

Cách Brute Force (Sơ đồ gốc)

void solve_brute() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    long long total = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            total += (A[i] | A[j]) ^ (A[i] & A[j]);
        }
    }
    cout << total << "\n";
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Giải pháp này sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các cặp (i, j) có thể. Với mỗi cặp, nó tính trực tiếp biểu thức $(Ai \text{or} Aj) \oplus (Ai \text{and} Aj)$ và cộng dồn vào tổng. Đây là cách làm trực quan nhất nhưng không đủ nhanh cho N lên tới $10^5$.

Cách Bit Manipulation (Phân tích Bit)

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

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    long long total = 0;
    // Duyệt qua 31 bit (vì a_i < 2^31)
    for (int k = 0; k < 31; ++k) {
        long long count_1 = 0;
        for (int x : A) {
            if (x & (1 << k)) count_1++;
        }
        long long count_0 = N - count_1;
        // Đóng góp của bit thứ k là số lượng cặp (i, j) mà bit này khác nhau
        total += count_1 * count_0 * (1LL << k);
    }
    cout << total << "\n";
}

• Time Complexity: O(31 * N)
• Space Complexity: O(N)

Thay vì duyệt cặp, ta duyệt theo từng bit (từ 0 đến 30). Với mỗi bit $k$, ta đếm số lượng số có bit $k$ là 1 ($cnt1$) và số lượng số có bit $k$ là 0 ($cnt0$). Theo phân tích toán học, bit $k$ của kết quả chỉ bằng 1 nếu một trong hai số có bit 1 và số còn lại có bit 0. Số lượng cặp thỏa mãn là $cnt1 \times cnt0$. Giá trị đóng góp là $cnt1 \times cnt0 \times 2^k$. Độ phức tạp là $O(31N)$, rất nhanh.

Cách Bit Manipulation (Tối ưu nhập xuất)

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

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    ll total = 0;
    for (int k = 0; k < 31; ++k) {
        ll count_1 = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] & (1 << k)) count_1++;
        }
        ll count_0 = N - count_1;
        total += count_1 * count_0 * (1LL << k);
    }
    cout << total << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

• Time Complexity: O(31 * N)
• Space Complexity: O(N)

Đây là phiên bản hoàn chỉnh của phương pháp Bit Manipulation, bao gồm các tối ưu hóa nhập xuất chuẩn trong lập trình thi đấu (ios_base::sync_with_stdio(false); cin.tie(nullptr);) để đảm bảo tốc độ đọc dữ liệu nhanh nhất có thể. Logic tính toán tương tự như cách 2.

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

Bài học kinh nghiệm

• Biến đổi đại số: $(Ai \text{or} Aj) \oplus (Ai \text{and} Aj)$ chỉ bằng 1 tại những bit mà $Ai$ và $Aj$ khác nhau (một bên 1, một bên 0).
• Tách rời các bit: Bài toán có thể chia thành 31 bài toán con độc lập, mỗi bài tính tổng đóng góp của một bit.
• Tính toán theo cặp: Với mỗi bit, số lượng cặp $(i, j)$ thỏa mãn điều kiện bit khác nhau là $cnt{1} \times cnt{0}$.

Lỗi thường gặp

• Kiểu dữ liệu: Kết quả có thể rất lớn (lên tới $10^5 \times 10^5 \times 2^{31}$), cần sử dụng long long (64-bit) để lưu trữ.
• Sai lệch công thức: Đừng cố gắng tính trực tiếp phép cộng $(Ai \text{or} Aj) + (Ai \text{xor} Aj)$ rồi XOR với $Ai \text{and} Aj$. Hãy phân tích theo bit.
• Quên dịch chuyển bit: Khi tính giá trị đóng góp, phải nhân với $2^k$ (tức là $1LL \ll k$).
• Độ lớn input: Với $N=10^5$, giải pháp $O(N^2)$ sẽ chạy trong $10^{10}$ thao tác, chắc chắn bị timeout.