# [3209\. Number of Subarrays With AND Value of K](https://leetcode.com/problems/number-of-subarrays-with-and-value-of-k/)

1. **Initialization**: Start by initializing a hashmap `map` to keep track of the count of all bitwise AND results encountered so far. Also, initialize a variable `res` to store the count of valid subarrays.

2. **Iterate through the array**: For each element in the array, update a temporary hashmap `map2` with new bitwise AND results formed by ANDing the current element with all keys in `map`.

3. **Update the current element in the hashmap**: Additionally, add the current element itself to `map2` with a count of 1.

4. **Update the main hashmap**: Replace `map` with `map2` at the end of each iteration.

5. **Count the valid subarrays**: For each iteration, add the count of subarrays with the bitwise AND result equal to `k` (if present in the hashmap) to `res`.

6. **Return the result**: Finally, return `res` as the count of subarrays with bitwise AND equal to `k`.

:::spoiler Solution

#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;
    }
};

- 時間複雜度：$O(n * m)$
- 空間複雜度：$O(m)$
:::