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 numpy as np #numpyの練習がてら
n = int(input())
tmp = list(map(int,input().split()))

mod = 10**9 + 7
a = np.array(tmp,np.int64)

ans = 0
for i in range(60 + 1):
    b = (a >> i) & 1 #すべてのaについて2**n乗目のビットが1か否か
    iti = np.count_nonzero(b) #すべてのaのうち2**n乗目が1であるものの個数
    zero = n - iti #同様に0であるものの個数
    ans += (iti * zero) * pow(2,i,mod) % mod#片方1で片方0なら1なので1の個数×0の個数
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):
    cou  = 0
    bit = 1 << i
    for j in a:
        if j & bit:
            cou += 1
    num1 = cou
    num0 = n - num1
    ans += ((num1*num0) * bit )%mod
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = pow(10, 9) + 7


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

m = max(a)

num = [0] * 61

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

s = 0

#print(num)

for i in range(61):
    s += (n - num[i]) * num[i] * pow(2, i, MOD) % MOD

print(s % MOD)

Submission status: Accepted

Solution code:
import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n=INT()
    a=np.array(LIST())
    ans=0
    mod=10**9+7
    for i in range(70):
        digit=np.sum((a>>i)&1)
        ans+=pow(2,i,mod)*(((n-digit)*digit)%mod)%mod
        ans=ans%mod
    
    print(ans)



if __name__=='__main__':
    do()

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):
    cnt = 0
    digit = 1 << i
    for j in a:
        if digit & j:
            cnt += 1
    ans += digit*cnt*(n - cnt)%mod

print(ans%mod)

Submission status: Accepted

Solution code:
def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

N = cin()
A = cin()
INF = 10 ** 9 + 7

res = [0 for _ in range(65)]
for i in range(65):
    c0, c1 = 0, 0
    for j in range(N):
        if bool(A[j] & (1 << i)):  c1 += 1
        else:  c0 += 1
    res[i] = c0 * c1
ans = 0
for i in range(65):  ans = (ans + (1 << i) * res[i]) % INF
print(ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
o = [0]*61
z = [0]*61
for i in l:
    a = bin(i)[2:]
    j = 0
    while(j < len(a)):
        if a[j] == "1":
            o[len(a)-j-1] += 1

        j += 1

cnt = 0
b = 1
for j in range(len(o)):
    cnt = (cnt+(o[j]*(n-o[j])*b)%M)%M
    b *= 2

print(cnt)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
o = [0]*61
z = [0]*61
for i in l:
    a = bin(i)[2:]
    j = 0
    while(j < len(a)):
        if a[j] == "1":
            o[len(a)-j-1] += 1

        j += 1

cnt = 0
b = 1
for j in range(len(o)):
    cnt = (cnt+(o[j]*(n-o[j])*b)%M)%M
    b *= 2

print(cnt)

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)

        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1
        # j=0
        # ai=a[i]
        # while ai>0:
        #     if ai&1==1:
        #         hist[j]+=1
        #     ai = ai >> 1
        #     j+=1


    #print(bs)
    #print(hist)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()

ans = 0
k = 1
for i in range(60):
    s = 0
    t = 0
    for j in range(n):
        if a[j] % 2 == 0:
            s += 1
        else:
            t += 1
        a[j] //= 2
    ans = ( ans + s * t * k ) % ( 10**9 + 7 )
    k *= 2
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array([int(x) for x in input().split()])

ans = 0
mod = pow(10, 9)+7
for i in range(100):
  c = np.sum((a>>i)&1)
  ans += (c*(n-c)%mod)*pow(2, i, mod)%mod
  ans %= mod

print(ans)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    size = 60
    digits = [[0, 0] for _ in range(size)]
    for a in read_ints():
        for i in range(size-1, -1, -1):
            digits[i][a&1] += 1
            a >>= 1
    p = 1
    answer = 0
    modulo = 10**9+7
    for i in range(size-1, -1, -1):
        answer = (answer+p*digits[i][0]*digits[i][1])%modulo
        p *= 2
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:

mod = 10**9+7
n = int(input())
arr = list(map(int , input().split()))
dp = [ [0 for i in range(67)] for j in range(0, n+6)]
for i in range(n-1,0 , -1):
	for j in range( 0 , 61):
		dp[i+1][j]=dp[i+2][j]
	for j in range(0 , 61):
		if (arr[i] &(1<<j)):
			dp[i+1][j]+=1
