<jupyter_start><jupyter_text>说明：    我们有一个非负整数数组 A。    对于每个（连续的）子数组 B = [A[i], A[i+1], ..., A[j]] （ i <= j），    我们对 B 中的每个元素进行按位或操作，获得结果 A[i] | A[i+1] | ... | A[j]。    返回可能结果的数量。 （    多次出现的结果在最终答案中仅计算一次。）示例 1：    输入：[0]    输出：1    解释：        只有一个可能的结果 0 。示例 2：    输入：[1,1,2]    输出：3    解释：        可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。        产生的结果为 1，1，2，1，3，3 。        有三个唯一值，所以答案是 3 。示例 3：    输入：[1,2,4]    输出：6    解释：        可能的结果是 1，2，3，4，6，以及 7 。 提示：    1、1 <= A.length <= 50000    2、0 <= A[i] <= 10^9 dp[i]表示以A[i]结尾的所有子数组的异或结果，其实是个set。转移方程式dp[i] = [b | A[i] for b in dp[i - 1]] + A[i]，即以A[i]结尾的所有子数组异或结果等于以A[i-1]结尾的所有子数组异或结果，和当前的A[i]异或，再加上A[i]这个结果。同时使用一个set保存所有的异或结果。最后返回这个结果set的长度。dp[i]的大小至多是32个，即 |dp[i]| <= 32 的证明：dp[i] = {A[i], A[i] | A[i - 1], A[i] | A[i - 1] | A[i - 2], … , A[i] | A[i - 1] | … | A[0]}，这个序列单调递增，通过把A[i]中的0变成1。A[i]最多有32个0。所以这个集合的大小 <= 32。举例：最坏情况 A = [8, 4, 2, 1, 0] 都是2^k。A[5] = 0，dp[5] = {0, 0 | 1, 0 | 1 | 2, 0 | 1 | 2 | 4, 0 | 1 | 2 | 4 | 8} = {0, 1, 3, 7, 15}.时间复杂度是O(32*N)，空间复杂度是O(32N).参考：https://blog.csdn.net/fuxuemingzhu/article/details/83511833<jupyter_code># 超时方案
class Solution:
    def subarrayBitwiseORs(self, A) -> int:
        res = set()
        N = len(A)
        memo = {}
        for i in range(N):
            for j in range(i+1, N+1):
                if tuple(A[i:j]) in memo:
                    continue
                val = A[i:j][0]
                for k in range(1, len(A[i:j])):
                    val |= A[i:j][k]
                res.add(val)
                memo[tuple(A[i:j])] = val
        return len(res)
solution = Solution()
solution.subarrayBitwiseORs([0])
class Solution:
    def subarrayBitwiseORs(self, A) -> int:
        res = set()
        cur = set()
        for a in A:
            cur = {n | a for n in cur} | {a}
            res |= cur
        return len(res)
solution = Solution()
solution.subarrayBitwiseORs([1,1,2])
class Solution:
    def subarrayBitwiseORs(self, A) -> int:
        pass
a = {1}
b = {2}
c = a | b
c<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.20009857072449483, 'fraction_numerical': 0.05963528831936915, 'mean_word_length': 2.242811501597444, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 8, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '130368', 'license': 'Apache-2.0', 'n_tokens_mistral': 1184, 'n_tokens_neox': 1162, 'n_words': 199, 'path': 'Dynamic Programming/1103/898. Bitwise ORs of Subarrays.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '2029'}