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:
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]


length = int(fetch_one_line())
nums = fetch_int_input()

bit_nums = [bin(i)[2:] for i in nums]
max_length = max([len(i) for i in bit_nums])

bit_nums = [list(i.zfill(max_length)) for i in bit_nums]
bit_nums = list(zip(*bit_nums))
sum_ones = [lst.count("1") for lst in bit_nums]
sum_zeros = [length - o for o in sum_ones]
multiples = [i * j for i, j in zip(sum_ones, sum_zeros)]

result = sum([pow(2, i) * m for i, m in enumerate(reversed(multiples))])
print(result % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
sum = 0
for s in range(n-1):
  for t in range(n-s-1):
    tmp = a[s] ^ a[t+s+1]
    sum += tmp
ans = sum % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
##D
from itertools import combinations
N = int(input())
 
A_list = list(map(int,input().split()))
ans = 0
 
for i in combinations(A_list, 2):
    ans += i[0]^i[1]
    
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    arr = list(map(int, input().split()))
    vec = [0]* 60
    mod = 10**9 + 7
    fac = [(1<<i)%mod for i in range(60)]
    # print(fac)
    ans, cnt = 0, 0
    for val in reversed(arr):
        for d in range(60):
            if ((val >> d) & 1) == 0:
                ans += fac[d] * vec[d]
            else:
                ans += fac[d] * (cnt-vec[d])
            ans %= mod
        for d in range(60):
            if ((val >> d) & 1) == 1:
                vec[d] += 1
        cnt += 1
        # print(vec)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    sum = 0

    for i in range(60):
        count_1 = 0
        for a in a_list:
            bin_a = format(a, "b").zfill(60)
            if bin_a[59-i] == "1":
                count_1 += 1

        sum += 2 ** i * count_1 * (N - count_1)

    print(sum % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
amax=max(a)
m=len( bin(amax)[2:] )
bin_a = [bin(aa)[2:].zfill(m) for aa in a]

ans=0
mod=10**9+7
for i in range(m):
    sum0 = sum( bi[-1-i]=="0" for bi in bin_a )
    sum1 = sum( bi[-1-i]=="1" for bi in bin_a )
    ans += sum0*sum1*2**i % mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

divider = 10**9+7

ans = 0
for shift in range(0, 60+1):
    one_num = 0
    for a in A:
        one_num += (a>>shift) & 1
    ans += (2**shift)*one_num*(N-one_num)
print(ans%divider)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
x=1
for i in range(60):
  z=o=0
  for j in range(n):
    if a[j]%2:o+=1
    else:z+=1
    a[j]//=2
  ans+=(x*o*z)%mod
  ans%=mod
  x=(x*2)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[61*[0]for _ in range(n)]
c=[0]*61
for i in range(n):
  s=bin(a[i])[2:].zfill(61)
  for j in range(61):
    if s[-j-1]=="1":
      c[j]+=1
      b[i][j]=1
ans=0
mod=10**9+7
mod*=2
for i in range(n):
  x=1
  for j in range(61):
    if b[i][j]==1:s=n-c[j]
    else:s=c[j]
    ans+=s*x
    x=(x*2)%mod
    ans%=mod
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[61*[0]for _ in range(n)]
c=[0]*61
for i in range(n):
  s=bin(a[i])[2:].zfill(61)
  for j in range(61):
    if s[-j-1]=="1":
      c[j]+=1
      b[i][j]=1
ans=0
mod=10**9+7
mod*=2
for i in range(n):
  x=1
  for j in range(61):
    if b[i][j]==1:s=n-c[j]
    else:s=c[j]
    ans+=s*x
    x=(x*2)%mod
    ans%=mod
print(ans//2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
n = int(input())
array = np.array([list(map(int, format(num, "060b")))[::-1] for num in map(int, input().split())], dtype="int64")
sum_ = 0
for idx, column in enumerate(array.T):
    n_ones = column.sum()
    sum_ += ((n_ones * (n - n_ones)) % MOD) * ((2 ** idx) % MOD) % MOD
    sum_ %= MOD
print(sum_)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

maxA = max(A)
K = len(str(bin(maxA)))-2
ans = 0
for k in range(K):
    N1 = 0
    bk = 1<<k
    for i in range(0,N):
#        N1 += ( (A[i] >> k) & 1)
        N1 += (A[i] & bk)
    N1 //= bk
    N0 = N-N1
    ans += (((1<<k)%M) *N0 *N1) % M

ans %= M    
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
ct=0
while ma>0:
  ma//=2
  ct+=1
lis=[0 for _ in range(ct)]

for i in range(n):
  digit=ct
  while digit>0:
    if a[i] >= 2**(digit-1):
      a[i]-=2**(digit-1)
      lis[digit-1]+=1
    digit-=1

lis2=[n-x for x in lis]
ans=0
for i in range(ct):
  ans+=lis[i]*lis2[i]*2**i
  ans%=10**9+7
print(ans)

Submission status: Time Limit Exceeded

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

maxA = max(A)
K = len(str(bin(maxA)))-2
ans = 0
for k in range(K):
    N1 = 0
    for i in range(0,N):
        N1 += ( (A[i] >> k) & 1)
    N0 = N-N1
    ans += (((1<<k)%M) *N0 *N1) % M

ans %= M    
print(int(ans))

Submission status: Time Limit Exceeded

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

ans = 0
i = 0

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

res = 0

for k in range(60):
    cnt = [0, 0]
    for i in range(N):
        cnt[(A[i] >> k) & 1] += 1
    res = (res + cnt[0] * cnt[1] * pow(2, k)) % MOD

print(res)

Submission status: Time Limit Exceeded

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

ans=0

for i in range(60):
    cnt=len([i for i in range(n) if A[i]&1])
    ans +=2**i*cnt*(n-cnt)
    A=[A[i]>>1 for i in range(n)]

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mod=10**9+7;ans=0
a=list(map(int,input().split()))
for i in range(61):
  checkbit=1 << i
  cnt=0
  for j in a:
    cnt+= (j & checkbit) // checkbit
  ans+=checkbit*cnt*(n-cnt)
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
s=[0]*61
for i in range(n):
  c=format(a[i], 'b')
  L=len(c)
  for j in range(L)[::-1]:
    s[L-j-1]+=int(c[j])
ans=0
for i in range(61):
  ans+=2**(i)*(s[i])*(n-s[i])
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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

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):
    bit = 1 << i
    count = 0
    for j in range(N):
        if bit & A[j]:
            count += 1
    ans += 2**i * count * (N-count) % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

ans = 0
for i in range(60):
    num1 = len([1 for j in range(N) if A[j] & 2**i])
    num0 = N - num1

    ans += ((num1 * num0) * (2 ** i))

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

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    vA = list(map(int, input().split()))
    MOD = 10**9 + 7
    BMAX = 61

    vC = [0,]*BMAX
    for a in vA:
        d = 0
        while a:
            vC[d] += a&1
            d += 1
            a >>= 1
    res = 0
    for i,c in enumerate(vC):
        x = pow(2,i) * c * (N-c) % MOD
        res = (res + x) % MOD
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = 0
    for j in range(n):
        c += a[j] & m
    c //= m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = 0
    for j in range(n):
        c += (a[j] & m)//m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a = np.array([int(x) for x in input().split()])
inf = 10**9+7

ans = 0
p = 1
for i in range(61):
    a, b = a//2, a%2
    key = int(sum(b))
    ans += p*(n-key)*key
    ans = ans%inf
    p *= 2
    p %= inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = 60
MOD = 10**9 + 7
n = int(input())
c0 = [0 for _ in range(N)]
c1 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) == 0:
            c0[j] += 1
        else:
            c1[j] += 1

ans = 0
for i in range(n-1):
    for j in range(N):
        if a[i] & (1 << j) == 0:
            c0[j] -=1
        else:
            c1[j] -=1
    for j in range(N):
        if a[i] & (1 << j) == 0:
            ans += (1<<j) * c1[j]
        else:
            ans += (1<<j) * c0[j]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
N = 60
MOD = 10**9 + 7
n = int(input())
l = [[] for _ in range(n)]
# c1 = [0 for _ in range(N)]
c0 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            # c1[j] += 1
            l[i].append(True)
        else:
            c0[j] += 1
            l[i].append(False)

ans = 0
for i in range(n-1):
    for j in range(N):
        if not l[i][j]:
            c0[j] -=1
        # else:
        #     c0[j] -=1
    for j in range(N):
        if l[i][j]:
            ans += (1<<j) * c0[j]
        else:
            ans += (1<<j) * (n-i-1-c0[j])
            #ans += (1<<j) * c1[j]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
N = 60
MOD = 10**9 + 7
n = int(input())
l = [[] for _ in range(n)]
c1 = [0 for _ in range(N)]
c0 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            c1[j] += 1
            l[i].append(True)
        else:
            c0[j] += 1
            l[i].append(False)

ans = 0
for i in range(n-1):
    for j in range(N):
        if l[i][j]:
            c1[j] -=1
        else:
            c0[j] -=1
    for j in range(N):
        if l[i][j]:
            ans += (1<<j) * c0[j]
        else:
            ans += (1<<j) * c1[j]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
lines = sys.stdin.readlines()
n = int(lines[0])
arr = list(map(int, lines[1].split(' ')))

maxi = 62
mod = int(1e9) + 7
ones = [0 for _ in range(maxi)]
for num in arr:
    x = bin(num)[2:]
    # print(x)
    for idx, val in enumerate(reversed(x)):
        ones[idx] += int(val)

ans = 0
for idx, val in enumerate(ones):
    ans += ((pow(2, idx) % mod) * (((n - val)%mod) * (val%mod))) % mod

    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

maxi = 62
mod = int(1e9) + 7
ones = [0 for _ in range(maxi)]
for num in arr:
    x = bin(num)[2:]
    # print(x)
    for idx, val in enumerate(reversed(x)):
        ones[idx] += int(val)

ans = 0
for idx, val in enumerate(ones):
    ans += ((pow(2, idx) % mod) * (((n - val)%mod) * (val%mod))) % mod

    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int, readline().split()))
