Beautiful quadruples challenge

Problem statement
We call an quadruple of positive integers, (W, X, Y, Z), beautiful if the following condition is true:

W \oplus X \oplus Y \oplus Z \ne 0

Note: \oplus is the bitwise XOR operator.

Given A, B, C and D, count the number of beautiful quadruples of the form (W, X, Y, Z) where the following constraints hold:

1 \le W \le A
1 \le X \le B
1 \le Y \le C
1 \le Z \le D

When you count the number of beautiful quadruples, you should consider two quadruples as same if the following are true:
– They contain same integers.
– Number of times each integers occur in the quadruple is same.

For example (1, 1, 1, 2) and (1, 1, 2, 1) should be considered as same.

Input Format
A single line with four space-separated integers describing the respective values of A, B, C and D.

Constraints
1 \le A, B, C, D \le 3000

Output Format
Print the number of beautiful quadruples.

Sample Input

Sample Output

Explanation
There are 11 beautiful quadruples for this input:
(1,1,1,2)
(1,1,1,3)
(1,1,1,4)
(1,1,2,3)
(1,1,2,4)
(1,1,3,4)
(1,2,2,2)
(1,2,2,3)
(1,2,2,4)
(1,2,3,3)
(1,2,3,4)

Thus, we print 11 as our output.
Note that (1, 1, 1, 2) is same as (1, 1, 2, 1) .

Solution
Since the order of the integers in a quadruple does not matter we can sort our input values such that A \le B \le C \le D:

We will then solve it for the first half of the quadruple (a,b,c,d). For that we define the following arrays:
total = new int[3001]: total[B] holds the number of pairs \{ a,b\} such that a \le b with 1 \le a \le A and 1 \le b \le B:

count = new int[3000 + 1][4096 + 1]: count[B][x] holds the number of pairs \{a,b\} such that a \le b and a \oplus b = x with 1 \le a \le A and 1 \le b \le B:

Note here that the maximum XOR value achievable is 4096 since 1 \le A, B, C, D \le 3000 (12 bits).

We can now go ahead and use total and count to find our solution. Remember we sorted our A \le B \le C \le D so that we count our quadruples (a,b,c,d) such that a \le b \le c \le d.

For the second half of (a,b,c,d) we have \{c,d\} with 1 \le c \le C and 1 \le d \le D. Let c \oplus d = y. We know that a \oplus b \oplus c \oplus d = 0 if a \oplus b = y. We know that we have a total of total[c] pairs \{a,b\} with a \le b and 1 \le b \le c. We want to exclude the pairs that have a \oplus b = y. There are count[c][y] pairs \{a,b\} that combined with \{c,d\} result to 0. So from total[c] we have to exclude count[c][y] and do this for all possible c and d:
\sum_{c=1}^{C}\sum_{d=1}^{D}total[c]-count[c][c \oplus d]

The full code is listed below.

Full code

 

lucas