시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 67 | 46 | 28 | 65.116% |
XOR is a bitwise operator that evaluates the resulting bit into 1 if and only if their corresponding input bits differ (one of them is 1 while the other is 0). XOR operator is usually written with a symbol ⊕, or in most programming languages, the character ^(caret). For example, (10 ⊕ 6) = 12.
10 => 1010 6 => 0110 ----- ⊕ 1100 => 12
In this problem, you are given an integer N and a set of integers S1..M. Your task is to count how many pairs of integers <A, B> such that 1 ≤ A, B ≤ (A ⊕ B) ≤ N, and (A ⊕ B) ∉ S.
For example, let N = 10 and S1..4 = {4, 6, 7, 10}. There are 6 pairs of <A, B> that satisfy the condition.
Observe that a pair such as <2, 4> does not satisfy the condition for this example as (2 ⊕ 4) = 6 but 6 ∈ S. Another pair such as <5, 1> also does not satisfy the condition as it violates the requirement A, B ≤ (A ⊕ B).
Input begins with a line containing two integers N M (1 ≤ N ≤ 106; 1 ≤ M ≤ 100 000) representing the given N and the size of the set of integers S1..M. The next line contains M integers Si (1 ≤ Si ≤ 106) representing the set of integers S1..M.
Output contains an integer in a line representing the number of <A, B> such that 1 ≤ A, B ≤ (A ⊕ B) ≤ N and (A ⊕ B) ∉ S1..M.
10 4 4 6 7 10
6
This is the example from the problem description.
8 5 4 3 5 8 1
10
There are 10 pairs of <A, B> that satisfy the condition.
20 7 3 7 18 15 12 18 19
50
5 6 1 2 3 4 5 6
0