LC 898. Bitwise ORs of Subarrays

https://leetcode.com/problems/bitwise-ors-of-subarrays/

这题目我总想存在某些取巧的办法，但实际上一个二重循环就能搞定。不过虽然形式上是二重循环，但本质还是一重循环。因为我们可以证明，每次循环次数不会超过32个，也就是len(cons) <= 32,

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        n = len(A)
        ans, cons = set(), set()
        for i in range(n):
            cons = {x | A[i] for x in cons}
            cons.add(A[i])
            ans |= cons
        return len(ans)

这里cons表示的是，当处理到ith个元素的时候，所有我们可以通过bit or得到的值。当我们执行下面语句

cons = {x | A[i] for x in cons}
cons.add(A[i])

那么每次 `x|A[i]` 如果产生元素的话至少会有一个新的1出来，而因为A[i]<=10**9可以使用31个bit表示，所以最多增加到31个1就不会多了。更准确地说，如果A[i]里面有m个1的话，那么这个集合最多(31-m)+1个元素。