ans = 0
for i in range(1 , n+1):
	for j in range(0 , 61):
		if (arr[i-1]&(1<<j)):
			ust = n-i-dp[i+1][j]
			ans = ans + (ust*(1<<j))
			ans = ans%mod
		else:
			st = dp[i+1][j]
			ans = ans+(st*(1<<j))
			ans = ans%mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
zero_count = [0]*70
one_count  = [0]*70

for a in A:
    count_ = [0]*70
    bin_a = list(bin(a)[2:])
    bin_a.reverse()
    
    for b_idx,b in enumerate(bin_a):
        count_[b_idx] = int(b)
        
#     print(count_)
    
    for c_idx,c in enumerate(count_):
        if c == 0: 
            zero_count[c_idx] += 1
            
        elif c == 1: 
            one_count[c_idx] += 1
            
# print(zero_count,one_count)
ans = 0     

for l in range(70):
    ans += zero_count[l]*one_count[l]*(2**l)
    
print(ans%((10**9)+7))

Submission status: Accepted

Solution code:

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

MOD = 10 ** 9 + 7
ans = 0
for b in range(61):
    ctr = [0, 0]
    for i in range(N):
        ctr[X[i] >> b & 1] += 1

    ans += (1 << b) * ctr[0] * ctr[1]
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
X=[0]*60
M=10**9+7
N=int(input())
T=500000004

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

for a in A:
    for k in range(60):
        X[k]+=a%2
        a>>=1


Y=0
y=1
for b in X:
    Y+=b*(N-b)*y
    Y%=M
    y<<=1
print(Y)

Submission status: Accepted

Solution code:
import numpy as np

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

for i in range(60):
  keta = a>>i & 1
  num1 = int(keta.sum())
  num0 = n - num1
  ans+= ((2**i)%mod)*(num1*num0)
  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):
  keta=1<<i
  cnt=0
  for j in a:
    if keta & j:
      cnt+=1
  ans+=keta*cnt*(n-cnt)%mod


print(ans%mod)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10**9+7
sm=0

for i in range(60):
    c1 = np.count_nonzero(arr & 1)
    sm += 2 ** i * c1 * (n-c1)
    arr >>= 1

print(sm%mod)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
b = [0] * 60
ans = 0
for i in range(n):
    for j in range(60):
        ans += 2**j * (i - b[j] if a[i] >> j & 1 else b[j])
        ans %= 10**9 + 7
    for j in range(len(bin(a[i])) - 2):
        b[j] += a[i] >> j & 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
L = 60
MOD = 10**9 + 7
data = [0]*L
for a in A:
    S = reversed(bin(a)[2:])
    for i, s in enumerate(S):
        data[i] += s=="1"
p = 1
res = 0
for i in range(L):
    res += data[i]*(N-data[i])*p
    p *= 2
    p %= MOD
print(res%MOD)

Submission status: Accepted

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

rlt = 0
pw = 1
for i in range(61):
  c0 = 0
  c1 = 0
  for j in range(N):
    a = As[j]
    if a % 2 == 0:
      c0 += 1
    else:
      c1 += 1
    As[j] = a//2
  rlt += c0*c1*pw % P
  rlt %= P
  pw *= 2
  
print(rlt)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10**9+7
sm=0

for i in range(60):
    c1 = np.count_nonzero(arr & 1)
    sm += 2 ** i * c1 * (n-c1)
    arr >>= 1

print(sm%mod)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

n = max(A).bit_length()

cnt = [0]*n

for x in A:
	for i, y in enumerate("{:b}".format(x).zfill(n)[::-1]):
		if y == "1":
			cnt[i] += 1

ans = 0

for i, c in enumerate(cnt):
	bit_sum = (c*(N-c)%mod) * pow(2, i, mod) % mod
	ans = (ans+bit_sum)%mod

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)

Submission status: Accepted

Solution code:
MOD = 10**9+7
def resolve():
    N = int(input())
    A = list(map(lambda x: bin(int(x))[2:].zfill(60), input().split()))
    ans = 0
    for i in range(60):
        one_cnt = 0
        zero_cnt = 0
        for a in A:
            if a[i] == "1":
                one_cnt += 1
            else:
                zero_cnt += 1
        ans += (one_cnt*zero_cnt)*(2**(59-i))
        ans %= MOD
    print(ans)

    

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

num_per_digit = [0]*60

