Count triplets with the following restriction

Question

Given A, B, C, and D, we need to find the number of triplets (x, y, z) such that ((x xor y) or z) ≤ D under the constraint x≤A, y≤B, z≤C, where each of A, B, C and D can reach 10 ^ 18.

Since the answer can be very large, we need to output the number of triplets modulo 10 ^ 9 + 7.

The main and inefficient approach:

i=0,j=0,k=0,ans=0

FOR (i<=A)

   FOR(j<=B)

     FOR(k<=C)

        if(((i^j)|k)<=D) ans=ans+1

print ans%1000000007

Obviously, its very ineffective could be a little better?

Answer 1

We can solve the problem by breaking the numbers (x, y, z) into bits. Like x, y, z <= 10 18, so the number is less than 50 bits .

So, from the first bit to the 50th bit, we need to know four things

• If xless than A
• y , B
• z C
• (x ^ y) | z D

, :

long totalNumber(int bit, boolean lessThanA, boolean lessThanB, boolean lessThanC, boolean lessThanD)

0 1 x, y, z

    long result = 0;
    for(int x = 0; x < 2; x++){
       for(int y = 0; y < 2; y++){
          for(int z = 0; z < 2; z++){
             //update lessThanA, lessThanB, lessThanC, lessThanD. This step is omitted.
             result += totalNumber(bit + 1, lessThanA, lessThanB, lessThanC, lessThanD);
             result %= MOD; //remember to take modulo of the result. 
          }
       } 
    }

1, 50th

if(bit == 50)
   return 1;

, ,

dp[bit][lessThanA][lessThanB][lessThanC][lessThanD]

O(bit * lessThanA * lessThanB *lessThanC * lessThanD), ~ O(50*2^4) = O(800)

: . B round 1B Google Code Jam 2014 .

Answer 2

, . r. ^ j = r , j? : .

0 ≤ ≤ A, ^ j = r. : 0 ≤ ≤ A 0 ≤ j ≤ B. . , .

O (n ^ 3) O (n ^ 2), A, B, C, D ≤ 10 ^ 6, .

Answer 3

, :

x = ???????????????????

y = ???????????????????

z = ???????????????????

D = 1100000011001101010 (binary)

, (, ), f(D), , , D. , D:

(1) Any number without the highest bit D has set: 
    _xxxxxxxxxxxxxxxxxx

(2) Any number with the highest bit D has set, but without the next highest bit D has set:
    10xxxxxxxxxxxxxxxxx

(3) Any number with the highest bit and the next highest bit D has set, but without the 
    third highest bit D has set:    
    110000000xxxxxxxxxx

 And so on...

Each of (1), (2), (3), etc. It is an excellent opportunity for combinatorial calculation of possible triplets, where methods for obtaining already filled bits can be calculated using our previous method f, or xcan be easily calculated as all possible combinations.