HackerEarth Xor sum problem solution

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.

#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;
}