0 like 0 dislike
Let's define a function , fun(A,B) = A + B - 2(A&B) , where '&' is a bitwise operation of AND.

Given an array of size 'N' , find the sum over all the triplets triplets fun(a[i],fun(a[j],a[k])).

1<=N<=100000

1<=a[i]<=1000000000

retagged

0 like 0 dislike

Step - 1 : There is this popular equation in bit manipulation theory :

A + B = A xor B + 2*(A&B)

How this works ? Link : https://lnkd.in/e5iaMt2P

Re-arranging the terms , you get A xor B = A + B - 2*(A&B) = fun(A,B)

Voila! This means , our question is reduced to find sum of all xor triplets in the array. Answer = XoR(a[i],a[j],a[k]) over all possible triplets in the array.

Step - 2 : In order to solve this complex problem , we should first know solution to a simpler problem , which is : find sum of all xor pairs in the array. Answer = XoR(a[i],a[j]) over all possible pairs in the array.

This is a popular concept can be found here :- https://lnkd.in/eDbg5CVu

From this , we derive the way for triplets.

Hence , we solved a problem on combinatorics and bit manipulation by smart simple observations :)

Time Complexity : O(N*(log(max(A[i])))

```

C++ code:->
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

ll fac[1000000+7];

ll power(ll x, ll y, ll p)

{

ll res = 1;

x = x % p;

while (y > 0)

{

if (y & 1){

res = (res * x) % p;

}

y = y >> 1;

x = (x * x) % p;

}

return res;

}

ll modInverse(ll n, ll p)

{

return power(n, p - 2, p);

}

ll nCrModPFermat(ll n,ll r, ll p)

{

if (r == 0)

{

return 1;

}

if (n < r){

return 0;

}

return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;

}

ll Sumofxor(ll a[], ll n)

{

ll mod = 1000000000+7;

for (ll k = 0; k < 32; k++)

{

ll x = 0, y = 0;

for (ll i = 0; i < n; i++)

{

if (a[i] & (1 << k))

{

x++;

}else

{

y++;

}

}

answer += ((1 << k) % mod *

(nCrModPFermat(x, 3, mod)+ x * nCrModPFermat(y, 2, mod))% mod) % mod;

}

}

int main() {

ios_base::sync_with_stdio(false) ;

cin.tie(NULL);

cout.tie(NULL);

ll p = 1e9 + 7 ;

fac[0] = 1;

for (ll i = 1; i <= 100000+55; i++){

fac[i] = (fac[i-1]*i) % p;

}

ll n ;

cin>>n;ll a[n];

ll i = 0 ;

while(i<=n-1)

{

cin>>a[i];

i++;

}

cout<<Sumofxor(a,n);

return 0 ;

}```
by Expert (112,910 points)
selected