Problem:


Score : 400 points

Problem Statement

We have N integers. The i-th integer is A_i.

Find \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

2 \leq N \leq 3 \times 10^5

0 \leq A_i < 2^{60}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the value \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

Sample Input 1

3
1 2 3

Sample Output 1

6

We have (1\mbox{ XOR } 2)+(1\mbox{ XOR } 3)+(2\mbox{ XOR } 3)=3+2+1=6.

Sample Input 2

10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

237

Sample Input 3

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

Sample Output 3

103715602

Print the sum modulo (10^9+7).



Sample input:
3
1 2 3


Sample output:
6

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC147 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
a = LI()
b = [0]*60
for i in range(n):
    for j in range(a[i].bit_length()):
        if (a[i] >> j) & 1:
            b[j] += 1
ans = 0
tmp = 0
for i in range(60):
    r = n-b[i]
    ans += b[i]*r*(2**tmp)
    ans %= mod
    tmp += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 

def main():
    n=int(input())
    a=list(map(int, input().split()))
    pre2 = (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 73741817, 147483634, 294967268, 589934536, 179869065, 359738130, 719476260, 438952513, 877905026, 755810045, 511620083, 23240159, 46480318, 92960636, 185921272, 371842544, 743685088, 487370169, 974740338, 949480669, 898961331, 797922655, 595845303, 191690599, 383381198, 766762396, 533524785, 67049563, 134099126, 268198252, 536396504)
    pre1 = (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976)
    x=[0 for _ in range(61)]
    ans=0
    for i in range(n):
        z=[0 for _ in range(61)]
        y = a[i]
        for k in range(60,-1,-1):
            if y>=pre1[k]:
                y-=pre1[k]
                z[k]+=1
        for j in range(61):
            num = i-x[j]
            if i!=0:
                if z[j]==0:
                    ans=(ans+x[j]*pre2[j])%mod
                else:
                    ans=(ans+num*pre2[j])%mod
            x[j]+=z[j]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0] * 60
    for i in A:
        for j in range(60):
            if i & (1 << j):
                B[j] += 1
    r = 0
    for ii, i in enumerate(A[:-1]):
        for j in range(60):
            if i & (1 << j):
                B[j] -= 1
                r = (r + (1 << j) * (N - ii - 1 - B[j])) % MOD
            else:
                r = (r + (1 << j) * B[j]) % MOD
    print(r)

main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split())) 

def sumXOR( arr,  n): 
    sum = 0
    for i in range(0, 64): 
  
        #  Count of zeros and ones 
        zc = 0
        oc = 0
           
        # Individual sum at each bit position 
        idsum = 0
        for j in range(0, n): 
            if (arr[j] % 2 == 0): 
                zc = (zc + 1)
                  
            else: 
                oc = (oc + 1)
            arr[j] = (arr[j] >> 1) 
          
           
        # calculating individual bit sum  
        idsum = (oc * zc * ((1 << i))) % 1000000007
   
        # final sum     
        sum = (sum + idsum)
      
    return sum
  
  
  
  
print(sumXOR(A, N)  % 1000000007)

Submission status: Accepted

Solution code:
MOD=10**9+7

N=int(input())
alist=list(map(int,input().split()))

#print(alist)
blist=[0]*64
for a in alist:
  bblist=[]
  acopy=a
  while(acopy>0):
    bblist.append(acopy%2)
    acopy//=2
    
  #print(bblist)
  for b in range(len(bblist)):
    blist[-1-b]+=bblist[b]
      
blist.reverse()
#print(blist)
answer=0
pow=1
for i in range(64):
  answer+=blist[i]*(N-blist[i])*pow
  answer%=MOD
  pow*=2
  
print(answer)

Submission status: Accepted

Solution code:
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

count_list = [0 for i in range(61)]
def counts(count_list, a):
    for i in range(61):
        if a <= 0:
            break
        count_list[i] += a % 2
        a = a // 2
    return count_list

