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:
import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=[0]*60

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(digit):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for i in range(60):
    if cnt[i]==0:continue
    ans=(ans+pow(2,i)*cnt[i]*(n-cnt[i]))%mod
print(ans%mod)

Submission status: Accepted

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

m = 1
ans = 0
for i in range(60):
  s = sum([a&m for a in A])
  s//=m
  ans = (ans + (n-s)*s * m) % MOD
  m <<= 1
  
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
N=int(input())
A=list(map(int,input().split()))
ans=0
 
for i in range(60):
  x=0
  for j in range(N):
    if A[j]>>i&1: x+=1
  ans+=x*(N-x)*(2**i)
print(ans%mod)

Submission status: Accepted

Solution code:
from math import log
def main():
    N = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    
    digits_cnt1 = [0]*60
    for ai in A:
        if ai == 0:
            continue
        #2**60-1みたいな時にfloatの桁落ちが生じるが、元々の桁数を超えるとai>>dがfalseになるのでlist index out of rangeは生じない
        for d in range(int(log(ai)/log(2))+1):
            if ai>>d & 1:
                digits_cnt1[d] += 1
    
    ans = 0
    for i in range(60):
        ans += digits_cnt1[i]*(N-digits_cnt1[i])*pow(2,i,mod)
        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(60):
    mask = 1 << i
    count = sum(1 for j in a if mask & j == 0)
    ans += count * (n-count) * pow(2,i,mod)
