In this HackerEarth Xor sum problem solution, You are given an array A[] of size N. Now you are given Q queries to be performed over this array. In each query, you are given space-separated integers L and R. For each query, you need to find the summation of the xor-sum of all triplets (i,j,k) of the sub-array L...R, where L <= I < j < k <= R.

In short, you need to find sigma(A[i] xor A[j] xor A[k]), over all triplets (i,j,k), such that L <= i < j < k <= R. Print the answer for each query , Modulo 10^9 + 7.


HackerEarth Xor sum problem solution


HackerEarth Xor sum problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
ll n,q,a[100005],seg[400005][45],l,r,po[100005];
/*void build(ll node,ll st,ll en)
{
if(st==en)
{
for(ll i=0;i<=42;i++)
{
if(a[st]&(1<<i))
seg[node][i]=1;
}
}
else
{
ll mid=(st+en)/2;
build(2*node,st,mid);
build(2*node+1,mid+1,en);
for(ll i=0;i<=42;i++)
{
seg[node][i]=seg[2*node]+seg[2*node+1];
}
}
}
ll qry(ll node,ll st,ll en,ll l,ll r,ll idx)
{
if(st>en||st>r||en<l||l>r)
return 0;
else if(st>=l&&en<=r)
return seg[node][idx];
else
{
ll mid=(st+en)/2;
return qry(2*node,st,mid,l,r,idx)+qry(2*node+1,mid+1,en,l,r,idx);
}
}*/
void create()
{
ll i,j;
for(i=0;i<=42;i++)
{
for(j=1;j<=n;j++)
{
seg[j][i]=seg[j-1][i];
if(a[j]&(1LL<<i))
seg[j][i]++;
}
}
}
int main()
{
//ios::sync_with_stdio(0);
//cin.tie(0);
freopen("in05.txt","r",stdin);
freopen("out05.txt","w",stdout);
ll i,j,k;
cin>>n;
po[0]=1;
for(i=1;i<=100002;i++)
{
po[i]=2*po[i-1];
po[i]%=MOD;
}
for(i=1;i<=n;i++)
{
cin>>a[i];
}
//build(1,1,n);
create();
cin>>q>>j;
while(q--)
{
cin>>l>>r;
ll cnt1,cnt0,ans=0,ans1=0;
for(i=0;i<=42;i++)
{
cnt1=seg[r][i]-seg[l-1][i];
cnt0=r-l+1-cnt1;
ans=cnt1*(cnt0*(cnt0-1))/2;
ans+=(cnt1*(cnt1-1)*(cnt1-2))/6;
ans%=MOD;
ans=ans*po[i];
ans%=MOD;
ans1+=ans;
ans1%=MOD;
}
cout<<ans1<<"\n";
}
return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

typedef complex<double> base;
typedef long double ld;
typedef long long ll;

#define pb push_back

const int maxn=(int)(2e5+5),LN=41;
const ll mod=(ll)(1e9+7);
ld pi=2.0*acos(0.0);
ll a[maxn];
int pre[LN][maxn];

int mul(ll a,ll b)
{
a%=mod;b%=mod;

ll ret=(a*b);

if(ret>=mod)
{
ret%=mod;
}

return (int)ret;
}

int add(ll a,ll b)
{
a%=mod;b%=mod;

ll ret=a+b;

if(ret>=mod)
{
ret%=mod;
}

return (int)ret;
}

int sub(ll a,ll b)
{
a%=mod;b%=mod;

ll ret=a-b;

if(ret<0)
{
ret+=mod;
}

return (int)ret;
}

static int poww(ll a,ll b)
{
ll x=1,y=a;

while(b>0)
{
if(b%2)
{
x=mul(x,y);
}

y=mul(y,y);b/=2;
}

return (int)(x%mod);
}

const int inv_6=poww(6,mod-2),inv_2=poww(2,mod-2);

int nC3(ll n)
{
if(n<3)
{
return 0;
}

return mul(mul(n,mul(n-1,n-2)),inv_6);
}

int nC2(ll n)
{
if(n<2)
{
return 0;
}

return mul(n,mul(n-1,inv_2));
}

int main()
{
int n;scanf("%d",&n);

assert(n>=1 && n<=(int)(1e5));

for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);

assert(a[i]>=1 && a[i]<=(ll)(1e12));
}

for(int j=0;j<LN;j++)
{
int now=0;ll zz=(1ll<<j);

for(int i=1;i<=n;i++)
{
if((zz&a[i])!=0)
{
now++;
}

pre[j][i]=now;
}
}

int q,two;scanf("%d%d",&q,&two);

assert (q>=1 && q<=(int)(5e5) && two==2);

for(int i=0;i<q;i++)
{
int l,r;scanf("%d%d",&l,&r);

assert (l>=1 && l<=r && r<=n);

int res=0,size=(r-l+1);

for(int j=0;j<LN;j++)
{
int val1=(pre[j][r]-pre[j][l-1]),val0=size-val1;

int zz1=mul(val1,nC2(val0)),zz2=nC3(val1);

res=add(res,mul(1ll<<j,add(zz1,zz2)));
}

printf("%d\n",res);
}

return 0;
}