A.reverse()
ans = 0
ans_list = [0 for i in range(61)]
for i in range(N-1):
    count_list = counts(count_list, A[i])
    hikaku = counts([0 for i in range(61)], A[i + 1])
    for j in range(61):
        if hikaku[j] == 1:
            ans_list[j] += i+1 - count_list[j]
        else:
            ans_list[j] += count_list[j]

for i in range(61):
    ans += ans_list[i] * (2 ** i % mod)
    ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
L = len(format(max(a), 'b'))
x = [0 for i in range(L)]
ans = 0
MOD = 10 ** 9 + 7
for i in a:
    i_str = list(format(i, '0' + str(L) + 'b'))[::-1]
    for j, s in enumerate(i_str):
        if s == '1':
            x[j] += 1
b = 1
for i, xi in enumerate(x):
    ans += xi * (n - xi) * b % MOD
    ans %= MOD
    b *= 2
    b %= MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

counts = [sum((a >> i) & 1 for a in A) for i in range(60)]

power2 = [1]
for _ in range(59):
    power2.append((power2[-1] * 2) % MOD)

ans = sum(c * (N - c) * power2[i] for i, c in enumerate(counts))

print(ans % MOD)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
one = [0 for _ in range(60)]

for a in A:
    for i in range(60):
        if a & 1 << i:
            one[i] += 1
ans = 0
for a in A:
    n -= 1
    if n == 0:
        break
    for i in range(60):
        if a & 1 << i:
            one[i] -= 1

    for i in range(60):
        if a & 1 << i:
            ans += (1 << i) * (n - one[i])
        else:
            ans += (1 << i) * one[i]

print(ans % 1000000007)

Submission status: Accepted

Solution code:
MOD=10**9+7

N=int(input())
alist=list(map(int,input().split()))

#print(alist)
blist=[0]*64
for a in alist:
  bblist=[]
  acopy=a
  while(acopy>0):
    bblist.append(acopy%2)
    acopy//=2
    
  #print(bblist)
  for b in range(len(bblist)):
    blist[-1-b]+=bblist[b]
      
blist.reverse()
#print(blist)
answer=0
for i in range(64):
  answer+=blist[i]*(N-blist[i])*(2**i)
  
print(answer%MOD)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False


def ans():
    n = onem()

    a = l()

    dp = [[0]*60 for j in range(n+1)]

    co = 0

    for i in range(1,n+1):
        kkk = a[i-1]
        for j in range(60):
            if j != 0:
                kkk = kkk // 2
            if kkk & 1:
                dp[i][j] = dp[i-1][j] + 1
            else:
                dp[i][j] = dp[i-1][j]

    two = [0 for i in range(61)]
    two[0] = 1
    for i in range(1,61):
        two[i] = (two[i-1]*2) % mod
        

    for i in range(1,n):
        for j in range(60):
            if dp[i][j] == dp[i-1][j]:
                ans = two[j]*(dp[-1][j]-dp[i][j])
                ans %= mod
                co += ans
                co %= mod
            else:
                ans = two[j]*(n-(i-1) - (dp[-1][j] - dp[i-1][j]))
                ans %= mod
                co += ans
                co %= mod

    print(co)

if __name__ == '__main__':
    ans()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ans=0
    bit=[0]*60
    seki=10**9+7
    a=list(map(int,input().split()))
    for i in range(n):
        for j in range(60):
            if a[i]%2==1:
                bit[j]+=1
            a[i]=a[i]>>1
    for i in range(60):
        ans+=(bit[i]*(n-bit[i]))*(2**i)
    print(ans%seki)
main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

B = [0]*60

for a in A:
    for i in range(60):
        B[i] += (a >> i) % 2

ans = 0
for i in range(60):
    ans += (B[i]*(N-B[i])) * (1 << i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(len(str(bin(max(a)))) - 2)]
a = [bin(i)[2:] for i in a]

for i in a:
    for j, k in enumerate(i[::-1]):
        if k == "1":
            l[j] += 1
ans = 0
for i, j in enumerate(l):
    ans = (ans + (j * (n - j)) * (2 ** i)) % mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
