**PROBLEM LINK** -

Author and Editoriallist - AmirRezaPoorAkhavan

Tester - MohammadSina Pakseresht

Second Tester - Shayan CheshmJahan

**DIFFICULTY** –

**PREREQUISITES** –

Dynamic-programming, bitmasks.

**EXPLANATION** –

In this problem let z = 20 and maxk = 2 ^ {20}.

Let’s prove that max(X, Y) \leq X | Y. Consider Y \leq X, so the left part of inequality is equal to X. It’s obvious that X \leq X | Y. So we have to count pairs such that max(X, Y) = X | Y.

Again consider Y \leq X, so the left part of inequality is equal to X, So max(X, Y) = X = X | Y \Rightarrow Y \in X (every true bit in Y is also true in X).

Now for each mask like M, let’s count the number of i’s, such that a_i \in M. It’s really important not to overcount here. For example, this code will overcount:

```
for(int i = 0; i < maxk; i++)
for(int j = 0; j < z; j++)
if(i >> j & 1)
dp[i] += dp[i ^ 1 << j];
```

You should use SOS (Sum over Subsets) dp trick, as mentioned here. Look, this code will work:

```
for(int j = 0; j < z; j++)
for(int i = 0; i < maxk; i++)
if(i >> j & 1)
dp[i] += dp[i ^ 1 << j];
```

Proof: Read *SoS Dynamic Programming solution* section in the link above.

Now the remaining part is easy. For each mask like M, calculate cnt_M, the number of times it occurred in A.

Now it’s simple that the answer is \sum {cnt_M \cdot (dp_M - cnt_M) + {cnt_M \choose 2} }.

Because there are dp_M - cnt_M indexes like i of the array such that a_i \in M and a_i \neq M so we should count them. In addition, there are {cnt_M \choose 2} pairs of elements of the array such that are equal to M, so we count them separately.

Time complexity: \mathcal{O}(n + z \cdot 2 ^ z)

**IMPLEMENTATION** -

Author’s code - here.

Tester’s code - here.

Second tester’s code - here.