Tối đa hóa OR bitwise của mảng bằng cách nhân một phần tử trong C++

Đề bài

Cho mảng N số nguyên. Có thể chọn tối đa 1 phần tử và nhân nó với x^K (x mũ K). Tối đa hóa OR bitwise của toàn mảng sau phép toán.

Ví dụ: arr={4,3,6,1}, K=2, x=3 → x^K=9. Nhân 6*9=54. OR = 4|3|54|1 = 55.

Thuật toán (Prefix/Suffix OR)

1. Tính power = x^K.
2. Tính mảng pref[i] = OR của arr[0..i-1].
3. Tính mảng suff[i] = OR của arr[i+1..n-1].
4. Với mỗi i, giá trị OR nếu nhân arr[i] = pref[i] | (arr[i]*power) | suff[i]. Lấy max.

Ví dụ minh họa (C++)

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

int getMaxOr(int* arr, int n, int k, int x) {
    long long power = 1;
    for (int i = 0; i < k; ++i) power *= x;

    vector<int> pref(n+1, 0), suff(n+1, 0);
    for (int i = 0; i < n; ++i) pref[i+1] = pref[i] | arr[i];
    for (int i = n-1; i >= 0; --i) suff[i] = suff[i+1] | arr[i];

    int res = 0;
    for (int i = 0; i < n; ++i) {
        long long val = (long long)arr[i] * power;
        res = max(res, pref[i] | (int)val | suff[i+1]);
    }
    return res;
}

int main() {
    int arr[] = {4, 3, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2, x = 3;
    cout << "Ket qua = " << getMaxOr(arr, n, k, x) << endl;
    return 0;
}

Kết quả

Ket qua = 55