Блог пользователя garg_saurav

Автор garg_saurav, история, 3 года назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится