A Bit Easy solution codechef

A Bit Easy solution codechef

 

Chef was impressed by an array AA of NN non-negative integers. But, he was asked to solve the following problem in order to get this array.

Given a non-negative integer kk, find the number of pairs (i,j)(i,j) (1i<jN)(1≤i<j≤N) such that the following condition holds true:
(Ai(Ai || Aj)Aj) ++ (AiAj)(Ai⊕Aj) ++ (Ai(Ai && Aj)Aj) =k=k +Aj+Aj, where

You, being Chef’s friend, help him get this array by solving the above problem.

Input Format

A Bit Easy solution codechef

  • The first line contains an integer TT, the number of test cases.
  • The first line of each test case contains two space-separated integers NN and kk, the number of integers in the array AA and the non-negative integer kk respectively.
  • The next line contains NN space-separated non-negative integers A1,A2,,ANA1,A2,…,AN, the elements of the array AA.

Output Format

For each test case, print a single line containing the number of pairs satisfying the mentioned condition.

Constraints

  • 1T2001≤T≤200
  • 1N1051≤N≤105
  • 0k10180≤k≤1018
  • 0Ai10180≤Ai≤1018
  • Sum of NN over all test cases does not exceed 31053⋅105.

Sample Input 1  

A Bit Easy solution codechef

2
1 8
7
3 8
1 6 4

Sample Output 1

0
2

Explanation

Test case 11: The input array contains only a single integer. Thus, no pairs are possible.

Test case 22: There are two pairs satisfying the condition –

 

  • (i,j)=(1,2)(i,j)=(1,2)A1=1A1=1 and A2=6A2=6. Thus, (1|6)+(16)+(1(1|6)+(1⊕6)+(1 && 6)=7+7+0=146)=7+7+0=14. Also, k+A2=8+6=14k+A2=8+6=14.
  • (i,j)=(2,3)(i,j)=(2,3)A2=6A2=6 and A3=4A3=4. Thus, (6|4)+(64)+(6(6|4)+(6⊕4)+(6 && 4)=6+2+4=124)=6+2+4=12. Also, k+A3=8+4=12k+A3=8+4=12.

     

    A Bit Easy solution codechef

    Solution

    Click here

Leave a Comment