for i in range(60):
    num = 0
    for j,a in enumerate(A):
        num += a % 2
        A[j] //= 2
    num_per_digit[i] = num

result = 0    
for d,num in enumerate(num_per_digit):
    result = (result + num * (N - num) * pow(2, d, MOD)) % MOD
    
print(result)

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)

        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1
        # j=0
        # ai=a[i]
        # while ai>0:
        #     if ai&1==1:
        #         hist[j]+=1
        #     ai = ai >> 1
        #     j+=1


    #print(bs)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)
        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1

    #print(bs)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)

Submission status: Accepted

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

# 解説AC
ans, num = 0,1
for i in range(60):
    cnt = sum((ai & num) == num for ai in a)
    ans += (cnt * (n - cnt) * num) % mod
    num <<= 1
print(ans % mod)

Submission status: Accepted

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

# 解説AC
ans, num = 0,1
for i in range(60):
    cnt = sum((ai & num) >> i for ai in a)
    ans += (cnt * (n - cnt) * num) % mod
    num <<= 1
print(ans % mod)

Submission status: Accepted

Solution code:
# if required XOR, re-solve later.
# just copy and paste from https://atcoder.jp/contests/abc147/submissions/14707076
for i in range(pow(10,6)):
    pass
# added due to avoid duplicated search list wtih the same solver.
n = int(input())
a = list(map(int,input().split()))
d = 0
m = 10**9+7
for i in range(60):
    b = 1<<i
    l = len([1for j in a if j&b])
    d += l*(n-l)*b%m
    d %= m
print(d)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
INF = 10 ** 9 + 7

D = defaultdict(int)
for a in A:
    for i in range(61):
        # a の i ビット目がたっているか否か
        D[1 << i] += bool(a & (1 << i))

ans = 0
for key, value in D.items():
    ans += key * value * (N - value)
    ans %= INF

print(ans % INF)

Submission status: Accepted

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n=int(input())
    A=np.array(list(map(int, input().split())),dtype='int64')
    ans = 0
    mod = 10**9 + 7
    for i in range(60):
        q = int((A >> i & 0b1).sum())
        ans += q*(n-q)*pow(2, i, mod)
        ans %= mod
    print(ans)
 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()

    # 桁ごとに1の足される数を数える方針

    # 下準備 Aの中で、d桁目が1であるものの個数
    cnt = [0] * 60
    for i in A:
        for j in range(60):
            if i >> j & 1:
                cnt[j] += 1

    # 繰り上がりのない2進数→10進数に変換
    ans = 0
    for i in range(60):
        # i桁目に1の足される数に2のi乗をかければよい
        ans += cnt[i] * (N - cnt[i]) * pow(2, i, MOD)
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
m = 10**9+7
sumA = 0
for i in range(60):
    cnt1 = 0
    for a in A:
        if a>>i & 1:
            cnt1 += 1
    sumA += (cnt1*(N-cnt1)*2**i)%m
print(sumA%m)

Submission status: Accepted

Solution code:
import numpy as np

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

a = np.array(a, dtype='int64')
MOD = 10**9+7
ans = 0
for i in range(60):
    ca = a >> i & 1
    c1 = int(ca.sum())
    c0 = n - c1
    c0c1 = (c0 * c1) % MOD
    c0c1pow = (c0c1 * 2**i) % MOD
    ans = (ans + c0c1pow) % 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(61):
    x=0
    for j in range(N):
        if A[j]>>i&0b1:
            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 numpy as np

N = int(input())
A = tuple(map(int, input().split(' ')))
A = np.array(A, dtype=np.int64)
MOD = 10 ** 9 + 7

ans = 0
mask = 1

for i in range(60):
    ones = np.count_nonzero(A & mask)
    ans += (ones * (N - ones) % MOD) * (mask % MOD)
    ans %= MOD
    mask <<= 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    mod = 10**9+7
    div = {}
    for i in range(61):
        div[i] = 0
    for i in range(n):
        b = bin(a[i])
        l = len(b)
        for j in range(l-2):
            if b[l-1-j]=='1':
                div[j]+=1
    ans = 0
    for k in div.keys():
        ans += div[k] * (n-div[k]) * 2**k
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 1_000_000_007

  mem0 = [[0]*60 for _ in range(N+1)]
  mem1 = [[0]*60 for _ in range(N+1)]
  for i in range(1, N+1):
    # j 桁目について
    for j in range(60):
      if A[i-1] & (1 << j):
        mem1[i][j] = mem1[i-1][j] + 1
        mem0[i][j] = mem0[i-1][j]
      else:
        mem1[i][j] = mem1[i-1][j]
        mem0[i][j] = mem0[i-1][j] + 1

  sum_ = 0
  MAX = len(bin(max(A))) - 2
  for i in range(1, N+1):
    for j in range(MAX):
      if A[i-1] & (1 << j):
        sum_ += ( (1 << j)*(mem0[N][j] - mem0[i][j]) % MOD )
      else:
        sum_ += ( (1 << j)*(mem1[N][j] - mem1[i][j]) % MOD )

  print(sum_ % MOD)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7