T=[0]*61
mod=10**9+7

for i in range(N):
  for j in range(61):
    if ((A[i]>>j) & 1):
      #print(i,j)
      T[j]+=1
#print(T)

ans=0
for i in range(61):
  ans+=2**i*(N-T[i])*T[i]
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ans = 0
for j in range(60):
    c0 = 0
    c1 = 0
    for i in range(n):
        if a[i] % 2**(j+1) == 0:
            c0 += 1
        else:
            a[i] -= 2**j
            c1 += 1
    ans += 2 ** j * c0 * c1
    ans %= 10**9 + 7

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
alist = list(map(int,input().split()))
binlist = [0]*60
mod_number = 10**9+7

def dec2bin(target):
    amari = []
    while target != 0:
        amari.append(target%2)
        target = target//2
    amari.reverse()
    return amari

for a in alist:
    a_bin = dec2bin(int(a))
    for i in range(len(a_bin)):
        if int(a_bin[-(i+1)])==1:
            binlist[-(i+1)] += 1
            #print(a,a_bin,i,binlist)
ans = 0
for i in range(60):
    ans = (ans + binlist[-(i+1)]*(n-binlist[-(i+1)])*pow(2,i))%mod_number
    
print(ans)

Submission status: Accepted

Solution code:
import sys

inf = float("inf")

def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

mod = 10**9+7

def sumXOR(arr, n):
    sum = 0
    for i in range(0, 64):

        #  Count of zeros and ones
        zc = 0
        oc = 0

        # Individual sum at each bit position
        idsum = 0
        for j in range(0, n):
            if (arr[j] % 2 == 0):
                zc = zc + 1

            else:
                oc = oc + 1
            arr[j] = arr[j]//2

            # calculating individual bit sum
        idsum = oc * zc * (1 << i)

        # final sum
        sum = sum + idsum
        sum%=mod

    return sum

n = int(input())
Arr = get_array()
ans = sumXOR(Arr,n)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
MOD=10**9+7
L=60
ls=[int(s) for s in input().split()]
bi_ls=[0 for _ in range(L)]
for i in range(N):
  for j in range(L):
    if (2**j)&ls[i]>0:
      bi_ls[j]+=1    
ans=0
base=1
for j in range(L):
  ans=(ans+bi_ls[j]*(N-bi_ls[j])*base)%MOD
  base*=2%MOD
print(ans)

Submission status: Accepted

Solution code:
def bi(x):
    x = int(x)
    i = 0
    o = [0]*61
    while x > 0:
        o[i] = x % 2
        x //= 2
        i += 1
    return o

N = int(input())
A = list(map(bi,input().split()))

# print(*A,sep='\n')
a = 0
ruijoo = 1
bbb = 0
B = [0]*N
h = 0
while h < 61:
    i = 0
    isOne = 0
    while i < N:
        aaaa = A[i][h]
        isOne += aaaa
        B[i] = aaaa
        i += 1
    isZero = N - isOne
    C = [isOne,isZero]
    bbbb = 0
    i = 0
    while i < N:
        bbbb += C[B[i]]
        i += 1
    bbbb *= ruijoo
    bbb += bbbb
    bbb %= 1000000007
    ruijoo *= 2
    ruijoo %= 1000000007
    h += 1

bbb *= 500000004
bbb %= 1000000007
print(bbb)

Submission status: Accepted

Solution code:
N=int(input()) 
import math
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7

c = [0]*k

for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    if bit[j] == '1':
      c[-1-j] +=1
      
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
m = 65
a = list(map(int, input().split()))
b = [[0] * n for i in range(m)]

for i in range(n):
    for j in range(m):
        b[j][i] = (a[i] >> j) & 1

ans = 0
d = 1
for i in range(m):
    s = sum(b[i])
    ans += s * (n-s) * d
    ans %= MOD
    d *= 2

print(ans % MOD)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))
buf = [0 for i in range(61)]

count = [[0,0] for i in range(61)]

