Given an array of integers A, find the number of triples of indices (i, j, k) such that:

0 <= i < A.length
0 <= j < A.length
0 <= k < A.length
A[i] & A[j] & A[k] == 0, where & represents the bitwise-AND operator.

 
Example 1:
Input: [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

 
Note:

1 <= A.length <= 1000
0 <= A[i] < 2^16

Difficulty: interview

Starter code:

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        counters = [0] * (1 << 16)
        counters[0] = len(A)
        for num in A:
            mask = (~num) & ((1 << 16) - 1)
            sm = mask
            while sm != 0:
                counters[sm] += 1
                sm = (sm - 1) & mask
        
        return sum(counters[num1 & num2] for num1 in A for num2 in A)


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        d = defaultdict(int)
        for a in A:
            for b in A:
                d[a & b] += 1
        return sum(d[ab] for c in A for ab in d if not(ab & c))

from collections import Counter

class Solution(object):
    def countTriplets(self, A):
        c = Counter(x & y for x in A for y in A)
        return sum(c[xy] for xy in c for z in A if xy & z == 0)


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        and_values = {}
        for x in A:
            for y in A:
                c = x & y
                if c in and_values:
                    and_values[c] += 1
                else:
                    and_values[c] = 1
        triplet_count = 0
        for a in and_values:
            for z in A:
                if a & z == 0:
                    triplet_count += and_values[a]
        return triplet_count
                
                        
                  


from collections import Counter
from functools import lru_cache
from itertools import product


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        
        @lru_cache(None)
        def count_and_zero(x):
            return sum(1 for a in A if a & x == 0)

        pair_and_count = Counter(
            x & y
            for x, y in product(A, A)
        )
        return sum(
            count_and_zero(x) * cnt
            for x, cnt in list(pair_and_count.items())
        )


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        memo = {}
        for i in A:
            for j in A:
                memo[i&j] = memo.get(i&j, 0)+1
        res = 0
        for num in A:
            for k in memo:
                if num&k==0:
                    res += memo[k]
        return res

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        t=0
        d={}
        for i in A:
            for j in A:
                a=i&j
                if a in d:
                    d[a]+=1
                else:
                    d[a]=1
        for k in d:
            for i in A:
                if k&i==0:
                    t+=d[k]
        return t

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        count =collections.defaultdict(int)
        ret = 0
        for i in A:
            for j in A:
                count[i & j] += 1
        for i in A:
            for j in count:
                if i & j == 0: ret += count[j]
        return ret

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n=len(A)
        count=0
        dic=collections.defaultdict(int)
        for i in range(n):
            for j in range(n):
                dic[(A[i]&A[j])]+=1
        ans=0
     #   print(dic)
        for ele in A:
            for res in dic:
                if res&ele==0:
                    ans+=dic[res]
        
        return ans

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        c = Counter(x&y for x in A for y in A)
        return sum([c[xy] for xy in c for z in A if xy&z == 0])

from collections import defaultdict
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        d = defaultdict(int)
        mask = (1<<16) - 1
        for i in A:
            high = mask ^ i
            j = high
            while j:
                d[j] += 1
                j = (j-1) & high
            d[0] += 1
        res = 0
        for i in A:
            for j in A:
                res += d[i&j]
        return res


#
# @lc app=leetcode id=982 lang=python3
#
# [982] Triples with Bitwise AND Equal To Zero
#
# https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/description/
#
# algorithms
# Hard (54.38%)
# Likes:    67
# Dislikes: 91
# Total Accepted:    5.5K
# Total Submissions: 10.2K
# Testcase Example:  '[2,1,3]'
#
# Given an array of integers A, find the number of triples of indices (i, j, k)
# such that:
# 
# 
# 0 <= i < A.length
# 0 <= j < A.length
# 0 <= k < A.length
# A[i] & A[j] & A[k] == 0, where & represents the bitwise-AND operator.
# 
# 
# 
# 
# Example 1:
# 
# 
# Input: [2,1,3]
# Output: 12
# Explanation: We could choose the following i, j, k triples:
# (i=0, j=0, k=1) : 2 & 2 & 1
# (i=0, j=1, k=0) : 2 & 1 & 2
# (i=0, j=1, k=1) : 2 & 1 & 1
# (i=0, j=1, k=2) : 2 & 1 & 3
# (i=0, j=2, k=1) : 2 & 3 & 1
# (i=1, j=0, k=0) : 1 & 2 & 2
# (i=1, j=0, k=1) : 1 & 2 & 1
# (i=1, j=0, k=2) : 1 & 2 & 3
# (i=1, j=1, k=0) : 1 & 1 & 2
# (i=1, j=2, k=0) : 1 & 3 & 2
# (i=2, j=0, k=1) : 3 & 2 & 1
# (i=2, j=1, k=0) : 3 & 1 & 2
# 
# 
# 
# 
# Note:
# 
# 
# 1 <= A.length <= 1000
# 0 <= A[i] < 2^16
# 
# 
#
from collections import Counter

class Solution:
    def countTriplets(self, A: List[int]) -> int:

        c = Counter(x & y for x in A for y in A)
        return sum(c[xy] for xy in c for z in A if xy & z == 0)
        



class Solution:
    def countTriplets(self, A: List[int]) -> int:
        l = len(A)
        Memo = {}
        for i in range(l):
            for j in range(i+1):
                t = A[i]&A[j]
                if t not in Memo:
                    Memo[t] = 0
                if i == j:
                    Memo[t] += 1
                else:
                    Memo[t] += 2
        r = 0
        for a in A:
            for key in Memo:
                if key&a == 0:
                    r += Memo[key]
        return r


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        d={}
        for i in A:
            for j in A:
                if(i&j in d):
                    d[i&j]+=1
                else:
                    d[i&j]=1
        c=0
        for i in A:
            for j in d:
                if(i&j==0):
                    c+=d[j]
        return c
            
                
                    
            
                


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        tmp = {}
        for a in A:
            for b in A:
                if a&b in tmp:
                    tmp[a&b]+=1
                else:
                    tmp[a&b]=1        
        ans = 0
        
        for k, t in tmp.items():
            for c in A:
                if c&k==0:
                    ans +=t
        return ans

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        mp = {}
        for i in A:
            for j in A:
                k = i & j
                mp[k] = mp.get(k, 0) + 1
        
        result = 0
        for i in A:
            for j in mp:
                if i & j == 0:
                    result += mp[j]
        return result


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        counter = Counter()
        for a in A:
            for b in A:
                counter[a&b] += 1
        
        res = 0
        for a in A:
            for b in counter:
                if a&b==0:
                    res += counter[b]
                    
        return res

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        dic = defaultdict(int)
        res = 0
        for i in A:
            for j in A:
                tmp = i&j
                dic[tmp] += 1
        for i in A:
            for j in dic:
                if i&j == 0:
                    res += dic[j]
        return res
'''
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        dic = defaultdict(int)
        res = 0
        for i in range(len(A)):
            for j in range(len(A)):
                num = A[i] & A[j]
                dic[num] += 1
        for i in range(len(A)):
            for j in dic:
                if A[i] & j == 0:
                    res += dic[j]
        return res
'''

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        cnt = collections.defaultdict(int)
        for i in A:
            for j in A:
                cnt[i&j]+=1
        res = 0
        for i in A:
            for j in cnt:
                if i & j == 0:
                    res += cnt[j]
        return res

from collections import defaultdict

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        counts = defaultdict(int)
        for x in A:
            for y in A:
                counts[x & y] += 1
        
        def dfs(z, xy, k):
            if k == -1:
                return counts[xy]
            
            answer = dfs(z, xy << 1, k - 1)
            if (z >> k & 1) == 0:
                answer += dfs(z, (xy << 1 | 1), k - 1)
            return answer
        
        answer = 0
        for z in A:
            answer += dfs(z, 0, 16)
        return answer


from collections import defaultdict

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        counts = defaultdict(int)
        for x in A:
            for y in A:
                counts[x & y] += 1
        
        def dfs(xy, z, k):
            if k == -1:
                return counts[xy]
            
            answer = dfs(xy << 1, z, k - 1)
            if (z >> k & 1) == 0:
                answer += dfs(xy << 1 | 1, z, k - 1)
            return answer
        
        answer = 0
        for z in A:
            answer += dfs(0, z, 16)
        return answer


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        
        B = [bin(a)[2:] for a in A]
        M, N = len(B), max(list(map(len, B)))
        B = [b.zfill(N) for b in B]
        
        dic = collections.defaultdict(set)
        for i in range(M):
            for j in range(N):
                if B[i][j] == '1':
                    dic[j].add(i)
        
        Venn = collections.defaultdict(list)
        cnt = 0
        for j in range(N):
            if len(dic[j]):
                cnt += (len(dic[j])) ** 3
                for i in range(j, 0, -1):
                    for prv in Venn[i]:
                        intersec = prv & dic[j]
                        if len(intersec):
                            cnt += ((-1) ** i) * (len(intersec)) ** 3
                            Venn[i + 1].append(intersec)
                Venn[1].append(dic[j])
        
        return M ** 3 - cnt
        
        
#         # ans = 0
#         n = len(A)
        
#         @lru_cache(None)
#         def dfs(i, pre):
#             if i == 4 and not pre:
#                 return 1
#             ans = 0
#             for a in A:
#                 if (i > 1 and not pre & a) or (i == 1 and not a):
#                     ans += n ** (3 - i)
#                 elif i < 3:
#                     ans += dfs(i + 1, pre & a if i > 1 else a)
#             return ans
        
        
#         return dfs(1, None)


class Solution:
    def countTriplets(self, nums):
        count_map = collections.Counter(i & j for i in nums for j in nums)
        return sum(count_map[key] for num in nums for key in count_map if num & key == 0)

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        # O(2**16*n), since a&b<= a,b<= 2**16
        
        dp = collections.defaultdict(int)
        for n1 in A:
            for n2 in A:
                dp[n1&n2]+=1
        
        res = 0
        for n in A:
            for k,v in dp.items():
                if not k&n:
                    res+=v
        return res

from collections import defaultdict


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        pairs = defaultdict(int)
        for a in A:
            for b in A:
                pairs[a & b] += 1
        res = 0
        for a in A:
            for p, cnt in pairs.items():
                if not a & p:
                    res += cnt
        return res

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        # O(N^2)
        two_and_count = collections.Counter()
        res = 0
        
        for idx, x in enumerate(A):
            if x == 0: # x & x & x
                res += 1
            # y & x & x -> 3
            new_two_and = collections.Counter([x])
            for idy in range(idx):
                if x & A[idy] == 0:
                    res += 3
                new_two_and[A[idy] & x] += 2

            for v, c in two_and_count.items():
                if x & v == 0:
                    res += 3 * c
            two_and_count += new_two_and
        return res

    def countTriplets_II(self, A: List[int]) -> int:
        M = 3
        N = 1 << 16
        dp = [[0] * (N) for _ in range(M + 1)]
        dp[0][N - 1] = 1
        
        for m in range(1, M + 1):
            for v in range(N):
                for a in A:
                    dp[m][v & a] += dp[m - 1][v]
        return dp[M][0]

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        counter = collections.Counter()
        
        for i in A:
            for j in A:
                counter[i&j] += 1
        
        result = 0        
        for k in A:
            for v in counter:
                if k & v == 0:
                    result += counter[v]
        return result

import numpy as np
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        memo=dict()
        for i in range(len(A)):
            for j in range(i,len(A)):
                r=A[i]&A[j]
                memo[r]=memo.get(r,0)+(1 if i==j else 2) 
        ret=0
        for i in range(len(A)):
            for k in memo:
                if A[i]&k==0:
                    ret+=memo[k]
        return ret

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        d={}
        res=0
        for a in A:
            for b in A:
                t=a&b
                if t in d:
                    d[t]+=1
                else:
                    d[t]=1
        for a in A:
            for k,v in list(d.items()):
                if a&k==0:
                    res+=v
        return res


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        cnt = collections.Counter()
        A = list(collections.Counter(A).items())
        result = 0
        for i, k1 in A:
            for j, k2 in A:
                cnt[i & j] += k1 * k2
        cnt = list(cnt.items())
        for i, k1 in A:
            if i == 0:
                result += k1 * n * n
                continue
            for j, k2 in cnt:
                if i & j == 0:
                    result += k1 * k2
        return result

class Solution:
    def countTriplets(self, A: List[int]) -> int:
#         N = 1 << 16
#         M = 3
#         dp = [[0]*N for _ in range(M+1)]
#         dp[0][N - 1] = 1
        
#         for i in range(M):
#             for k in range(N):
#                 for a in A:
#                     dp[i+1][k&a] += dp[i][k]
        
#         return dp[M][0]
    
        N = len(A)
        ans = 0
        count = collections.Counter()

        for i in range(N):
            for j in range(N):
                count[A[i]&A[j]] += 1
                
        for k in range(N):
            for v in count:
                if A[k] & v == 0:
                    ans += count[v]
        return ans

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        umap = collections.Counter(A)
        n = len(A)
        mask = (1 << 16) - 1
        
        for i in range(n):
            for j in range(i+1, n):
                key = A[i] & A[j]
                if key not in umap:
                    umap[key] = 0
                umap[key] += 2
        
        result = 0
        for a in A:
            d = (~a) & mask
            key = d
            result += umap.get(d, 0)
            while d > 0:
                d = (d-1)&key
                result += umap.get(d, 0)
        return result


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        N = len(A)
        ans = 0
        count = collections.Counter()
        for i in range(N):
            for j in range(N):
                count[A[i] & A[j]] += 1
        for k in range(N):
            for v in count:
                if A[k] & v == 0:
                    ans += count[v]
        
        return ans

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        cnt = collections.Counter()
        result = 0
        for i in A:
            for j in A:
                cnt[i & j] += 1
        for i in A:
            for j, k in cnt.items():
                if i & j == 0:
                    result += k
        return result

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        cnt=0
        d={}
        for i in range(len(A)):
            for j in range(len(A)):
                if A[i]&A[j] not in d:
                    d[A[i]&A[j]]=1
                else:
                    d[A[i]&A[j]]+=1
                    
        for i in range(len(A)):
            for j in d:
                if A[i]&j==0:
                    cnt+=d[j]
                    
                    
        return cnt


# class Solution:
#     def countTriplets(self, A: List[int]) -> int:
#         N, M = 1<<16, 3
#         dp = [[0]*N for _ in range(M+1)]
#         dp[0][-1] = 1
#         for m in range(M):
#             for n in range(N):
#                 for a in A:
#                     dp[m+1][a&n] += dp[m][n]
#         return dp[-1][0]


class Solution:
    def countTriplets(self, A: 'List[int]') -> 'int':
        N = len(A)
        ans = 0
        count = collections.Counter()

        for i in range(N):
            for j in range(N):
                count[A[i]&A[j]] += 1
                
        for k in range(N):
            for v in count:
                if A[k] & v == 0:
                    ans += count[v]
        return ans

from collections import defaultdict
from collections import Counter

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        combo = collections.Counter(x&y for x in A for y in A)
            
        res = 0
        for a in A:
            for k,v in list(combo.items()):
                if a&k==0:
                    res+=v
        return res
                        
        
 


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        combo = collections.Counter(x&y for x in A for y in A)
        return sum(combo[k] for z in A for k in combo if z&k == 0)

from collections import defaultdict
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        ans = 0
        A_counts = defaultdict(lambda: 0)
        for num in A:
            A_counts[num] += 1
        
        counts = defaultdict(lambda: 0)
        for n1, count1 in list(A_counts.items()):
            for n2, count2 in list(A_counts.items()):
                counts[n1&n2] += count1*count2
                
        for n1, count1 in list(A_counts.items()):
            for n2, count2 in list(counts.items()):
                if n1 & n2 == 0:
                    ans += count1*count2
        return ans


from collections import Counter
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        ## https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/discuss/227309/C%2B%2B-naive-O(n-*-n)
        cnt = Counter()
        for a in A:
            for b in A:
                cnt[a&b] += 1
        
        res = 0
        for a in A:
            for k, v in cnt.items():
                if a&k==0:
                    res += v
        
        return res

from collections import defaultdict
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        ans = 0
        A_counts = defaultdict(lambda: 0)
        for num in A:
            A_counts[num] += 1
        
        counts = defaultdict(lambda: 0)
        for n1, count1 in list(A_counts.items()):
            for n2, count2 in list(A_counts.items()):
                counts[n1&n2] += count1*count2
                
        for n in A:
            for num, count in list(counts.items()):
                if num & n == 0:
                    ans += count
        return ans


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        count=0
        dic=dict()
        for i in range(len(A)):
            for j in range(i,len(A)):
                r=A[i]&A[j]
                dic[r]=dic.get(r,0)+(1 if i==j else 2)
        result=0
        for i in range(len(A)):
            for k in dic:
                if A[i]&k==0:
                    result+=dic[k]
                
        return result
                    


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        counters = defaultdict(int)
        counters[0] = len(A)
        for num in A:
            mask = (~num) & ((1 << 16) - 1)
            sm = mask
            while sm != 0:
                counters[sm] += 1
                sm = (sm - 1) & mask
        
        return sum(counters[num1 & num2] for num1 in A for num2 in A)


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        
        N = len(A)
        ans = 0
        count = dict()

        for i in range(N):
            for j in range(N):
                tmp = A[i]&A[j]
                if tmp not in count:
                    count[tmp] = 1
                else:
                    count[tmp] += 1
                
        for k in range(N):
            for v in count:
                if A[k] & v == 0:
                    ans += count[v]
        return ans
        


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        d={}
        ans=0
        for i in range(len(A)):
            for j in range(len(A)):
                a=A[i]&A[j]
                d[a]=d.get(a,0)+1
        
        for i in range(len(A)):
            for j in list(d.keys()):
                if A[i]&j==0:
                    ans+=d[j]
        return ans
                    
        
        
        
        
        
        
        


import collections

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        
        N = len(A)
        ans = 0
        count = collections.Counter()

        for i in range(N):
            for j in range(N):
                count[A[i]&A[j]] += 1
                
        for k in range(N):
            for v in count:
                if A[k] & v == 0:
                    ans += count[v]
        return ans
        


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        C = defaultdict(int)
        for i in range(n):
            C[A[i]] += 1
            for j in range(i + 1, n):
                C[A[i] & A[j]] += 2
        return sum(c * sum((x & y) == 0 for y in A) for x, c in C.items())

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        C = defaultdict(int)
        for i, x in enumerate(A):
            C[x] += 1
            for j in range(i + 1, n):
                C[x & A[j]] += 2
        return sum(c * sum((x & y) == 0 for y in A) for x, c in C.items())

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        C = defaultdict(int)
        for i in range(n):
            C[A[i]] += 1
            for j in range(i + 1, n):
                C[A[i] & A[j]] += 2
        res = 0
        for x, c in C.items():
            res += c * sum((x & y) == 0 for y in A)
        return res

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        memo = dict()
        for i in range(len(A)):
            for j in range(i,len(A)):
                r=A[i]&A[j]
                memo[r]=memo.get(r,0)+(1 if i==j else 2) 
        ret=0
        for i in range(len(A)):
            for k in memo:
                if A[i]&k==0:
                    ret+=memo[k]
        return ret

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        n2 = n*n
        dp = {}
        ways = 0
        for i in range(n):
            for j in range(n):
                res = A[i] & A[j]
                dp[res] = dp.get(res, 0) + 1
        for i in range(n):
            for tgt, ct in dp.items():
                if A[i] & tgt == 0:
                    ways += ct
                    #print(A[i], tgt, ct)
        return ways

from collections import defaultdict
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        n = len(A)
        ans = 0
        counts = defaultdict(lambda: 0)
        for i in range(n):
            for j in range(n):
                counts[A[i]&A[j]] += 1
                
        for k in range(n):
            for num, count in list(counts.items()):
                if num & A[k] == 0:
                    ans += count
        return ans
                        
#         (a & b) & c== 0  
        
# # 0010
# # 0001
# # 1101
# # 0011
# # 1110


from collections import defaultdict
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        mp = defaultdict(int) # key: elem_value, value: number_of_complement_elements
        mask = (1 << 16) - 1
        for x in A:
            y = mask ^ x
            s = y
            while s:
                mp[s] += 1
                s = (s - 1) & y
        n = len(A)
        cnt = 0
        for i in range(n):
            if A[i] == 0:
                cnt += n * n
                continue
            for j in range(n):
                if A[i] & A[j] == 0:
                    cnt += n
                    continue
                cnt += mp[A[i] & A[j]]
        return cnt

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        from collections import defaultdict
        dic=defaultdict(int)
        n=len(A)
        dp=defaultdict(int)
        for i in range(n):
            for j in range(n):
                dic[(i,j)] = A[i]&A[j]
                dp[A[i]&A[j]]+=1
        ans=0
        for i in range(n):
            for x in dp:
                if x&A[i]==0:
                    ans+=dp[x]
        return ans


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        d = dict()
        for i in range(len(A)):
            for j in range(len(A)):
                product = A[i] & A[j]
                if product in d:
                    d[product]+=1
                else:
                    d[product] = 1
        ans = 0
        for i in range(len(A)):
            for k,v in d.items():
                if A[i]& k == 0:
                    ans+=v
        return ans

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        c = Counter(x & y for x in A for y in A)
        return sum(c[xy] for xy in c for z in A if xy & z == 0)
#         bitsOneDict = {\"@\": 20}
#         ans = 0
#         ALen = len(A)
#         for j, num in enumerate(A):
#             i = 0
#             pointer = bitsOneDict
#             while num > 0:
#                 if num & 1:
#                     if i not in pointer:
#                         pointer[i] = {}
#                     if \"@\" not in pointer:
#                         pointer[\"@\"] = i
#                     else:
#                         pointer[\"@\"] = max(i, pointer[\"@\"])
#                     pointer = pointer[i]
#                 num >>= 1
#                 i += 1
#             if \"$\" in pointer:
#                 pointer[\"$\"].add(j)
#             else:
#                 pointer[\"$\"] = set([j])
#             if \"@\" not in pointer:
#                 pointer[\"@\"] = i+1
#             else:
#                 pointer[\"@\"] = max(i+1, pointer[\"@\"])
                
#         for j1, num1 in enumerate(A):
#             for j2 in range(j1, ALen):
#                 num2 = A[j2]
#                 num12 = num1 & num2
#                 if num12 == 0:
#                     if j1 == j2:
#                         ans += ALen
#                     else:
#                         ans += ALen*2
#                 else:
#                     pointers = [bitsOneDict]
#                     i = 0          
#                     subAns = set()
#                     while i < 16:
#                         if num12 & 1 == 0:
#                             newPointers = []
#                             for k in range(len(pointers)-1, -1, -1):
#                                 pointer = pointers[k]
#                                 if i in pointer:
#                                     newPointers.append(pointer[i])
#                                 else:
#                                     if i > pointer[\"@\"]:
#                                         if \"$\" in pointer:
#                                             subAns |= pointer[\"$\"]
#                                         pointers.pop(k)   
#                             pointers += newPointers
#                         num12 >>= 1
#                         i += 1
#                     for pointer in pointers:
#                         if \"$\" in pointer:
#                             subAns |= pointer[\"$\"]
#                     if j1 == j2:
#                         ans += len(subAns)
#                     else:
#                         ans += len(subAns)*2
#         return ans


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        
        # ans = 0
        n = len(A)
        
        @lru_cache(None)
        def dfs(i, pre):
            if i == 4 and not pre:
                return 1
            ans = 0
            for a in A:
                if (i > 1 and not pre & a) or (i == 1 and not a):
                    ans += n ** (3 - i)
                elif i < 3:
                    ans += dfs(i + 1, pre & a if i > 1 else a)
            return ans
        
        
        return dfs(1, None)

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        memo=dict()
        for i in range(len(A)):
            for j in range(i,len(A)):
                r=A[i]&A[j]
                memo[r]=memo.get(r,0)+(1 if i==j else 2) 
        ret=0
        for i in range(len(A)):
            for k in memo:
                if A[i]&k==0:
                    ret+=memo[k]
        return ret

from collections import Counter
class Solution:
    def countTriplets(self, A: List[int]) -> int:
        c = Counter()

        for val in A:
            val = (~val) & 0xffff
            mask = val
            c[val] += 1

            while val > 0:
                val = (val-1) & mask
                c[val] += 1

        ans = 0
        for v1 in A:
            for v2 in A:
                val = v1 & v2
                if val in c:
                    ans += c[val]
        return ans


class Solution:
    def countTriplets(self, A: List[int]) -> int:
        
        tot = 1<<16
        cnt = [0 for _ in range(tot)]
        for a in A:
            for b in A:
                cnt[a&b]+=1
        
        ans = 0
        for e in A:
            s = 0
            while s<tot:
                if s&e==0:
                    ans += cnt[s]
                    s += 1
                else:
                    s += (e&s)
        return ans

class TrieNode:
    def __init__(self):
        self.children = [None] * 2
        self.count = 0
        self.cache = {}
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
        #self.cache = {}
        
    def insert(self, num):
        now = self.root
        for j in range(16):
            i = num & 1
            if not now.children[i]:
                now.children[i] = TrieNode()
            now = now.children[i]
            num >>= 1
        now.count += 1
    
    def match(self, num):
        return self.count_match(self.root, num)
        
    def count_match(self, now, num):
        if not now:
            return 0
        
        if num in now.cache:
            return now.cache[num]
        
        if now.count > 0:
            return now.count
                
        
        bit = num & 1
        next_num = num >> 1
        if bit:
            now.cache[num] = self.count_match(now.children[0], next_num)
        
        else:
            tmp = 0
            tmp += self.count_match(now.children[0], next_num)
            tmp += self.count_match(now.children[1], next_num)
            now.cache[num] = tmp
        
        return now.cache[num]
        
    

class Solution:
    def countTriplets(self, A: List[int]) -> int:
        # Tries: 16 * n^2
        
        trie = Trie()
        
        # build Trie
        for num in A:
            trie.insert(num)
        
        cache = {}
        ans = 0
        for num1 in A:
            for num2 in A:
                num = (num1 & num2)
                a = trie.match(num)
                ans += a
                #print(num1, num2, a)
        return ans