B1 = [0 for i in range(60)]
for x in A:
    bA = format(x,"b").zfill(60)
    for i in range(60):
        if bA[i] == "1":
            B1[i] += 1
ans = 0
for i,x in enumerate(B1):
    ans = (ans + 2**(59-i)*x*(N-x)) % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
a = [ int(i) for i in input().split() ]
ans = 0
for i in range(60):
    zero = 0
    one = 0
    if (a[n-1] & (1<<i)) == 0:
        zero += 1
    else:
        one += 1

    for j in range(n-2,-1,-1):
        if (a[j] & (1<<i)) == 0:
            ans += one * (1<<i)
            ans %= mod
            zero += 1
        else:
            ans += zero * (1<<i)
            ans %= mod
            one += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    MAX = 10**9+7

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

    dic = {key:0 for key in range(61)}
    for i in a:
        for ind, j in enumerate(bin(i)[:1:-1]):
            dic[ind] += int(j)

    ans = 0
    bit = 1
    for i in range(61):
        ans += bit * dic[i] * (n-dic[i])
        bit *= 2
    print(ans%MAX)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split(' ')))
B1 = defaultdict(int)
B0 = defaultdict(int)
for x in A:
    bA = format(x,"b").zfill(60)
    for i in range(60):
        if bA[i] == "1":
            B1[i] += 1
        elif bA[i] == "0":
            B0[i] += 1
