发表于 2024.08.10

• 第四题反而没那么难想，其实就是计数DP。记dp[i][j]为以nums[i]结尾的子数组中，按位与值为j的数目。那么有状态转移方程：dp[i][j & nums[i]] += dp[i - 1][j]。由于j的范围是0~2^10，因此可以使用dict来存储dp数组。

  class Solution:
      def countSubarrays(self, nums: List[int], k: int) -> int:
          cur_map = {nums[0]: 1}  # 初始状态
          ans = int(nums[0] == k)
          for i in range(1, len(nums)):
              new_map = defaultdict(int)
              new_map[nums[i]] = 1
              for prev_res, cnt in cur_map.items():
                  new_map[prev_res & nums[i]] += cnt
              cur_map = new_map
              ans += cur_map.get(k, 0)
          return ans

• LC 题目链接