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: Time Limit Exceeded

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

        else:
            z[j] = z[j]+1

        j = j+1

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


print(cnt)

Submission status: Time Limit Exceeded

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

        else:
            z[j] = z[j]+1

        j = j+1


cnt = 0
for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    j = u-1
    y = 0
    while(j > -1):
        if a[y] == "0":
            z[y] = z[y]-1
            cnt = (cnt+((2**j)*o[y])%M)%M

        if a[y] == "1":
            o[y] = o[y]-1
            cnt = (cnt + ((2 ** j) * z[y]) % M) % M

        y = y+1
        j = j-1

print(cnt)

Submission status: Time Limit Exceeded

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

        j = j+1

cnt = 0
z = len(o)*[0]
for i in range(len(o)):
    z[i] = len(l)-o[i]


for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    j = u-1
    y = 0
    while(j > -1):
        if a[y] == "0":
            z[y] = z[y]-1
            cnt = (cnt+((2**j)*o[y])%M)%M

        if a[y] == "1":
            o[y] = o[y]-1
            cnt = (cnt + ((2 ** j) * z[y]) % M) % M

        y = y+1
        j = j-1

print(cnt)

Submission status: Time Limit Exceeded

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

        j = j+1

cnt = 0
z = len(o)*[0]
for i in range(len(o)):
    z[i] = len(l)-o[i]


