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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0]*60
    for a in A:
        for i in range(len(B)):
            if a & (2**i):
                B[i] += 1
    ans = 0
    for i, b in enumerate(B):
        ans += 2**i * b * (N-b)
        ans %= 10**9+7
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9) + 7

n = int(input())
a = list(map(int, input().split()))
ans = 0
for b in range(60)[::-1]:
    ans <<=1
    c = sum(a[i]>>b & 1 for i in range(n))
    ans = (ans + c*(n-c))%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = []
lenge = 0
for i in range(n):
    b.append(format(a[i],"b"))
    lenge = max(lenge,len(b[i]))
ans = 0
for i in range(lenge):
    zero_count = 0
    one_count = 0
    for j in range(n):
        if len(b[j]) > i:
            if b[j][-1*(i+1)] == "1":
                one_count += 1
            else:
                zero_count += 1
        else:
            zero_count += 1
    ans += zero_count * one_count * (2**i)

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
nums = list(map(int, input().split()))
xors = [x[0]^x[1] for x in list(itertools.combinations(nums, 2))]
print(sum(xors)% (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    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]
            if ans>=10**9+7:
                ans=ans%(10**9+7)
    print(ans)
    

solve()

Submission status: Time Limit Exceeded

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

for i in range(N):
    tmp = format(As[i], 'b').zfill(60)
    for j in range(60):
        L[j] += int(tmp[j])

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[-(i + 1)]
    a = L[i] % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = list(map(int, inputs[1].split()))
MOD = 10 ** 9 + 7

bit = len(format(max(A), 'b'))
B = [(format(a, '0{}b'.format(bit)))[::-1] for a in A]
ans = 0
for i in range(bit):
    nb_1 = sum([int(b[i]) for b in B])
    ans += (nb_1 * (n - nb_1)) << i
    ans %= MOD
    
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
s = 0
for i in range(60):
  B = [((1<<i)&Ai)>0  for Ai in A]
  s += (1<<i) * B.count(True) * B.count(False)
print(s%MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.reverse()
sum = 0
check = []
num = []
sub = []
a = subb = 0
for i in range(1, N):
    sub_sum = 0
    if A[i] in check:
        a = check.index(A[i])
        for j in range(num[a], i):
            sub_sum += A[i] ^ A[j]
        subb = sub_sum + sub[a]
        sum += subb
        sub[a] = subb
    else:
        check.append(A[i])
        num.append(i)
        for j in range(i):
            sub_sum += A[i] ^ A[j]
        sum += sub_sum
        sub.append(sub_sum)
print(sum%1000000007)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
S = 0
j = 0
while A != [0 for i in range(N)]:
  m = 0
  n = 0
  for i in range(N):
    if A[i] % 2 == 1:
      m += 1
    else:
      n += 1
    A[i] //= 2
  S += (m * n) * (2 ** j)
  j += 1
S %= mod
print(S)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)] for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        if j - 1 >= ll:
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = deque(bin(a[i]))
    k.reverse()
    k.pop()
    k.pop()
    k = deque(map(int, k))
    for s in range(leng - len(k)):
        k.append(0)
    for j in range(leng):
        if k[j] == 1:
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = dd(int)
  zeros = dd(int)
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        ones[i] += 1
      else:
        zeros[i] += 1

  res = 0
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        res += zeros[i] * 2 ** i
        ones[i] -= 1
      else:
        res += ones[i] * 2 ** i
        zeros[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
l=[int(x) for x in input().rstrip().split()]
a=[]
 
for i in l:
    for j in l:
        if i<j:
            a.append([i,j])
 
A_1=0
A_2=0
SUM=0
ans=""
ANS=[]
for i in range(len(a)):
    A_1=format(a[i][0],'b')
    A_2=format(a[i][1],'b')
    if len(A_1)<len(A_2):
        A_1='0'*(len(A_2)-len(A_1))+A_1
    elif len(A_2)<len(A_1):
        A_2='0'*(len(A_1)-len(A_2))+A_2
 
 
    for j in range(len(A_1)):
        if A_1[j]==A_2[j]:
            ans=ans+'0'
        else:
            ans=ans+'1'
    ANS.append(ans)
    SUM+=int(ans,2)
    ans=''
SUM=SUM%(10**9+7)
print(SUM)

Submission status: Time Limit Exceeded

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

s = 0

for i in range(61):
    z=0
    o=0
    for n in l:
        if (n >> i)%2 == 0:
            z += 1
        else:
            o += 1
    s += (z*o)*((2**i)% (10**9+7))
    s = s % (10**9+7)

print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = [[0 for i in range(N)] for j in range(60)]
As = map(int, input().split())
mod = 1000000007
ans = 0
index = 0

for A in As:
    tmp = format(A, 'b').zfill(60)
    for j in range(60):
        L[j][index] = int(tmp[j])
    index += 1

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[-(i + 1)]
    a = sum(L[i]) % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for i in range(N):
	for j in range(i,N):
		count += A[i] ^ A[j]
print(count % (10 ** 9 +7))

Submission status: Time Limit Exceeded

Solution code:

mod = 10**9 + 7


def main():
    n = int(input())
    A = [int(a) for a in input().split()]
    ans = 0
    for k in range(60):
        a = 0
        for i in range(n):
            a += A[i] & 1
            A[i] >>= 1
        da = (1 << k) % mod
        da *= (n - a)*a
        da %= mod
        ans += da
        ans %= mod
    print(ans)


main()

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(61):
    zero = 0
    one = 0
    for a_ in a:
        if (a_ >> i) & 1:
            one += 1
        else:
            zero += 1
    ans += one * zero * pow(2, i, mod) % mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [0] * 60
  zeros = [0] * 60
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        ones[i] += 1
      else:
        zeros[i] += 1

  res = 0
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        res += zeros[i] * 2 ** i
        ones[i] -= 1
      else:
        res += ones[i] * 2 ** i
        zeros[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

s = 0

for i in range(61):
    z=0
    o=0
    for n in l:
        if (n >> i)%2 == 0:
            z += 1
        else:
            o += 1
    s += (z*o)*(2**i)
    s = s % (10**9+7)

print(s)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

ys = []
k = 0
for x in xs:
    y = list(reversed(bin(x)))[:-2]
    ys.append(y)
    k = max(k, len(y))
#print(ys, n)




def calc2(ans, i):
    def calc (x,y):
        if i < len(y) and y[i] == "1":
            return x+1
        else:
            return x
    x1 = 0
    x1 = reduce(calc,ys,0)
    #print(x1,x0)
    ans += x1 * (len(ys)-x1) * (2**(i))
    ans %= 10**9 + 7
    return ans
ans = reduce(calc2, range(k), 0)
print(ans)

Submission status: Time Limit Exceeded

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

arr = [0] * 60
for a in A:
    for i in range(60):
        if a&(1<<i):
            arr[i] += 1

ans = 0
for i,a in enumerate(arr):
    b = N-a
    ans += a*b * 2**i
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

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

ans = 0
for d in range(60):
    sumXOR = 0
    num0, num1 = 0, 0
    for A in As:
        if (A>>(59-d))&1:
            num1 += 1
        else:
            num0 += 1
#    print('d:', d, '/ num0:', num0, '/ num1:', num1)
    sumXOR += (num0 * num1) % MOD
    sumXOR %= MOD
    ans *= 2
    ans += sumXOR
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
mod = 10 ** 9 + 7
a = [list(bin(int(i))[2:].zfill(60)) for i in input().split()]
a = np.array(a)
x = a.T
x = x.tolist()
#print(x)
ans = 0
for i in range(60):
    y = x[i].count('0')
    z = x[i].count('1')
    tmp = ( (n * (n - 1) // 2) - (y * (y - 1) // 2) - (z * (z - 1) // 2) ) % mod
    tmp2 = 1
    for j in range(60 - i - 1):
        tmp2 = tmp2 * 2 % mod
    #print(tmp,tmp2)
    
    ans = (ans + tmp2 * tmp) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
lone = [0]*60
for i in range(n):
  m = l[i]
  for j in range(59,-1,-1):
    if m >= 2**j:
      m = m -2**j
      lone[j] += 1
ans = 0
const = 10**9+7
for i in range(60):
  ans += (2**i*lone[i]*(n-lone[i]))%const
print(ans%const)

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    mLEN = len(format(max(A),'b'))
    bA = [[0]*N for _ in range(mLEN)]

    for i in range(N):
        a = format(A[i],'b').zfill(mLEN)
        for k in range(mLEN):
            bA[k][i] = a[k]

    answer = 0
    for keta in range(mLEN):
        zero = bA[keta].count('0')
        one = N-zero



        answer += (zero*one)*pow(2,mLEN-1-keta,MOD)
    print(answer%MOD)
    return

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]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

ys = []
k = 0
for x in xs:
    y = list(reversed(bin(x)))[:-2]
    ys.append(y)
    k = max(k, len(y))
#print(ys, n)

def calc (x,y):
    if i < len(y) and y[i] == "1":
        return x+1
    else:
        return x

ans = 0
for i in range(k):
    x1 = 0
    x1 = reduce(calc,ys,0)
    #print(x1,x0)
    ans += x1 * (len(ys)-x1) * (2**(i))
    ans %= 10**9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [0] * 60
  zeros = [0] * 60
  for i in range(N):
    x = A[i]
    x = bin(x)[2:]
    x = x.zfill(60)
    for j in range(59, -1, -1):
      if x[j] == '0':
        zeros[j] += 1
      else:
        ones[j] += 1
  # print(ones)
  # print(zeros)

  res = 0
  for i in range(N):
    x = A[i]
    x = bin(x)[2:]
    x = x.zfill(60)
    for j in range(60):
      if x[-j - 1] == '0':
        res += ones[-j - 1] * 2 ** j
        res %= MOD
        zeros[-j - 1] -= 1
      else:
        res += zeros[-j - 1] * 2 ** j
        res %= MOD
        ones[-j - 1] -= 1
  print(res)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import collections
d = collections.Counter()
MOD = int(1e9 + 7)

max_i = 0
for a in map(int, input().split()):
  inv_bin = bin(a)[2:][::-1]
  for i, b in enumerate(inv_bin):
    if (b == '1'):
      d[i] += 1
  max_i = max(i, max_i)

ans = 0
for k, v in d.items():
  ans += (N - v) * v * (2 ** k) 
  ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

ys = []
n = 0
for x in xs:
    y = list(reversed(bin(x)))[:-2]
    ys.append(y)
    n = max(n, len(y))
#print(ys, n)

def calc (x,y):
    if i < len(y) and y[i] == "1":
        return x+1
    else:
        return x

ans = 0
for i in range(n):
    x1 = 0
    x1 = reduce(calc,ys,0)
    #print(x1,x0)
    ans += x1 * (len(ys)-x1) * (2**(i))
    ans %= 10**9 + 7
print(ans)

Submission status: Time Limit Exceeded

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

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, atan, degrees
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
from bisect import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	A = LIST()

	upper_len = len("{:b}".format(max(A)))

	cnt = [defaultdict(int) for _ in range(upper_len)]
	for i in range(N):
		num = "{:b}".format(A[i]).zfill(upper_len)
		for j in range(len(num)):
			cnt[upper_len-j-1][num[j]] += 1

	ans = 0
	for i in range(upper_len):
		ans = (ans + (1<<i)*cnt[i]["0"]*cnt[i]["1"])%mod
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*l, = map(int,input().split())
lone = [0]*60
for i in range(n):
  m = l[i]
  for j in range(59,-1,-1):
    if m >= 2**j:
      m = m -2**j
      lone[j] += 1
ans = 0
for i in range(len(lone)):
  ans += 2**i*lone[i]*(n-lone[i])
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = [[0 for i in range(N)] for j in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0
for i in range(N):
    tmp = format(As[i], 'b').zfill(60)
    for j in range(60):
        L[j][i] = (int(tmp[j]))

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[-(i+1)]
    a = sum(L[i]) % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % 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, atan, degrees
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
from bisect import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

A.sort()
A_acc = list(accumulate(A))
upper_len = len("{:b}".format(max(A)))

upper = 10**6  # 必要そうな階乗の限界を入れる
factorial = [1]
for i in range(1, upper):
    factorial.append(factorial[i-1] * i % mod)

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod

def C(n, r):
    return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod
x_inv = [0] * (upper)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(upper-2, -1, -1):
    x_inv[i] = x_inv[i+1] * (i+1) % mod

cnt = [defaultdict(int) for _ in range(upper_len)]
for i in range(N):
	num = "{:b}".format(A[i]).zfill(upper_len)
	for j in range(len(num)):
		cnt[upper_len-j-1][num[j]] += 1

ans = 0
for i in range(upper_len):
	ans = (ans + (2**i)*cnt[i]["0"]*cnt[i]["1"])%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
ones = [0] * 60
zeros = [0] * 60
for i in range(N):
  x = A[i]
  x = bin(x)[2:]
  x = x.zfill(60)
  for j in range(59, -1, -1):
    if x[j] == '0':
      zeros[j] += 1
    else:
      ones[j] += 1
# print(ones)
# print(zeros)

res = 0
for i in range(N):
  x = A[i]
  x = bin(x)[2:]
  x = x.zfill(60)
  for j in range(60):
    if x[-j - 1] == '0':
      res += ones[-j - 1] * 2 ** j
      res %= MOD
      zeros[-j - 1] -= 1
    else:
      res += zeros[-j - 1] * 2 ** j
      res %= MOD
      ones[-j - 1] -= 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = tuple(map(int,input().split()))
b = 0
num = 1000000007
A_1 = A[:-1]
A_2 = A[1:]
for i in A_1:
    for j in A_2:
        b += i ^ j
    A_2 = A_2[1:]
    #print(A_2)
print(b%num)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
S=0
for i in range(N-1):
  x=format(A[i], 'b')
  x=x.zfill(60) 
  for j in range(i+1,N):
    y=format(A[j], 'b')
    y=y.zfill(60)
    for k in range(60):
      if x[k] !=  y[k]:
        S=(S+ 2**(59-k))%(10**9+7)
print(S)

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint

mod = 10**9 + 7

def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2) % mod
    else:
        return (x * pow_r(x ** 2, (n - 1) // 2)) % mod


def solve(n, a):

    zero_count = [0] * 60
    for a_i in a:
        binary = format(a_i, '060b')

        for j, b_j in enumerate(binary):
            zero_count[j] += int(b_j)

    ans = 0
    for i, count in enumerate(zero_count[::-1]):
        # ans += (2**i) * (count * (n - count)) 
        ans += pow_r(2, i) * (count % mod) * ((n - count) % mod) 
        ans %= mod
    print(ans)

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    a = map(int, sys.stdin.readline().strip().split(" "))
    
    solve(n, a)

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = 10**9+7
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
C = [0 for i in range(60)]
for i in A:
    for l in range(60):
        if ((i >> l) & 1) == 1:
            C[l] += 1
for i in range(60):
    t = C[i]
    ans = (ans + t*(N-t)*(2**i)) % mod
print(ans)

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * (n_1 % MOD)) % MOD
        else:
            ret += (((2**i) % MOD) * ((n_1_max - n_1) % MOD)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  L[i]='{0:062d}'.format(int(format(L[i],"b")))
d=0
for i in range(62):  
  c=0
  for j in range(N):    
    c+=int(L[j][-i-1])    
  d+=(c*(N-c))*2**i  
print(d%(10**9+7))

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * (n_1 % MOD)) % MOD
        else:
            ret += (((2**i) % MOD) * ((n_1_max - n_1) % MOD)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for i in range(N - 2, -1, -1):
    a = A[i]
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = []
x = 0
y = 1
time = 0
for i in range(n):
  n -= 1
  time += n
for i in range(time):
  l.append(a[x] ^ a[y])
  y += 1
  if y == len(a):
    x += 1
    y = x+1
total = sum(l)
print(total % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = 10**9+7
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
for i in A:
    B.append(list(bin(i)[2:]))
C = [0 for i in range(60)]
for i in B:
    for l in range(len(i)):
        if i[-(l+1)] == '1':
            C[l] += 1
for i in range(60):
    t = C[i]
    ans = (ans + t*(N-t)*(2**i)) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)]for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        if j - 1 >= ll:
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = bin(a[i])
    k = list(map(int, k[:1:-1]))
    k = k + [0 for i in range(leng - len(k))]
    for j in range(leng):
        if k[j] == 1:
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=0
for i in range(n):
    for j in range(i+1,n):
        x=[]
        y=[]
        k=0
        if a[i]>a[j]:
            m=a[i]
            s1=a[j]
        else:
            m=a[j]
            s1=a[i]
        while s1>0:
            if m%2!=s1%2:
                s+=2**k
            m=m//2
            s1=s1//2
            k+=1
        s+=m*(2**k)
print(s%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(sys.stdin.readline())

A=[int(i) for i in input().split()]
sum=0
for i in range(N-1):
  for j in range(i+1,N):
    sum+=A[i]^A[j]
print(sum%1000000007)

Submission status: Time Limit Exceeded

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


def xor(x, y):
    X = bin(max(x, y))
    Y = bin(min(x, y))
    w = bin(int(X, 2) ^ int(Y, 2))

    return int(w, 2)


for i in itertools.combinations(a, 2):
    Ans = Ans + xor(i[0], i[1])

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):
    ni = A[i]
    # print(ni)
    for j in range(i + 1, N):
        nj = A[j]

        # print("\t"+str(nj))
        # print(bin(ni ^ nj))
        ans += int(bin(ni ^ nj)[2:], 2) % (10**9+7)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, (input().split())))
result = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        resultbin = bin(a[i] ^ a[j])
        result += int(resultbin, 2)
print(result % ((10 ** 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  L[i]='{0:070d}'.format(int(format(L[i],"b")))

d=0
for i in range(63):
  
  c=0
  for j in range(N):
    
    c+=int(L[j][-i-1])
    
  d+=(c*(N-c))*2**i
  
print(d%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
def pairORSum(arr, n) : 
    ans = 0     # Initialize result 
  
    # Consider all pairs (arr[i], arr[j)  
    # such that i < j 
    for i in range(0, n) : 
          
        for j in range(i + 1, n) : 
              
            ans = ans + (arr[i] ^ arr[j]) 
              
    return ans 
      
  
# Driver Code 
n=int(input())
arr=list(map(int,input().split()))
print(pairORSum(arr, n)%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = [[] for i in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0
for i in range(N):
    tmp = format(As[i], 'b').zfill(60)
    for j in range(60):
        L[j].append(int(tmp[j]))

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[-(i+1)]
    a = sum(L[i]) % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)