print(ans % mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

ans = 0
for i in range(len(format(max(a), 'b'))):
    x = 0
    for j in range(n):
        if a[j] >> i & 1:
            x+=1
    now = x * (n - x) % mod
    for j in range(i):
        now = now * 2 % mod
    ans+=now
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
A = LIST()
 
max_length = len("{:b}".format(max(A)))
 
cnt = [defaultdict(int) for _ in range(max_length)]
 
for i in range(N):
    num = "{:b}".format(A[i]).zfill(max_length)
    for j in range(len(num)):
        # [i桁目][numのj番目の数，(0 or 1)]
        # 0, 1 の数を数える
        cnt[max_length-1-j][num[j]] += 1
 
ans = 0
 
for i in range(max_length):
    # 1を左にiシフト(2 ** i 倍)
    # 桁内で0の個数 * 桁内で1の個数 が，XOR = 1になる数 (0 xor 1 = 1)
    ans = ans + (1 << i) * cnt[i]["0"] * cnt[i]["1"]
ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
mod = 10**9+7
n = int(input())
a = np.fromstring(input(), dtype = np.int64, sep = ' ')

result = 0
for i in range(60):
    count_one = int((a&1).sum())
    result += count_one*(n-count_one)*(2**i)
    a >>= 1
print(result%mod)

Submission status: Accepted

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

mod = 10**9 + 7
res = 0
for i in range(60):
    cnt_one  = sum([a[j]&1 for j in range(n)]) #1とのandをとり，1の個数をカウント
    cnt_zero = n - cnt_one
    res += 2**i * cnt_one * cnt_zero
    a = [a[j]>>1 for j in range(n)] #各要素に対し，右に1ビットシフト
print(res % mod)

Submission status: Accepted

Solution code:
import numpy as np
mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
A=np.array(A)

ans=0
for i in range(60):
    cnt=np.count_nonzero(A&1)
    ans +=2**i*cnt*(n-cnt)
    A >>=1

print(ans%mod)

Submission status: Accepted

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

b = [format(x,'b').zfill(60) for x in a]

ones = [0 for i in range(60)]
for x in b:
    for i in range(60):
        if x[59-i]=='1':
            ones[i] += 1

pow_two = [pow(2,i,mod) for i in range(60)]

ans = 0
for i in range(60):
    ans += ones[i]*(n-ones[i])*pow_two[i]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines  

import numpy as np

N = int(inp())
A = np.array(inp().split(), dtype=np.int64)
MOD = 10**9+7

ans = 0
for k in range(60):
  x0 = 0 # k桁目のbitが0になる総数
  x1 = 0 # k桁目のbitが1になる総数
  B = (A>>k) & 1 # k桁目が1になる要素
  
  # k桁目が 0, 1 のどちらかを数えておく
  x1 = np.count_nonzero(B)
  x0 = N - x1
  # x0 * x1 が 0, 1 の組み合わせ数
  cmb = x0 * x1  
  ans += (cmb * 2**k) % MOD # 10進数に変換
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines  

import numpy as np

N = int(inp())
A = np.array(inp().split(), dtype=np.int64)
MOD = 10**9+7

ans = 0
for k in range(60):
  x0 = 0 # k桁目のbitが0になる総数
  x1 = 0 # k桁目のbitが1になる総数
  B = (A>>k) & 1 # k桁目が1になる要素
  
  # k桁目が 0, 1 のどちらかを数えておく
  x1 = np.count_nonzero(B)
  x0 = N - x1
  # x0 * x1 が 0, 1 の組み合わせ数
  cmb = x0 * x1
  
  for _ in range(k): # 10進数に変換
    cmb *= 2
    cmb %= MOD
  ans += cmb
print(ans%MOD)

Submission status: Accepted

Solution code:
import numpy as np

n=int(input())
A=np.array(list(map(int,input().split())))
mod=10**9+7

ans=0
for i in range(62):
    cnt=np.count_nonzero(A&1) #1とのANDで一番右の桁を抽出
    ans+=cnt*(n-cnt)*(2**i)%mod
    ans%=mod
    A=A>>1 #ビットシフト
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
ar=[0]*60
for i in a:
  for j in range(60):
    if i&(1<<j):
      ar[j]+=1


for i ,j in enumerate(ar):
  b=n-j
  ans+= j*b*2**i

print(ans%mod)

Submission status: Accepted

Solution code:
n=int(input())
a= list(map(int, input().split()))
v=[[0,0] for i in range(60)]

for i in range(n):
    for j in range(60):
        if (a[i]>>j)&1:
            v[j][1]+=1
        else:
            v[j][0]+=1

ans=0

for i in range(60):
    ans+=v[i][0]*v[i][1]*(2**i)
    ans%=10**9+7

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
xorsum = 0
for i in range(60):
  c1 = sum([1 for a in A if (a >> i) & 1]) #
  xorsum += (c1*(N-c1)*(1<<i))
  xorsum = xorsum%mod
print(xorsum%mod)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    MOD = 10 ** 9 + 7
    for d in range(60):
        one = 0
        zero = 0
        for i in range(N):
            if A[i] & (1 << d):
                one += 1
            else:
                zero += 1

        ans += (2 ** d) * (one * zero)
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A = np.array(list(map(int,input().split())))
mod = 10**9+7
m = len(bin(max(A)))-2
ans = 0

for i in range(m):
  one = np.count_nonzero((A >> i)&1)
  zero = n - one
  ans += (pow(2,i,mod)*zero*one)%mod
print(ans%mod)

Submission status: Accepted

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

for i in range(N):
    a = format(A[i],'b')
    a = a[::-1]
    for j in range(len(a)):
        if a[j] == '1':
            c[j] += 1

k = 1
for i in range(len(c)):
    p = c[i]*(N-c[i])
    ans += k*(p % mod) % mod
    k = k*2 % mod

print(ans%mod)

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce

# a, b = [int(v) for v in input().split()]


def main():
    mod = 1000000007

    N = int(input())
    A = [int(v) for v in input().split()]

    dig = 60

    ans = 0
    for i in range(dig + 1):
        mask = 1 << i
        zero = sum(1 for a in A if a & mask == 0)
        ans += zero * (N - zero) * mask
        ans %= mod

    print(ans % mod)


main()

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 0
max_digit = 0
for i in range(n):
    max_digit = max(max_digit, len(bin(a[i])))
for i in range(max_digit):
    num1 = np.count_nonzero((a >> i) & 1)  # 1の数
    num2 = n - num1  # 0の数
    ans += pow(2, i, mod) * (num1 * num2) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

ans = 0

zero = [0] * 60
one = [0] * 60

for i in range(60):
    for j in range(n):
        if a[j] >> i & 1:
            one[i] += 1
        else:
            zero[i] += 1

ans = 0

for i in range(60):
    ans += one[i] * zero[i] * 2**i
    ans %= const

print(ans)

Submission status: Accepted

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

P = 10 ** 9 + 7
mod_array = [0] * 60
digit_array = [0] * 60
p = 1
for i in range(60):
    mod_array[i] = p
    p = (p * 2) % P

for a in a_array:
    for i in range(60):
        digit_array[i] += (a & (1 << i)) >> i
# print(digit_array)
ans = 0

for i in range(60):
    ans = (ans + mod_array[i] * digit_array[i] * (N - digit_array[i]) % P) % P

print(ans)

Submission status: Accepted

Solution code:
import numpy as np 
n=int(input())
a=np.array(list(map(int, input().split())))
sum=0
for i in range(60):
  x= np.count_nonzero(a>>i & 1)
  sum+=x*(n-x)<<i
print(sum%(10**9+7))

Submission status: Accepted

Solution code:
import numpy as np 
n=int(input())
a=np.array(list(map(int, input().split())))
sum=0
i=0
while a.any():
  x= np.count_nonzero(a & 1)
  sum+=x*(n-x)<<i
  a>>=1
  i+=1

print(sum%(10**9+7))

Submission status: Accepted

Solution code:
import numpy as np
LARGE = 10 ** 9 + 7
N = int(input())
A = np.array(input().split(), dtype=np.int64)

shift = 0
total = 0
while A.any():
    bits = np.count_nonzero(A & 1)
    total += (bits * (N - bits)) << shift
    A >>= 1
    shift += 1

print(total % LARGE)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array([i for i in list(map(int, input().split()))])
m = 10**9+7
ans = 0
for k in range(60):
    b = (a>>k) & 1
    res = np.count_nonzero(b)
    ans += res*(n-res)*2**k
print(ans%m)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()] , dtype=np.int64)
m = 10**9+7
ans = 0
for k in range(60):
    b = (a>>k) & 1
    res = np.count_nonzero(b)
    ans += res*(n-res)*2**k