for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    j = u-1
    y = 0
    while(j > -1):
        if a[y] == "1":
            #print(o[])
            o[y] = o[y] - 1

        if a[y] == "0":
            z[y] = z[y]-1

        y = y+1
        j = j-1

    j = u-1
    y = 0
    while(j > -1):
        if a[y] == "0":
            cnt = (cnt+((2**j)*o[y])%M)%M

        if a[y] == "1":
            cnt = (cnt + ((2 ** j) * z[y]) % M) % M

        y = y+1
        j = j-1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
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: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
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
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 * 2**i ) % ( 10**9 + 7 )
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
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
for i in range(60):
    s = 0
    t = 0
    for x in a:
        if ( x // 2**i ) % 2 == 0:
            s += 1
        else:
            t += 1
    ans = ( ans + s * t * 2**i ) % ( 10**9 + 7 )
print(ans)

Submission status: Time Limit Exceeded

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

        j = j+1

#print(o)
cnt = 0
z = len(o)*[0]
for i in range(len(o)):
    z[i] = len(l)-o[i]

o = o[::-1]
z = z[::-1]
for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    a = a[::-1]
    j = u - 1
    while(j > -1):
        if a[j] == "1":
            o[j] = o[j] - 1

        if a[j] == "0":
            z[j] = z[j]-1

        j = j - 1

    j = u-1
    while(j > -1):
        if a[j] == "0":
            cnt = (cnt+((2**j)*o[j])%M)%M

        if a[j] == "1":
            cnt = (cnt + ((2 ** j) * z[j]) % M) % M


        j = j-1

    j = u-1
    #print(cnt)

print(cnt)

Submission status: Time Limit Exceeded

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

        j = j+1

#print(o)
cnt = 0
z = len(o)*[0]
for i in range(len(o)):
    z[i] = len(l)-o[i]

o = o[::-1]
z = z[::-1]
for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    a = a[::-1]
    j = u - 1
    #print(o,"lo")
    #print(z,"lo")
    while(j > -1):
        if a[j] == "1":
            o[j] = o[j] - 1

        j = j - 1

    j = u-1
    #print(a)
    #print(o)
    while(j > -1):
        if a[j] == "0":
            z[j] = z[j]-1
            cnt = (cnt+((2**j)*o[j])%M)%M

        j = j-1

    j = u-1
    #print(cnt)
    #print(z)
    while (j > -1):
        if a[j] == "1":
            cnt = (cnt + ((2 ** j) * z[j])%M) % M

        j = j - 1

    #print(cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
x = max(l)
s = bin(x)
u = len(s)-2
o = [0]*u
for i in l:
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u - len(a)
    a = (["0"] * d) + a
    j = 0
    while(j < len(o)):
        if a[j] == "1":
            o[j] = o[j]+1

        j = j+1

#print(o)
cnt = 0
z = len(o)*[0]
for i in range(len(o)):
    z[i] = len(l)-o[i]

o = o[::-1]
z = z[::-1]
for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    a = a[::-1]
    j = u - 1
    #print(o,"lo")
    #print(z,"lo")
    while(j > -1):
        if a[j] == "1":
            o[j] = o[j] - 1

        j = j - 1

    j = u-1
    #print(a)
    #print(o)
    while(j > -1):
        if a[j] == "0":
            z[j] = z[j]-1
            cnt = (cnt+((2**j)*o[j])%M)%M

        j = j-1

    j = u-1
    #print(cnt)
    #print(z)
    while (j > -1):
        if a[j] == "1":
            cnt = (cnt + ((2 ** j) * z[j])%M) % M

        j = j - 1

    #print(cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
x = max(l)
s = bin(x)
u = len(s)-2
o = [0]*u
for i in l:
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u - len(a)
    a = (["0"] * d) + a
    j = 0
    while(j < len(o)):
        if a[j] == "1":
            o[j] = o[j]+1

        j = j+1

#print(o)
cnt = 0
z = len(o)*[0]
for i in range(len(o)):
    z[i] = len(l)-o[i]

o = o[::-1]
z = z[::-1]
for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    a = a[::-1]
    j = u - 1
    #print(o,"lo")
    #print(z,"lo")
    while(j > -1):
        if a[j] == "1":
            o[j] = o[j] - 1

        j = j - 1

    j = u-1
    #print(a)
    #print(o)
    while(j > -1):
        if a[j] == "0":
            z[j] = z[j]-1
            cnt = (cnt+((2**j)*o[j]))%M

        j = j-1

    j = u-1
    #print(cnt)
    #print(z)
    while (j > -1):
        if a[j] == "1":
            cnt = (cnt + ((2 ** j) * z[j])) % M

        j = j - 1

    #print(cnt)

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

ans = 0
# 制約より、aはそれぞれ60桁以内で表せる
# i+1(=1,2,...,60)桁目についてそれぞれ考える
for i in range(60):
    k = 1 << i  # k = 100....00(2) = 2**i(10)
    cnt_1 = 0
    cnt_0 = 0

    for ai in a:
        if k & ai:
            cnt_1 += 1
        else:
            cnt_0 += 1
    # 1 XOR 0 = 1 となる個数 = cnt_1 * cnt_0
    ans += (k % mod * cnt_1 * cnt_0) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

ans = 0
# 制約より、aはそれぞれ60桁以内で表せる
# i+1(=1,2,...,60)桁目についてそれぞれ考える
for i in range(60):
    k = 1 << i  # k = 100....00(2) = 2**i(10)
    cnt_1 = 0
    cnt_0 = 0

    for ai in a:
        if k & ai:
            cnt_1 += 1
        else:
            cnt_0 += 1
    # 1 XOR 0 = 1 となる個数 = cnt_1 * cnt_0
    ans += (k * cnt_1 * cnt_0) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    ans+=a[i]^a[j]
    ans%=1000000007
print(ans)

Submission status: Time Limit Exceeded

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

res = 0
for i in range(n):
  for j in range(i+1, n):
    res += (a_lst[i] ^ a_lst[j])
print(res % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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: Time Limit Exceeded

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, 0] for _ in range(n)]

for x in A:
	x = "{:b}".format(x).zfill(n)
	for i in range(n):
		cnt[i][int(x[-(i+1)])] += 1

ans = 0

for i in range(n):
	bit_sum = ((cnt[i][0]*cnt[i][1])%mod) * pow(2, i, mod) % mod
	ans = (ans+bit_sum)%mod

print(ans)

Submission status: Time Limit Exceeded

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 = 60
cnt = [[0, 0] for _ in range(n)]

for x in A:
	x = "{:b}".format(x).zfill(n)
	for i in range(n):
		cnt[i][int(x[-(i+1)])] += 1

ans = 0

for i in range(n):
	bit_sum = ((cnt[i][0]*cnt[i][1])%mod) * pow(2, i, mod) % mod
	ans = (ans+bit_sum)%mod

print(ans)