ans = 0
for i in range(60):
    ans = (ans + 2**(59-i)*B1[i]*B0[i]) % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split(' ')))
B1 = [0 for i in range(60)]
B0 = [0 for i in range(60)]
for x in A:
    bA = format(x,"b").zfill(60)
    for i in range(60):
        if bA[i] == "1":
            B1[i] += 1
        elif bA[i] == "0":
            B0[i] += 1
ans = 0
for i in range(60):
    ans = (ans + 2**(59-i)*B1[i]*B0[i]) % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    # input
    import sys
    input = sys.stdin.readline
    MAX = 10**9+7

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

    li = [0]*61
    for i in a:
        for ind, j in enumerate(bin(i)[:1:-1]):
            li[ind] += int(j)

    ans = 0
    bit = 1
    for i in li:
        ans += bit * i * (n-i)
        bit *= 2
    print(ans%MAX)

    # calc



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

INF = 10 ** 9 + 7
N = int(input())
a = list(map(int, input().split()))
cnt = [0] * 60
for i in a:
    for j in range(60):
        tmp = i >> j
        if tmp != 0:
            cnt[j] += tmp % 2
        else:
            break
ans = 0
for b in range(60):
    ans += cnt[b] * (N - cnt[b]) << b
    ans %= INF
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

max_A = max(A)
j = 0
while max_A >> j > 0:
    j += 1
max_j = j

