Bitwise ORs of Subarrays ใน C++

คำอธิบายปัญหา

กำหนดอาร์เรย์ A ของจำนวนเต็มไม่ติดลบ สำหรับทุก subarray เรียงติดกัน คำนวณ bitwise OR ของสมาชิกทั้งหมด ต้องการจำนวนผลลัพธ์ที่แตกต่างกัน

ตัวอย่าง: [1,1,2] → subarrays: [1],[1],[2],[1,1],[1,2],[1,1,2] → ORs: 1,1,2,1,3,3 → distinct: {1,2,3} → 3

วิธีแก้ปัญหา (Set DP)

1. curr = set ของ ORs ของ subarrays ที่ลงท้ายที่ i-1
2. สำหรับ A[i]: newCurr = {A[i]} ∪ {x | A[i] for x in curr}
3. รวม newCurr เข้า global set
4. curr = newCurr

ขนาด set จำกัดด้วยจำนวนบิต (สูงสุด 32 บิต → set size <= 32)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        unordered_set<int> allResults;
        unordered_set<int> curr;
        
        for(int x : A) {
            unordered_set<int> next;
            next.insert(x);
            for(int val : curr) {
                next.insert(val | x);
            }
            curr = move(next);
            allResults.insert(curr.begin(), curr.end());
        }
        return allResults.size();
    }
};

int main() {
    vector<int> v = {1,1,2};
    Solution ob;
    cout << ob.subarrayBitwiseORs(v);
    return 0;
}

อินพุต

[1,1,2]

เอาต์พุต

3