Submission status: Time Limit Exceeded

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:]
        bs.append(s)
        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[len(s)-1-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: Time Limit Exceeded

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: Time Limit Exceeded

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
        b=1
        j=0
        while b<=a[i]:
            if a[i]&b==b:
                hist[j]+=1
            b*=2
            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: Time Limit Exceeded

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)
    #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: Time Limit Exceeded

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)
    #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
    return sum

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
answer = 0
for i in range(N-1):
    for j in range(i+1,N):
        
        answer += (A[i] ^ A[j])
        answer %= 10**9+7
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


def format2binary(n):
    return list(reversed(format(n, '060b')))


binaries = np.array(list(map(format2binary, A)))

zeros = np.sum((binaries == '0'), axis=0)
ones = np.sum((binaries == '1'), axis=0)

base = 1
ans = 0

for i in range(len(zeros)):
    ans += zeros[i] * ones[i] * base
    ans %= MOD
    base *= 2
    base %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

zeros = [0] * 60
ones = [0] * 60

for a in A:
    for i, bit in enumerate(reversed(format(a, '060b'))):
        if bit == '0':
            zeros[i] += 1
        else:
            ones[i] += 1

base = 1
ans = 0

for i in range(len(zeros)):
    ans += zeros[i] * ones[i] * base
    ans %= MOD
    base *= 2
    base %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
a = [format(i,'b') for i in A]
ans = 0
mod = 10**9+7
for i in range(60):
  cnt = 0
  for v in a:
    if len(v)<i+1:
      continue
    if v[-1-i]=='1':
      cnt += 1
  cnt = cnt*(n-cnt)%mod
  ans += cnt*(2**i)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

zeros = [0] * 61
ones = [0] * 61

for a in A_list:
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            ones[i] += 1
        else:
            zeros[i] += 1

res = 0
for a in A_list:
    twice = 1
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            cnt = zeros[i]
            ones[i] -= 1
        else:
            cnt = ones[i]
            zeros[i] -= 1
        res += twice * cnt
        twice *= 2
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

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):
        c = 0
        while a[i]>0:
            if a[i] %2 == 1:
                div[c] += 1
            a[i] = a[i]//2
            c+=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: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    mod = 10**9+7
    div = {}
    for i in range(n):
        c = 0
        while a[i]>0:
            if a[i]%2==1:
                if c not in div.keys():
                    div[c] = 1
                else:
                    div[c] += 1
            a[i] = a[i]//2
            c += 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: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
from collections import Counter
import numpy as np

def bi(s):
  return list(map(int, list(np.binary_repr(int(s),width=64))))

mod = 10**9+7
base = 2**np.arange(63,-1,-1) % mod

N=int(input())
A=list(map(bi,input().split()))
count=np.array(A).reshape(N,64).sum(0)

print((base*count*(N-count)).sum() % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import numpy as np

N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7
base = 2**np.arange(63,-1,-1) % mod

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

print((base*count*(N-count)).sum() % mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
aaa = list(map(int, input().split()))
zero = [0] * 61
one = [0] * 61
for a in aaa:
    for i in range(61):
        if a & (1<<i):
            one[i] += 1
        else:
            zero[i] += 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: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
aaa = np.array(list(map(int, input().split())), dtype='int64')
MOD = 1_000_000_007
ans = 0
for j in range(1, N):
    ans += sum((aaa[:j] ^ aaa[j]) % MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
aaa = list(map(int, input().split()))
ans = 0
MOD = 1_000_000_007
for i in range(N-1):
    for j in range(i + 1, N):
        ans += aaa[i] ^ aaa[j]
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
mod = pow(10,9) + 7
D = defaultdict(lambda:0)
for a in A:
    for i in range(61):
        D[1 << i] += bool(a & (1 << i))
ans = 0
for k, v in D.items():
    ans += k * (v * (n - v))
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(60):
    one = 0
    for a in A:
        if (a & (1 << i) != 0):
            one += 1
    zero = N - one
    now = one * zero % mod
    ans += now * pow(2, i) % mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    BN = 64
    B = [[0] * BN for _ in range(N+1)]
    for i, a in enumerate(A):
        for j in range(BN):
            B[i+1][j] = B[i][j] + ((a >> j) & 1)
    ans = 0
    for i in range(BN):
        b = 1 << i
        for j, a in enumerate(A):
            n = B[N][i] - B[j+1][i]
            if a & b:
                n = N - j  - n - 1
            ans = (ans + b * n % MOD) % MOD
    return ans


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

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