base = [(2**i)%mod for i in range(63,-1,-1)]

count = [0 for i in range(64)]
for i in range(N):
  b = list(map(int, list(bin(A[i])[2:])))
  b = [0]*(64-len(b))+b
  for j in range(64):count[j]+=b[j]

print(sum([base[i]*count[i]*(N-count[i]) for i in range(64)])%mod)

Submission status: Accepted

Solution code:
N = int(input())
aaa = list(map(int, input().split()))
bbb = [format(a, '061b') for a in aaa]

zero = [0] * 61
one = [0] * 61
for i in range(61):
    s = ''.join(list(b[-(i+1)] for b in bbb))
    zero[i] = s.count('0')
    one[i] = s.count('1')
ans = 0
MOD = 1_000_000_007
for i, o, l in zip(range(61), zero, one):
    ans += 2**i * o * l
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
l = max(a).bit_length()
ans = 0
M = 10**9+7
for j in range(l):
    v0 = 0
    v1 = 0    
    for i in range(n):
        if (a[i]>>j)&1:
            v1 += 1
        else:
            v0 += 1
    ans += v0*v1*pow(2,j,M)
    ans %= M
print(ans%M)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

mod=10**9+7
n=int(input())
a=lmp()
l=[[0,0] for i in range(60)]
for i in range(n):
    b=format(a[i],"060b")
    for j in range(60):
        if b[j]=="0":
            l[j][0]+=1
        else:
            l[j][1]+=1
ans=0
for i in range(60):
    ans+=(l[i][0]*l[i][1]*(2**(59-i)))%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n]*finv[r]*finv[n-r]%p

def perm(n,r,p):
  if (r < 0) or (n < r):
    return 0
  return fac[n]*finv[n-r]%p

N = 310000
MOD = pow(10,9)+7

fac = [-1]*(N+1); fac[0] = 1; fac[1] = 1 #階乗
finv = [-1]*(N+1); finv[0] = 1; finv[1] = 1 #階乗の逆元
inv = [-1]*(N+1); inv[0] = 0; inv[1] = 1 #逆元
for i in range(2,N+1):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD
  finv[i] = finv[i-1]*inv[i]%MOD

M = int(input())
A = list(map(int,input().split()))
MAX = 63
L = [0]*MAX

for i in range(M):
  for j in range(MAX):
    if A[i]>>j&1:
      L[j] += 1
#print(L)
ans = 0
for i in range(MAX):
  base = pow(2,i)
  kosu = cmb(M,2,MOD)-cmb(L[i],2,MOD)-cmb(M-L[i],2,MOD)
  ans += base*kosu%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
a=lnii()

mod=10**9+7

ans=0
for i in range(60):
  on=0
  off=0
  for j in a:
    if (j>>i)&1:
      on+=1
    else:
      off+=1
  ans+=(on*off)*(2**i)
  ans%=mod

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
mod = 10**9+7

bits = [0]*70
for a in As:
    for l in range(a.bit_length()):
        if (a>>l)&1:
            bits[l] += 1