for a in arr:
    txt = str(bin(a))[2:].zfill(61)

    for i in range(len(txt)):
        if txt[i] == "0":
            buf[i] += count[i][1]
            count[i][0] += 1
        else:
            buf[i] += count[i][0]
            count[i][1] += 1

m = 10**9 +7

buf.reverse()
ans = 0

for i in range(len(buf)):
    num = buf[i]
    if i == 0:
        base = 1
    else:
        base = base*2
    b = base%m
    b = (b*num)%m

    ans += b
    ans = ans%m

# print(buf)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7
for i in range(n):
  b = format(A[i],'b').zfill(61)
  A[i] = b


bit = [0]*61
for i in range(n):
  for j in range(61):
    if A[i][j] =='1':
      bit[j] += 1

ans = 0
for k in range(61):
  multi = (bit[k]*(n-bit[k]))%MOD
  if k > 30:
    ans += (((2**(60-k))%MOD) * multi)%MOD
  else:
    ooo = ((2**(30-k))%MOD * (2**20)%MOD * (2**10)%MOD) %MOD
    ans += (ooo * multi)%MOD
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
keta=[0]*60
lis=[]
for i in range(n):
    tmp=[]
    for j in range(60):
        if (a[i]>>j)&1==1:
            keta[j]+=1
            tmp.append(j)
    lis.append(tmp)

s=sum(a)
ans=0
for i in range(n):
    s-=a[i]
    j=0

    for j in range(len(lis[i])):
        tmp2=lis[i][j]
        keta[tmp2]-=1
        ans+=(2**tmp2)*((n-(i+1)-keta[tmp2]*2))
    ans+=s
    ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    xs = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    ps = [
        sum((x & (1<<i)) >> i for x in xs)
        for i in range(60)
    ]
    ms = [n - p for p in ps]

    ans = 0

    for i in range(60):
        s = 0
        for x in xs:
            b = (x & (1<<i)) >> i
            if b == 1:
                ps[i] -= 1
                s += ms[i]
            else:
                ms[i] -= 1
                s += ps[i]
        ans += s * (2**i % mod)
        ans = ans % mod

    print(ans)

main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
mod = 10**9 + 7
A = np.array(input().split(), dtype=np.int64)
# print(A)

ans = 0
for i in range(60):
    b = np.count_nonzero(A >> i & 1)
    ans += 2**i*(b*(N-b))
    ans %= mod
    # c = np.count_nonzero(A >> i)
    # print(c)
print(ans)

Submission status: Accepted

Solution code:
bits = [0]*60

n = int(input())
arr = list(map(int, input().split()))

mod = pow(10, 9) + 7
res = 0
eles = 0
mx = 0
for i in range(n-1, -1, -1):
	ele = arr[i]
	mx = max(mx, ele.bit_length())
	add = 0
	for j in range(mx):
		if ele&(1<<j):
			add += (eles - bits[j])*pow(2, j)
			bits[j] += 1
		else:
			add += (bits[j])*pow(2, j)
	res += add
	res %= mod
	eles += 1
print(res)

Submission status: Accepted

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    mod = 10 ** 9 + 7
    n = int(input())
    a = tuple(map(int, input().split()))

    b = [0] * 60

    for j in range(60):
        for x in a:
            if (x >> j) & 1:
                b[j] += 1

    ret = 0
    for j in range(60):
        ret = (ret + b[j] * (n - b[j]) * (1 << j)) % mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

pow2 = [1]
mod = 1000000007

for i in range(1,61):
    pow2.append(pow2[-1]*2 % mod)

seq = list(map(lambda x: bin(int(x))[2:], input().split()))

onec = [0 for i in range(61)]

for i in range(n):
    ln = len(seq[i])
    for j in range(ln):
        if seq[i][ln-1-j] == '1':
            onec[j] += 1

sm = 0

for i in range(61):
    sm += onec[i]*(n-onec[i]) * pow2[i] % mod
    
print(sm % mod)

Submission status: Accepted

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _i(): return int(sys.stdin.readline().strip())
def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]
mod = 10**9 + 7