ans = 0
MOD = 10 ** 9 + 7
for j in range(max_j):
    c = [0] * 2
    for i in range(N):
        c[A[i] >> j & 1] += 1
    ans += c[0] * c[1] * (1 << j)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

INF = 10 ** 9 + 7
N = int(input())
a = list(map(int, input().split()))
cnt = [0] * 60
for i in a:
    for j in range(60):
        cnt[j] += (i >> j) % 2
ans = 0
for b in range(60):
    ans += cnt[b] * (N - cnt[b]) << b
    ans %= INF
print(ans)

Submission status: Time Limit Exceeded

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

    r = list(range(N - 2, -1, -1))
    result = 0
    for b in range(60):
        t = 0
        bs = (A[N - 1] >> b) & 1
        for i in r:
            if (A[i] >> b) & 1 == 0:
                t += bs
            else:
                t += (N - (i + 1)) - bs
                bs += 1
        result = (result + t * (1 << b)) % 1000000007
    print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
digit = [0] * 60
for a in A:
  binary = bin(a)[-1:1:-1]
  for j in range(len(binary)):
    digit[j] += int(binary[j])
ans = 0
mod = 10**9+7
for i in range(60):
  ans += digit[i] * (N - digit[i]) * pow(2, i, mod)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
mod = 10**9 + 7
ans = 0
for b in range(60):
    M = sum((a >> b) & 1 for a in A)
    ans += 2**b * M * (N - M)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

    r = list(range(N - 2, -1, -1))
    result = 0
    for b in range(60):
        t = 0
        bs = (A[N - 1] >> b) & 1
        for i in r:
            a = (A[i] >> b) & 1
            if a == 0:
                t += bs
            else:
                t += (N - (i + 1)) - bs
            bs += a
        result = (result + t * (1 << b)) % 1000000007
    print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([1, 2, 3]), 6)

    def test_2(self):
        self.assertEqual(think([3, 1, 4, 1, 5, 9, 2, 6, 5, 3]), 237)

    def test_3(self):
        self.assertEqual(think([3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]), 103715602)

    def test_4(self):
        self.assertEqual(num_of_bits(0), 0)

    def test_5(self):
        self.assertEqual(num_of_bits(1), 1)

    def test_6(self):
        self.assertEqual(num_of_bits(4), 3)

    def test_7(self):
        self.assertEqual(num_of_bits(7), 3)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n)


def read_float(n):
    return read_type(float, n)


