<p>Given an array of integers <code>nums</code> and an integer <code>k</code>, return the number of <span data-keyword="subarray-nonempty">subarrays</span> of <code>nums</code> where the bitwise <code>AND</code> of the elements of the subarray equals <code>k</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>All subarrays contain only 1&#39;s.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,2], k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>Subarrays having an <code>AND</code> value of 1 are: <code>[<u><strong>1</strong></u>,1,2]</code>, <code>[1,<u><strong>1</strong></u>,2]</code>, <code>[<u><strong>1,1</strong></u>,2]</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3], k = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>Subarrays having an <code>AND</code> value of 2 are: <code>[1,<b><u>2</u></b>,3]</code>, <code>[1,<u><strong>2,3</strong></u>]</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>
</ul>

from array import array

def and_sum(bit_freq: List[int], size: int) -> int:
    ret = 0
    for freq in reversed(bit_freq):
        ret <<= 1
        ret |= (freq == size)
    return ret

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        ret = 0

        l, r = 0, 0
        bit_freq = array('i', [0] * 30)
        for i, num in enumerate(nums):
            if (num & k) == k:
                for bit in range(30):
                    bit_freq[bit] += (num & 1)
                    num >>= 1

                while and_sum(bit_freq, i - r + 1) == k:
                    delnum = nums[r]
                    for bit in range(30):
                        bit_freq[bit] -= (delnum & 1)
                        delnum >>= 1
                    r += 1
                
                ret += r - l
            else:
                bit_freq = array('i', [0] * 30)
                l, r = i + 1, i + 1

        return ret
4641