ans = 0
for i in range(70):
    one = bits[i]
    zero = N-one
    mul = pow(2, i, mod)
    ans += one*zero*mul
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
p0 = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p0
    else:
        return (x*(pow(x,(m-1)//2)**2)%p0)%p0

N = int(input())
A = list(map(int,input().split()))
A = [bin(A[i])[2:] for i in range(N)]
A = ["0"*(60-len(A[i]))+A[i] for i in range(N)]
C = {k:0 for k in range(60)}
for i in range(N):
    for m in range(60):
        if A[i][m]=="1":
            C[59-m] += 1
B = [0 for _ in range(60)]
for k in range(60):
    p = C[k]
    m = N-C[k]
    B[k] = p*m
cnt = 0
for k in range(60):
    cnt = (cnt+B[k]*pow(2,k))%p0
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
ln = len(bin(max(a))) -2
cnt = [0] * ln
for x in a:
    for shift in range(ln):
        cnt[shift] += (x>>shift)%2
# print(cnt)
res = 0
for i in range(ln):
    now = cnt[i] * (n-cnt[i])
    res += now*pow(2,i)
    res %= mod
print(res)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def solve():

    n = getN()
    nums = getList()
    keta = [[0, 0] for i in range(62)]

    for num in nums:
        tmp = num
        for i in range(62):
            if tmp % 2 == 1:
                keta[i][1] += 1
            else:
                keta[i][0] += 1

            tmp //= 2

    ans = 0
    dig = 0
    for k1, k2 in keta:
        ans += ((k1 * k2) * (2**dig)) % MOD
        dig += 1

    print(ans % MOD)


def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

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):
  on=0
  for j in a:
    if (j>>i)&1:
      on+=1
  ans+=(on*(n-on))*(2**i)
  ans%=mod

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

s=0
for i in range(60):
    bit = np.count_nonzero(a & 1)
    s += bit*(n-bit)*(2**i)
    a >>= 1
print(s % mod)

Submission status: Accepted

Solution code:
import math

def main():
    mod = 1000000007
    N = int(input())
    A = list(map(int, input().split()))

    A_max = sorted(A)[-1]
    if A_max == 0:
        print(0)
        exit()
    bit_max = int(math.ceil(math.log2(A_max)))

    i = 0
    bit = 1
    res = 0
    while i <= bit_max:
        c_zero = 0
        c_one = 0
        for j in range(N):
            if A[j] & bit == 0:
                c_zero += 1
            else:
                c_one += 1
        m_bit = bit % mod
        res += m_bit*c_zero*c_one
        res %= mod
        i += 1
        bit<<=1
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, *A = map(int, open(0).read().split())
A = np.array(A, dtype=np.int64)
mod = 10**9 + 7
 
ans = 0
for i in range(60):
    mask = 1 << i
    cnt = np.count_nonzero(A&mask)
    x = cnt * (N-cnt)
    x *= mask % mod
    ans += x
    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 j in range(60):
    one_num = 0
    for i in A:
        if (i >> j) & 1:
            one_num += 1
    ans += one_num * (N - one_num) * 2**j
    ans %= mod
print(ans)

Submission status: Accepted

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

n, s, res, MOD = int(input()), list(map(int, input().split())), 0, int(1e9) + 7
for i in range(61):
    x, c = int(pow(2, i, MOD)), [0, 0]
    for j in range(n): c[1 if s[j] & 1 << i else 0] += 1
    x = (x * c[0]) % MOD; x = (x * c[1]) % MOD; res = (res + x) % MOD
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MAX = max(A)
BIG = 10**9+7
L = len(bin(MAX)[2:])
ans = 0
for j in range(L):
    zero = 0
    one = 0
    for i in range(N):
        if (A[i] >> j) & 1:
            one+=1
        else:
            zero+=1
    ans += ((zero*one)%BIG)*pow(2,j,BIG)
    ans = ans%BIG
print(ans)

Submission status: Accepted

Solution code:
import math

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

Sum = 0
mod = (10 ** 9) + 7

for i in range(len(bin(max(A)))-2):
    Sum_1 = 0
    for j in range(N):
        #print(i, j)
        if ((A[j] >> i) & 1):
            Sum_1 += 1

    Sum_0 = N - Sum_1

    Sum = (Sum + ((Sum_0 * Sum_1) % mod * (2 ** i)) % mod) % mod
    # print(Sum_0,Sum_1)

print(Sum)

Submission status: Accepted

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

  ans = 0
  for j in range(digit):
    o = 0
    for i in a:
      if (i >> j) & 1:
        o += 1
    ans += o*(n-o)*2**j
    ans %= MOD
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    ans = 0
    mod = 10 ** 9 + 7
    for d in range(61):
        # d桁目ごとに考える
        x = 0
        for a in A:
            if (a >> d) & 1:
                x += 1
        ans += x * (n-x) * 2**d
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    ans = 0
    mod = 10 ** 9 + 7
    for d in range(61):
        # d桁目ごとに考える
        x = 0
        for a in A:
            if (a >> d) & 1:
                x += 1
        ans += x * (n-x) * 2**d
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()