n= _i()
a= _ia()
z = [ 0 ] * 60
o = [ 0 ] * 60

for ai in a:
    b = bin(ai)[2:]
    for i,c in enumerate(reversed(b)):
        if c=="0": z[i]+=1
        else: o[i]+=1
    #
    for i in range(len(b),60): z[i]+=1
#
ans = 0
base = 1
for zz,oo in zip(z,o):
    ans = ( ans + ( base * zz*oo ) ) % mod
    base = (base * 2) % mod
#
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
a=[0]*61
mod=10**9+7
for i in l:
    k=i
    j=0
    while k>0:
        a[j]+=k%2
        k=k//2
        j+=1
ans=0
for i in range(61):
    ans+=a[i]*(n-a[i])*pow(2,i,mod)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# problem D
mod=10**9+7

N=int(input())
A=list(map(int,input().split()))

b=[[0 for i in range(N)] for k in range(60)] # i番目の数の2^kの位(0<=k<60)
d0=[0 for k in range(60)]
d1=[0 for k in range(60)]

for i in range(N):
    for k in range(60):
        if A[i]>>k&1:
            d1[k]+=1
        else:
            d0[k]+=1

ans2=0
for k in range(60):
    ans2+=2**k*d0[k]*d1[k]

print(ans2%mod)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

inf = 10 ** 9 + 7

cnt = [0] * 60

for a in A:
    s = bin(a)[2:].zfill(60)
    s = s[::-1]
    for i in range(60):
        if s[i] == '1':
            cnt[i] += 1

ans = 0
for i in range(60):
    ans += (cnt[i] * (N - cnt[i])) * (2 ** i)
    ans %= inf

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def solve(n, a):
    m = 61
    b = [('0'*m + bin(a[i])[2:])[-1:-m:-1] for i in range(n)]
    cnt_bit = [0] * m
    for i in range(n):
        for j, c in enumerate(b[i]):
            if c == '1':
                cnt_bit[j] += 1
    total = 0
    k = 1
    for i in range(m - 1):
        t = 0
        for j in range(n):
            if b[j][i] == '0':
                t += k * cnt_bit[i]
            if b[j][i] == '1':
                t += k * (n - cnt_bit[i])
        t //= 2
        total += t
        k = (k*2 % MOD)
    return total % MOD


def bf(n, a):
    total = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            total += (a[i] ^ a[j])
    return total % MOD


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    print(solve(n, a))
    # print(bf(n, a))

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
ma = max(a)
maketa = len(bin(ma))-2
#print(maketa)
res = 0
dic = {}
for i in range(maketa):
    dic[i] = 0
for i in range(0,maketa):
    num = 0
    for j in range(N):
        #print(a[j] & (2**i))
        dic[i] += int((a[j] & (2**i))>>i)
        #count += 1
for i in range(maketa):
    num = dic[i]
    res += num*(N-num)*(2**(i))
print(res%(10**9+7))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
N = 60