print(ans%m)

Submission status: Accepted

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

ans = 0
for k in range(60):
    cnt_z = 0
    cnt_o = 0
    for i in range(len(a)):
        if (a[i] >> k) & 1 == 1:
            cnt_o += 1
        else:
            cnt_z += 1
    ans += ((cnt_o * cnt_z) * 2 ** k)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
blist=[0]*61
plist=[2**i for i in range(61)]
for i in range(n):
  tmp=arr[i]
  pos=0
  while tmp!=0:
    if tmp%2==1:
      blist[pos]+=1
      tmp-=1
    tmp=tmp//2
    pos+=1
ans=0
for i in range(61):
  ans+=(plist[i]*blist[i])*(n-blist[i])+(plist[i]*(n-blist[i]))*blist[i]
  ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
print(ans)

Submission status: Accepted

Solution code:

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

res = 0
bits = [0]*60
for a in al:
    i = 0
    b = a
    while b:
        bits[i] += b&1
        b = b >> 1
        i += 1

res = 0

for j in range(60):
    res += bits[j] * (n - bits[j])  * (2 ** j)

print(res % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    A = LMIIS()
    # maxNumBits = len(bin(max(A)))-2
    maxNumBits = 60
    numBitsOne = [0]*maxNumBits
    numBitsZero = [0]*maxNumBits

    for a in A:
        for i,b in enumerate(bin(a)[2:][::-1]):
            if b == '1':
                numBitsOne[i] += 1
    
    for i in range(maxNumBits):
        numBitsZero[i] = N - numBitsOne[i]

    numAnsBitsOne = []
    numAnsBits = list(map(lambda t : t[0]*t[1] , 
[t for t  in zip(numBitsOne,numBitsZero)]))
    
    ans = 0
    for i in range(maxNumBits):
        ans += numAnsBits[i] * 2**i
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    A = LMIIS()
    maxNumBits = len(bin(max(A)))-2
    numBitsOne = [0]*maxNumBits
    numBitsZero = [0]*maxNumBits

    for a in A:
        for i,b in enumerate(bin(a)[2:][::-1]):
            if b == '1':
                numBitsOne[i] += 1
    
    for i in range(maxNumBits):
        numBitsZero[i] = N - numBitsOne[i]

    numAnsBitsOne = []
    numAnsBits = list(map(lambda t : t[0]*t[1] , 
[t for t  in zip(numBitsOne,numBitsZero)]))
    
    ans = 0
    for i in range(maxNumBits):
        ans += numAnsBits[i] * 2**i
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
digit=[0 for i in range(0,61)]
for i in range(0,N):
    for j in range(0,60):
        digit[j+1]+=(A[i]>>j)&1
ans=((N-1)*sum(A))%(10**9+7)
X=[(digit[k]*(digit[k]-1)*2**(k-1))%(10**9+7) for k in range(1,61)]
print((ans-sum(X))%(10**9+7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    ans = 0
    MOD = 10**9+7
    k = 1
    x = np.max(A)
    n = 1 if x == 0 else int(np.log2(x))+1

    for i in range(n):
        c = np.count_nonzero(A%2)
        A >>= 1
        ans = (ans + c * (N-c) * k) % MOD
        k = (2*k) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7

twos = 1
ans = 0
for i in range(0,60):
    cou1 = np.count_nonzero((a >> i) & 1)
    ans += (cou1*(n-cou1)*twos)%mod
    twos = (twos*2)%mod

ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

mod = 10**9+7

bin_a = []

for i in range(n):
    bin_a.append(format(a[i],'060b'))

ans = 0

for i in range(60):
    one = 0
    zero = 0
    for j in range(n):
        #print(bin_a[j])
        if bin_a[j][i] == '1':
            one += 1
        else:
            zero += 1
    #print(i,zero,one)
    ans += zero * one * (2**(59-i))
    ans %= mod
    
print(ans%mod)

Submission status: Accepted

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

maxdig = 60
mod = 10**9+7

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

max_digits = 60
MOD = 10**9 + 7

ans = 0
for i in range(max_digits):
    one_num = np.count_nonzero((a >> i) & 1)
    radix_mod = 2**i % MOD
    ans += (radix_mod * one_num * (n - one_num)) % MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
from itertools import zip_longest

MOD = 10**9 + 7

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

a = ['{:b}'.format(i)[::-1] for i in a]

ans = 0
for k, v in enumerate(zip_longest(*a, fillvalue='0')):
    x = v.count('1')
    ans += x * (n - x) * 2**k % MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
mod=10**9+7
ans=0
for k in range(60):
  m=np.count_nonzero((a>>k)&1)
  ans+=m*(n-m)*2**k
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        # 先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    p = [pow(2, (leng - j - 1), mod) for j in range(leng)]
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
v=[0]*64
ans=0
mod=1000000007
zero=0
one=0

index=n-1
while index>=0:
	for k in range(61):
		one=v[k]
		zero=n-1-index-one
		tmp=1<<k
		if((a[index]&tmp)==0):
			ans=(ans+tmp*one)
		else:
			ans=(ans+tmp*zero)
			v[k]=v[k]+1
	index-=1

ans=ans%mod
print(ans)
print()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = len(format(max(a),"0b"))
b = []
for i in range(m):
  b.append(sum([1 for aa in a if (aa%(2**(i+1)))>=2**i]))
ans = 0
for i in range(m):
  ans += b[i]*(n-b[i])*(2**i)%(10**9+7)
ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

p = int(1e9+7)
res = 0

for i in range(60):
    zc = np.count_nonzero(A & 1)
    oc = N - zc

    res += zc*oc*2**i
    res %= p
    A >>= 1

print(res)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
s = input().split()
a = []
for i in range(n):
    a.append(int(s[i]))
arr = np.array(a)
# arr = np.array([int(i) for i in input().split()])

mod = 10 ** 9 + 7
ans = 0

for i in range(60):
    #arrについて2進数を右へ論理シフトした値になる？
    c1 = np.count_nonzero(arr & 1)
    ans += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    a = np.array(list(map(int,input().split())),dtype = int)
    MOD = 10**9+7
    ans = 0
    for n in range(60):
        bit = (a>>n)&1
        nonzero = np.count_nonzero(bit)
        zero = N-nonzero
        count = nonzero*zero
        for _ in range(n):
            count *= 2
            count %= MOD
        ans += count
        ans %= MOD
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
MOD = 10 ** 9 + 7
length = int(A.max()).bit_length()
answer = 0
for i in range(length):
    B = (A >> i) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    x *= 2 ** i % MOD
    answer += x

print(answer % MOD)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
MOD = 10 ** 9 + 7
length = int(A.max()).bit_length()
answer = 0
for i in range(length):
    B = (A >> i) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    x *= 2 ** i % MOD
    answer += x % MOD

print(answer % MOD)
# 18

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
MOD = 10 ** 9 + 7
length = int(A.max()).bit_length()
answer = 0
for i in range(length):
    B = (A >> i) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    x *= 2 ** i
    answer += x % MOD

print(answer % MOD)
# 18

Submission status: Accepted

Solution code:
import numpy as np


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    A = np.array(A, dtype=np.int64)
    modsum = 0
    for j in range(L):
        B = (A >> j) & 1
        count_ones = np.count_nonzero(B)
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

Solution code:
def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = sum([1 for a in A if (a >> j) & 1])
        # count_ones = sum([(A[i] >> j) & 1 for i in range(N)])
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

Solution code:
MOD=10**9+7

N=int(input())
A=list(map(int, input().split()))
ans=0
for i in range(60):
    x=0
    for j in range(N):
        if A[j]>>i&1: # A[j]のi桁目が1である場合
            x+=1
    now=x*(N-x)%MOD
    for j in range(i):
        now=now*2%MOD
    ans=(ans+now)%MOD
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

Cn, ans = N * (N-1) // 2, 0

for i in range(60):
    count = int(np.sum(A % 2))
    A //= 2
    if count == 0:
        continue
    ans += (Cn - (count*(count-1)//2 + (N-count)*(N-count-1)//2)) * (2**i)
print(ans % (10**9 + 7))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

MAX = 10**9 + 7

def main():
  n = int(input())
  As = numpy.array([int(line) for line in input().strip().split()])
  counts = numpy.zeros(60)
  for i in range(60):
    counts[i] = numpy.sum((As >> i) % 2)
  print(int(sum([(n-count) * count * (2**i) % MAX for i, count in  enumerate(counts)])) % MAX)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	
	keta =len(bin(max(A)))-2
	A = [ '{a:0{keta}b}'.format(a=a,keta=keta) for a in A]
	sum = 0
	for i in range(keta):
		bit = [a[i] for a in A]
		sum = sum + (2**(keta-i-1) * ( bit.count('1')*bit.count('0')))
	print(sum % (10**9+7))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    A = Scanner.map_int()
    ans = 0
    for k in range(61):
        x = 0
        for i in range(N):
            if (A[i] >> k) & 1:
                x += 1
        y = N - x
        tmp = x * y
        tmp %= MOD
        for _ in range(k):
            tmp *= 2
            tmp %= MOD
        ans += tmp
        ans %= MOD
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()])

ans=0
for i in range(61):
  B = (A >> i) & 1
  x = np.count_nonzero(B == 0)
  y = N - x
  ans += (x*y*(2**i))%(10**9+7)
  
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
t = 0
u = 0
m = max(A)
for i in range(60):
    if m >= 2**i:
        u += 1
    else: break
for i in range(u):
    for j in range(N):
        t += (A[j] >> i) & 1
    ans += (t * (N-t)) * 2**i
    t = 0
print(ans%1000000007)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
ans = 0
m = 1
ans = 0
for _ in range(60):
    one_count = sum(a & m for a in aaa)
    one_count //= m
    zero_count = n - one_count
    ans = (ans + one_count * zero_count * m) % MOD
    m *= 2
        
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

def main():
  MOD = 10**9+7
  n = int(input())
  A = np.array(input().split(), dtype=np.int64)
  ans = 0
  for j in range(61):
    X = A>>j & 1
    t = np.count_nonzero(X)
    ans += pow(2, j, MOD) * t * (n-t) % MOD
  print(ans%MOD)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read

def main():
  MOD = 10**9+7
  n, *A = map(int, read().split())
  ans = 0
  for j in range(61):
    c = 0
    for i in A:
      if i>>j & 1:
        c += 1
    ans += 2**j*((n-c)*c)
    ans %= MOD
  print(ans%MOD)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=0
for j in range(len(bin(max(a)))-2):
    cnt1=0
    cnt0=0
    for i in range(n):
      if (a[i]>>j)&1:
        cnt1+=1
      else:
        cnt0+=1
    s+=(cnt1*cnt0*2**j)%(10**9+7)
print(s%(10**9+7))

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):
  x=1<<i
  o=sum(1 for j in a if j&x)
  ans+=x*o*(n-o)
  ans%=mod
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):
  x=1<<i
  o=len([0 for j in a if j&x])
  ans+=x*o*(n-o)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
a=np.array([int(i) for i in input().split()])
mod=int(1e9+7)
ans=0
for k in range(60):
  b=(a>>k)&1
  m=np.count_nonzero(b)
  ans+=m*(n-m)*2**k
  ans%=mod
print(ans)

Submission status: Accepted

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