def read_type(t, n):
    return list(map(lambda x: t(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(data):
    mode = 10 ** 9 + 7
    num_of_digits = num_of_bits(max(data))

    result = 0
    for i in range(num_of_digits):
        num_of_zero = 0
        num_of_one = 0
        for d in data:
            if is_flag_set(d, i):
                num_of_one += 1
            else:
                num_of_zero += 1
        result += num_of_zero * num_of_one * (1 << i)
        result %= mode
    # return naive_think(data)
    return result


def is_flag_set(d, bits):
    return (d >> bits) % 2 == 1


def naive_think(data):
    mode = 10 ** 9 + 7
    result = 0
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            result += data[i] ^ data[j]
            result %= mode
    return result


def write(result):
    print(result)


def num_of_bits(n):
    count = 0
    while n > 0:
        n //= 2
        count += 1
    return count


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
mod = 10**9 + 7
B0 = [0] * 60
B1 = [0] * 60
a = A.pop()
for b in range(60):
    if (a >> b) & 1:
        B1[b] += 1
    else:
        B0[b] += 1
ans = 0
for a in A:
    for b in range(60):
        if (a >> b) & 1:
            ans += (1 << b) * B0[b]
            B1[b] += 1
        else:
            ans += (1 << b) * B1[b]
            B0[b] += 1
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

lst = [0] * 65
for a in A:
    tmp = a
    for i in range(61):
        lst[i] += tmp % 2
        tmp //= 2
        if tmp == 0:
            break

calc = [1]
for i in range(65):
    calc.append((calc[-1] * 2) % MOD)

ans = 0
for a in A:
    tmp = a
    for i in range(61):
        n = tmp % 2
        tmp //= 2
        if n == 1:
            ans += (calc[i] * (N - lst[i])) % MOD
        else:
            ans += (calc[i] * lst[i]) % MOD
    ans %= MOD

def modinv(a, m): #mod m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

# print (ans)
ans *= modinv(2, MOD)
print (ans % MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

lst = [0] * 65
for a in A:
    tmp = a
    for i in range(61):
        lst[i] += tmp % 2
        tmp //= 2
        if tmp == 0:
            break

calc = [1]
for i in range(65):
    calc.append(calc[-1] * 2)

ans = 0
for a in A:
    tmp = a
    for i in range(61):
        n = tmp % 2
        tmp //= 2
        if n == 1:
            ans += calc[i] * (N - lst[i])
        else:
            ans += calc[i] * lst[i]
    ans %= MOD

def modinv(a, m): #mod m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

# print (ans)
ans *= modinv(2, MOD)
print (ans % MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

lst = [0] * 65
for a in A:
    tmp = a
    for i in range(61):
        lst[i] += tmp % 2
        tmp //= 2
        if tmp == 0:
            break

calc = [1]
for i in range(65):
    calc.append(calc[-1] * 2)

ans = 0
for a in A:
    tmp = a
    for i in range(61):
        n = tmp % 2
        tmp //= 2
        if n == 1:
            ans += calc[i] * (N - lst[i])
        else:
            ans += calc[i] * lst[i]

print (ans // 2 % MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

lst = [0] * 65
for a in A:
    tmp = a
    for i in range(61):
        lst[i] += tmp % 2
        tmp //= 2
        if tmp == 0:
            break

ans = 0
for a in A:
    tmp = a
    for i in range(61):
        n = tmp % 2
        tmp //= 2
        if n == 1:
            ans += pow(2, i) * (N - lst[i])
        else:
            ans += pow(2, i) * lst[i]

print (ans // 2 % MOD)

Submission status: Time Limit Exceeded

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

ans = 0
one = np.zeros(60, dtype=int)

for i in range(n):
    b = bin(a[i])[2:].zfill(60)

    for j in range(60):
        if b[j] == "1":
            ans += pow(2, 60-j-1, mod)*(i-one[j])
        else:
            ans += pow(2, 60-j-1, mod) * one[j]
        ans %= mod

    one += np.array(list(map(int, list(b))))

print(ans)

Submission status: Time Limit Exceeded

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

    result = 0
    bs = [0] * N
    for b in range(60):
        a = [(e >> b) & 1 for e in A]
        bs[N - 1] = a[N - 1]
        t = bs[N - 1]
        for i in range(N - 2, -1, -1):
            t += a[i]
            bs[i] = t

        t = 0
        for i in range(N - 1):
            if a[i] == 0:
                t += bs[i + 1]
            else:
                t += (N - (i + 1)) - bs[i + 1]
        result = (result + t * (1 << b)) % 1000000007
    print(result)
main()

Submission status: Time Limit Exceeded

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

DIGIT = 61
MOD = (10**9) +7
count = 0
for i in range(DIGIT):
    one_count = 0
    for num in a_list:
        if (num >> i) % 2 == 1:
            one_count += 1
    comb_1_1 = one_count * (n - one_count)
    count += comb_1_1 * (2**i)
    count = count % MOD
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ar = list(map(int, input().split()))
res = 0
mod = 10 ** 9 + 7
for i in range(60):
    zero = 0
    one = 0
    for j in range(len(ar)):
        if ar[j] % 2 == 0:
            zero += 1
        else:
            one += 1
        ar[j] = ar[j] // 2
    curr = (zero * one * (1 << i)) % mod
    res = (res + curr) % mod
print(res)

Submission status: Time Limit Exceeded

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

result = 0
for b in range(60):
  a = [(e >> b) & 1 for e in A]
  bs = [0] * N
  bs[N - 1] = a[N - 1]
  for i in range(N - 2, -1, -1):
    bs[i] = bs[i + 1] + a[i]

  t = 0
  for i in range(N - 1):
    if a[i] == 0:
      t += bs[i + 1]
    else:
      t += (N - (i + 1)) - bs[i + 1]
  result = (result + t * (1 << b)) % 1000000007
print(result)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input().split()
A = [int(a) for a in A]
max_A = max(A)
max_keta = len((bin(max_A))[2:])
A = [bin(a)[2:] for a in A]
for i in range(N):
    s = A[i]
    while(len(s)<max_keta):
        s = "0"+s
    A[i] = s
zero = [0 for i in range(max_keta)]
one = [0 for i in range(max_keta)]

for i in range(N):
    for j in range(max_keta):
        if(A[i][j]=="0"):
            zero[max_keta-1-j] += 1
        else:
            one[max_keta-1-j] += 1


sum_ = 0
for i in range(max_keta):
    sum_ += one[i]*zero[i]*(2**(i))
    sum_ = sum_%1000000007
    
print(sum_)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(60):
  num_one = len([1 for x in A if x & (1 << i)])
  ans = ans + (1 << i) * num_one * (N - num_one)
print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(60):
  num_one = len([1 for x in A if x & (1 << i)])
  ans = (ans + (1 << i) * num_one * (N - num_one)) % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def d():
  N = int(input())
  A = list(map(int,input().split()))
  
  ans = 0
  for i in range(60):
    num_one = sum([1 for x in range(N) if A[x] & (1 << i) != 0])
    ans = (ans + (1 << i) * num_one * (N - num_one)) % 1000000007
  print(ans)
        
d()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
  
keta=[0]*60
for i in range(n):
  tar=A[i]
  ind=0
  while tar>0:
    if tar&1==1:
      keta[ind]+=1
    tar>>=1
    ind+=1

pair=[0]*60
for i in range(len(keta)):
  pair[i]=keta[i]*(len(A)-keta[i])
  
ans=0
mul=1
DIV=10**9+7
for i in range(len(pair)):
  ans+=pair[i]*mul
  ans%=DIV
  mul*=2
print(ans)

Submission status: Time Limit Exceeded

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

  num_ones = [0]*60
  powers_of_two = [1]
  for i in range(1,60):
    powers_of_two.append((powers_of_two[-1] << 1) % 1000000007)
  
  ans = 0
  for i in range(N-1,-1,-1):
    for j in range(60):
      if A[i] & 1 == 0:
        ans = (ans + powers_of_two[j] * num_ones[j]) % 1000000007
      else:
        ans = (ans + powers_of_two[j] * (N - i - 1 - num_ones[j])) % 1000000007
        num_ones[j] += 1
      A[i] >>= 1
  print(ans)
        
d()

Submission status: Time Limit Exceeded

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

num_ones = [0]*60
powers_of_two = [pow(2,x,1000000007) for x in range(60)]

ans = 0
for i in range(N-1,-1,-1):
  for j in range(60):
    if A[i] & 1:
      ans = (ans + powers_of_two[j] * (N - i - 1 - num_ones[j])) % 1000000007
      num_ones[j] += 1
    else:
      ans = (ans + powers_of_two[j] * num_ones[j]) % 1000000007
    A[i] >>= 1
print(ans)

Submission status: Time Limit Exceeded

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

  num_ones = [0 for x in range(60)]
  powers_of_two = [1]
  for i in range(1,60):
    powers_of_two.append((powers_of_two[-1] * 2) % 1000000007)
  
  ans = 0
  for i in range(N-1,-1,-1):
    for j in range(60):
      if A[i] & 1 == 0:
        ans = (ans + powers_of_two[j] * num_ones[j]) % 1000000007
      else:
        ans = (ans + powers_of_two[j] * (N - i - 1 - num_ones[j])) % 1000000007
        num_ones[j] += 1
      A[i] >>= 1
  print(ans)
        
d()

Submission status: Time Limit Exceeded

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

MOD = 1000000007
ans = 0
for i in range(0, N-1):
    for j in range(i+1, N):
        ans = (ans + (A[i] ^ A[j])) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
l = len(bin(a_max)) - 2
bits = np.zeros((l,2))
for num in a:
    for i, bit in enumerate(format(num, 'b').zfill(l)):
        if bit == '0':
            bits[i,0] += 1
        else:
            bits[i,1] += 1

sumation = 0
div = (10**9+7)
for i in range(l):
    sumation += (bits[i,0]) * (bits[i, 1]) * (2**(l-i-1) % div)
print(int(sumation % (10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
binA=[None]*n
for i in range(n):
  binA[i]=bin(A[i])[2:]
  
keta=[0]*60
for i in range(n):
  tar=binA[i]
  for j in range(len(tar)-1,-1,-1):
    if tar[j]=="1":
      keta[len(tar)-1-j]+=1

pair=[0]*60
for i in range(len(keta)):
  pair[i]=keta[i]*(len(A)-keta[i])
  
ans=0
mul=1
DIV=10**9+7
for i in range(len(pair)):
  ans+=pair[i]*mul
  ans%=DIV
  mul*=2
print(ans)