d = np.array(list(map(int, input().split())))
nums = (((d[:, None] & (1 << np.arange(N)))) > 0).astype(int)
res = 0
MOD = int(1e9+7)
k = np.full(N, (n*(n-1)/2) % MOD)
n1 = nums.sum(0) % MOD
n0 = (n-nums.sum(0)) % MOD
k -= (n1*(n1-1)//2) % MOD
k -= (n0*(n0-1)//2) % MOD
k %= MOD

res = 0
for i, kk in enumerate(k):
    res += ((1 << i)*kk) % MOD
    res %= MOD


print(int(res))

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9

    bit = dict()
    pow_list = dict()
    for j in range(60): 
        bit[j] = 0
        pow_list[j] = pow(2, j, mod)

    first = A[0]
    for j in range(60):
        bit[j] = first % 2
        first //= 2
    
    ans = 0
    for i in range(1, N):
        num = A[i]
        for j in range(60):
            if num % 2 == 1:
                ans += (i - bit[j]) * pow_list[j]
                ans %= mod
            else:
                ans += bit[j] * pow_list[j]
                ans %= mod
            bit[j] += (num % 2)
            num //=2
            
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
num = [ int(v) for v in input().split() ]
bits = [ 0 for i in range(100) ]

for i in num:
    j = 0
    while i > 0:
        if i % 2 == 1:
            bits[j] += 1
        i //= 2
        j += 1


binmax = 0
for i in range(100):
    if bits[i] > 0:
        binmax = i
binmax += 2


pow_2_list = []
q = 1
for i in range(100):
    pow_2_list.append(q)
    q *= 2
    q %= mod


ans = 0
for i, v in enumerate(bits[:binmax]):
    ans += v * (n-v)  * pow_2_list[i] 
print(ans % mod)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
MAXBIT=60
MOD=10**9+7
bits=[[0 for _ in range(MAXBIT)] for _ in range(N)]
for i in range(N):
    tmp=A[i]
    j=0
    while tmp>0:
        bits[i][j]=tmp%2
        tmp=tmp//2
        j+=1
ans=0
for j in range(MAXBIT):
    cnt0=0
    for i in range(N):
        if bits[i][j]==0:
            cnt0+=1
    ans=(((cnt0*(N-cnt0))%MOD*(2**j))%MOD+ans)%MOD
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
A.sort()

mod = 10**9 + 7
def mulmod(s):
    r = 1
    for i in s:
        r = r*i%mod
    return r


ans = 0
k=1
while A[-1]>0:
    t = 0
    for i in range(N):
        t+=A[i]%2
        A[i]//=2
    r = [N-t, t, pow(2, k-1, mod)]
    ans = (ans + mulmod(r))%mod
    k +=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

MOD = 10 ** 9 + 7

ans = 0
for i in range(60):
    n = sum([(a >> i) & 1 for a in A])
    ans = (ans + n * (N - n) * (2 ** i)) % MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

ans = 0
bitcnt = [0] * 60
for Ai in A:
    Ai_tmp = Ai
    for j in range(60):
        bitcnt[j] += (Ai_tmp % 2)
        Ai_tmp >>= 1

# table_tmp = 1
# table = []
# for i in range(64):
#     table.append(table_tmp)
#     table_tmp = (table_tmp << 1) % (10 ** 9 + 7)

ans = 0
for i in range(60):
    ans_cnt = (bitcnt[i] * (N - bitcnt[i])) % (10 ** 9 + 7)
    ans_lvl = (1 << i) % (10 ** 9 + 7)
    ans_tmp = (ans_cnt * ans_lvl) % (10 ** 9 + 7)
    ans = (ans + ans_tmp) % (10 ** 9 + 7)

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
import numpy as np

def main():
	n=int(input())
	A=np.array(read().split(), np.int64)
	n=len(A)
	ans=0
	
	for i in range(62):
		B=A%2
		k=np.count_nonzero(B)
		A=A//2
		ans+=(2**i)*(k*(n-k))
		ans%=mod
	print(ans)
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

ans = 0
for i in range(61):
    n1 = sum([1 for a in A if (a>>i)&1])
    ans += (1<<i)*n1*(N-n1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=[0 for i in range(60)]

for i in range(N):
    n=A[i]
    #print(n)
    for j in range(60):
        L[j]+=n//(2**(59-j))
        n%=(2**(59-j))
        #print(n)
#print(L)
ans=0
for i in range(60):
    ans+=(N-L[i])*(L[i])*2**(59-i)
    ans%=(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10**9+7
a = [int(c) for c in input().split()]
M = max(a).bit_length()
ls = [0]*M
for i in range(N):
  m = a[i]
  for j in range(M):
    if m%2==1:
      ls[j] += 1
    m >>= 1

ans = 0
x = 1
for i in range(M):
  ans += x*(ls[i]*(N-ls[i]))
  ans %= MOD
  x *= 2
  x %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A=list(map(int,input().split()))
l=[0]*60
for i in A:
    s=str(bin(i))[2:]
    for j in range(len(s)):
        if s[-j-1]=="1":
            l[j]+=1
a=0
for i in range(60):
    a=(a+2**i*l[i]*(N-l[i]))%(10**9+7)
print(a)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
mod = 10**9 + 7

dp0 = [0]*61
dp1 = [0]*61
for a in As:
    bins = format(a,"061b")[::-1]
    for i,b in enumerate(bins):
        if b == "0":
            dp0[i] += 1
        else:
            dp1[i] += 1
ans = 0
for i,(zero,one) in enumerate(zip(dp0,dp1)):
    ans += (zero*one*2**i)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
*A, = map(int, input().split())
ans = 0
for i in range(60):
    bit_0, bit_1 = 0, 0
    for a in A:
        if (a >> i) & 1: 
            bit_1 += 1
        else:
            bit_0 += 1
    ans += bit_1 * bit_0 * pow(2, i, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def sumXOR( arr,  n): 
    sum = 0
    for i in range(0, 100): 
        zc = 0
        oc = 0
        idsum = 0
        for j in range(0, n): 
            if (arr[j] % 2 == 0): 
                zc = zc + 1
                  
            else: 
                oc = oc + 1
            arr[j] = arr[j]//2
        idsum = oc * zc * (1 << i)    
        sum = sum + idsum;  
        sum%=10**9+7
    return sum

n=int(input())
arr=list(map(int,input().split()))
sum = sumXOR(arr, n); 
sum%=10**9+7
print(sum)

Submission status: Accepted

Solution code:
n = int(input())

nums = []

inputs = input()
for i in inputs.split(" "):
    nums.append(int(i))

count = 0
m = 10 **9 + 7
for i in range(0, 64):
    one = 0
    zero = 0

    for j in range(0, n):
        if (nums[j] % 2 == 1):
            one += 1
        else:
            zero += 1

        nums[j] //= 2
    
    count += (zero * one * (1 << i)) % m

print(count % m)

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))

P = 10**9 + 7

ans = 0

for i in range(60):
    c = 0
    for a in A:
        c += ((a >> i) & 1)
    
    ad = c * (N - c) % P
    ans += ad * (1 << i)
    ans %= P

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
P=10**9+7
ans=0
BIN=[0]*N
for h in range(N):
    BIN[h]=bin(A[h])[2:].zfill(60)

for i in range(60):
    inc=0
    one=0
    zero=0
    for j in range(N):
        if BIN[j][59-i]=="0":
            zero+=1
        else:
            one+=1
    ans+=zero*one*2**i
print(ans%P)

Submission status: Accepted

Solution code:
n = int(input())
str_a = ''.join(['{:060b}'.format(a) for a in map(int, input().split())])
mod = 10**9 + 7

rest = 0
for d in range(60):
  ones = str_a[59-d::60].count('1')
  rest = (rest + 2**d * ones * (n - ones)) % mod
    
print(rest)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
cnt=[]
q=set()
for i in range(n):
	q.add(i)
for i in range(60):
	p=0
	l=[]
	for j in q:
		if a[j]%2==1:
			p+=1
		a[j]//=2
		if a[j]==0:
			l.append(j)
	for j in range(len(l)):
		q.remove(l[j])
	cnt.append(p)
ans=0
for i in range(60):
	ans+=(n-cnt[i])*cnt[i]*(2**i)
	ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    z=len(bin(max(A)))-2
    l=[0]*z
    for x in A:
        for i in range(z):
            if (x >> i) & 0b1 == 1:
                l[i]+=1
    ans=0
    for i in range(z):
        ans+=l[i]*(N-l[i])*(2**i)
        ans%=MOD
    print(ans)
    
                    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9+7

    A_bin_cnt = [0] * 60
    for i in range(N):
        a = A[i]
        for j in range(60):
            if a >> j & 1:
                A_bin_cnt[j] += 1

    ans = 0
    for i in range(60):
        ans = (ans + (pow(2, i, mod) * (A_bin_cnt[i] * (N - A_bin_cnt[i])))%mod) % mod
    print(ans)


if __name__ == '__main__':
    main()