garg_saurav's blog

By garg_saurav, history, 4 years ago, In English

Hi everyone, this is a question that was asked in a contest which is over now. Here is the problem statement:

Description
You are given an array A of length N. Consider that the array is one indexed.
You need to find the sum of (A[i] & A[j] & (A[i]+A[j])) for all pairs (i,j) such that 1<=i<j<=N.

Constraints
2<=N<=2x10^5
1<=A[i]<=10^9

Output Format
Since the answer can be large, return it modulo 10^9 + 7

I know the solution in the case when there is only (A[i] & A[j]). In this case, we can count the number of set bits at i'th position (= k). Then it will contribute to kC2 pairs in summation which can directly be written as kC2 x 2^i But I can't extend the argument to the above problem. Any links/references would be highly appreciated.

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it