3209. Number of Subarrays With AND Value of K

#define ll long long

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k)
    {
        unordered_map<int, ll> map;
        ll res = 0;

        for (int x : nums)
        {
            unordered_map<int, long long> map2;
            for (auto& [y, count] : map)
            {
                map2[y & x] += count;
            }
            map2[x] += 1;
            map = map2;
            res += map[k];
        }
        return res;
    }
};

• T: $O(N * M)$
• S: $O(M)$