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:
#!/usr/bin/env python3

MOD = 1000000007
n, *a = map(int, open(0).read().split())

ans = 0
w = 1
for i in range(61):
    zero = one = 0
    for j in range(n):
        if a[j]&1: one += 1
        else: zero += 1
        a[j] >>= 1;
    ans = (ans + w * zero * one)% MOD
    w = w * 2 % MOD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 1000000007
n, *a = map(int, open(0).read().split())

ans = 0
w = 1
for i in range(61):
    zero = one = 0
    for x in a:
        if (x>>i)&1: one += 1
        else: zero += 1
    ans = (ans + w * zero * one % MOD) % MOD
    w = w * 2 % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
MOD = 1000000007
n, *a = map(int, open(0).read().split())
ans = 0
for i in range(61):
    zero = one = 0
    for x in a:
        if (x>>i)&1: one += 1
        else: zero += 1
    ans += pow(2, i, MOD) * zero * one % MOD
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
 
ans = 0
twopow = 1
for n in range(60):
    one = 0
    for i in range(N):
        one += A[i] & 1
        A[i] >>= 1
    zero = N - one
    ans = (ans + (one * zero) * twopow) % MOD
    twopow = twopow << 1 % MOD

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
twopow = 1
for n in range(60):
    one = sum( ((Ai >> n) & 1) for Ai in A )
    zero = N - one
    ans = (ans + (one * zero) * twopow) % MOD
    twopow = twopow << 1 % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
P=10**9+7
count=[0]*60    #マジックナンバー

def culc(a):
    global count

    i=0
    while a>0:
        if a&1==1:
            count[i]+=1
        a=a>>1
        i+=1

def res():
    global N
    global count

    res=0
    for i in range(len(count)):
        res=(res+(2**i)*count[i]*(N-count[i]))%P

    return res

for index in range(N):
    culc(A[index])

ans=res()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())
 
def log(*args):
    print("DEBUG:", *args, file=sys.stderr)
 
def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]
 
def inv(x, MOD):
    return pow(x, MOD-2, MOD)
 
MOD = 10**9+7
 
n,*A = get_all_int()
 
pow2 = [1] * 61
for i in range(1,61):
    pow2[i] = pow2[i-1] * 2
 
# ビットごとの出現回数 2**i
bits = [0] * 60
 
for a in A:
    for i in range(60):
        if pow2[i] & a != 0:
            bits[i] += 1
 
ans = 0
 
for a in A:
    for i in range(60):
        ans += pow(2,i,MOD) * abs(bits[i] - (1 if pow2[i] & a != 0 else 0) *n)
 
print(ans*inv(2,MOD) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())
 
def log(*args):
    print("DEBUG:", *args, file=sys.stderr)
 
def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]
 
def inv(x, MOD):
    return pow(x, MOD-2, MOD)
 
MOD = 10**9+7
 
debug = False
 
if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()
 
 
pow2 = [1] * 61
for i in range(1,61):
    pow2[i] = pow2[i-1] * 2

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if pow2[i] & a != 0:
            bits[i] += 1

 
# log("bits:", bits)
 
ans = 0
 
for a in A:
    # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]
 
    for i in range(60):
        ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)
 
    # a_dash = list(map(lambda a: a*(n-1), a_bits))
 
    # log("a_dash", a_dash)
 
    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )
 
    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )
 
    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)
 
print(ans//2 % MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 多分TLE
import numpy as np
from collections import deque
mod = 10**9 + 7
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]) % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

debug = False

if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()




# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

    for i in range(60):
        ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

    # a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans//2 % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

debug = False

if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()




# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

    for i in range(60):
        ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

    # a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans//2 % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

debug = False

if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()




# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

    for i in range(60):
        ans += 2**i * abs(bits[i] - a_bits[i]*n)

    # a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans//2 % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

debug = False

if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()




# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = int_to_bits(a)

    for i in range(60):
        ans += 2**i * abs(bits[i] - a_bits[i]*n)

    # a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans//2 % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = int_to_bits(a)
    a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    bits_dash = [ bits[i] - a_bits[i] for i in range(60)]

    # log("bits_dash", bits_dash)

    ans += sum( ( 2**i * abs(bits_dash[i]-a_dash[i])) for i in range(60) )
    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans * inv(2, MOD) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = int_to_bits(a)
    a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    bits_dash = [ bits[i] - a_bits[i] for i in range(60)]

    # log("bits_dash", bits_dash)

    for i in range(60):
        ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans * inv(2, MOD) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

MOD = 10**9+7

n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = int_to_bits(a)
    a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    bits_dash = [ bits[i] - a_bits[i] for i in range(60)]

    # log("bits_dash", bits_dash)

    for i in range(60):
        ans += 2**i * abs(bits_dash[i] - a_dash[i])
    # log(a, ans)

print((ans//2) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc147/tasks/abc147_d
n = int(input())
nums = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += (nums[i] ^ nums[j]) % 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
now = 1

sum = [0 for i in range(60)]
for i in a:
    ii = i
    for j in range(60):
        if ii%2 == 1:
            sum[j] += 1
        ii //= 2
        if ii == 0:
            break

for i in range(60):
    k = (sum[i]*(n-sum[i]))%mod
    ans = (ans+(k*now)%mod)%mod
    now = (now*2)%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
now = 1

sum = np.zeros(60,dtype=int)
for i in a:
    ii = i
    aa = np.zeros(60,dtype=int)
    for j in range(60):
        aa[j] = ii%2
        ii //= 2
        if ii == 0:
            break
    sum += aa

for i in range(60):
    k = (sum[i]*(n-sum[i]))%mod
    ans = (ans+(k*now)%mod)%mod
    now = (now*2)%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
now = 1

sum = np.zeros(60,dtype=int)
for i in a:
    aa = np.array(list(map(int,list(str(format(i,'060b'))))))
    
    sum += aa

for i in range(60):
    k = (sum[59-i]*(n-sum[59-i]))%mod
    ans = (ans+(k*now)%mod)%mod
    now = (now*2)%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=tuple(map(int,input().split()))
  ll=len(bin(max(a)))+1
  mod=pow(10,9)+7
  x=[0]*63
  for i in a:
    i=bin(i)
    l=len(i)-1
    for j in range(1,l):
      if i[-j]=='1':
        x[j]+=1
  ans=0
  for i in range(1,ll):
    ans+=pow(2,i-1,mod)*(x[i]%mod)*((n-x[i])%mod)%mod
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=tuple(map(int,input().split()))
  mod=pow(10,9)+7
  x=[0]*61
  for i in a:
    for j in range(60):
      if (i >> j) & 1:
        x[j+1]+=1
  ans=0
  for i in range(1,61):
    ans+=pow(2,i-1,mod)*(x[i]%mod)*((n-x[i])%mod)%mod
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(60):
        flag1 = sum([1 for x in a if x & (1 << i)])
        flag0 = n - flag1
        ans += (1 << i) * (flag1 * flag0)
        ans %= MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(60):
        flag1 = sum([1 for x in a if x & (1 << i)])
        flag0 = sum([1 for x in a if not (x & (1 << i))])
        ans += (1 << i) * (flag1 * flag0)
        ans %= MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=sorted(list(map(int,input().split())))
  mod=pow(10,9)+7
  x=[0]*63
  for i in a:
    i=bin(i)
    l=len(i)
    for j in range(1,l-1):
      if i[-j]=='1':
        x[j]+=1
  ans=0
  for i in range(1,l+1):
    if x[i]>0 and x[i]<n:
      ans+=pow(2,i-1,mod)*(x[i]%mod)*((n-x[i])%mod)%mod
      ans%=mod
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    res = 0
    two_factor = 1

    for d in range(60):
        even, odd = 0, 0
        for i in range(n):
            if a[i] & (1 << d):
                odd += 1
            else:
                even += 1
        add = (odd * even) % MOD * two_factor % MOD
        res = (res + add) % MOD
        two_factor = two_factor * 2 % MOD

    print(res)

Submission status: Time Limit Exceeded

Solution code:
K = 1000000007
N = int(input())
A = [int(a) for a in input().split()]
li = [0] * 60
for n in range(N):
    for i in range(60):
        li[i] += A[n] >> i & 1
ans = 0
for i in range(60):
    ans += (1 << i) * li[i] * (N - li[i])
    ans %= K
print(ans)

Submission status: Time Limit Exceeded

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

SUM = 0
for i, a in enumerate(A):
    for b in A[i+1:]:
        SUM += a ^ b
        SUM %= MOD

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	ans = 0
	for k in range(60):
		conts_0 = 0
		conts_1 = 0
		for i,val in enumerate(A):
			target = bin(val)
			target = target[2:]
			target = target[::-1]

			if len(target) >= k+1:
				if "1" == target[k]:
					conts_1 += 1
				else:
					conts_0 += 1
			else:
				conts_0 += 1

		#print("{} {}".format(conts_0, conts_1))
		ans = (ans + (conts_1 * conts_0 * (2**k)) % mod ) % mod

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

ml = len(format(A[-1], 'b'))
bA = [list(map(int, format(val, '061b'))) for val in A]
bAT = list(zip(*bA))
#print(bAT)
bAT = [sum(val) for val in bAT[::-1]]
#nbA = np.asarray(bA).sum(axis=0)[::-1]

cnt = 0
for i, val in enu(bAT):
    cnt += (N-val)*val*(2**(i))
    cnt %= MOD

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

ml = len(format(A[-1], 'b'))
bA = [list(map(int, list(format(val, '061b')))) for val in A]
bAT = list(zip(*bA))
bAT = bAT[::-1]

cnt = 0
for i, bat in enu(bAT):
    o = sum(bat)
    cnt += (N-o)*o*(2**(i))
    cnt %= MOD

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

ml = len(format(A[-1], 'b'))
bA = [list(format(val, '061b')) for val in A]
bAT = list(zip(*bA))
bAT = bAT[::-1]

cnt = 0
for i, bat in enu(bAT):
    z = bat.count('0')
    o = bat.count('1')
    cnt += z*o*(2**(i))
    cnt %= MOD

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=tuple(map(int,input().split()))
  mod=pow(10,9)+7
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=(ans+(a[i]^a[j])%mod)%mod
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    mod = 1000000007

    for i in range(60):
        x = 0
        for j in range(n):
            if a[j] >> i & 1:
                x += 1
        
        now = x * (n - x) % mod
        for j in range(i):
            now = now * 2 % mod
        ans += now
        ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, *A = map(int, open(0).read().split())
mod = 10**9 + 7
ans = 0
d = 1
while any(A):
  c = 0
  for i in range(n):
    q, r = divmod(A[i], 2)
    A[i] = q
    c += r
  ans += c*(n-c) * d
  ans %= mod
  d *= 2
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

b = [0] * 60

def count(a, b):
	i = len(b)-1
	while a:
		b[i] += a % 2
		a //= 2
		i -= 1
	return i+1

def sum_xor(a, b, l):
	i = len(b)-1
	e = 1
	s = 0
	for i in reversed(range(len(b))):
		if a % 2 == 0:
			s += b[i] * e % mod
		else:
			s += (l-(b[i])) * e % mod
		a //= 2
		e = e * 2 % mod
		s = s % mod
	return s

ans = 0
for i in range(N):
	if i > 0:
		ans = (ans + sum_xor(A[i], b, i)) % mod
	count(A[i], b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
MOD = pow(10,9)+7
N = int(input())
d = [[N,0] for _ in range(60)]
A = list(map(int,input().split()))
for k in A:
    c = 0
    while k > 0:
        if k % 2 == 1:
            d[c][0] -= 1
            d[c][1] += 1
        k = k // 2
        c += 1
s = 0
for i in range(60):
    li = d[i]
    s += (li[0]*li[1]*pow(2,i,MOD))%MOD
print(s%MOD)

Submission status: Time Limit Exceeded

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

lap = 0
big = max(a)
while big > 0:
    big //= 2
    lap += 1

xor = [0 for _ in range(lap)]
for i in a:
    num = 0
    for j in range(lap):
        if i % 2 == 1:
            xor[num] += 1
        i //= 2
        num += 1

ans = 0
for i in range(lap):
    ans += pow(2, i, mod) * xor[i] * (n - xor[i]) % mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
mod = 10 ** 9 + 7
cnt = [0 for _ in range(60)]
for a in A:
    for i in range(60):
        cnt[i] += a & 1
        a >>= 1
cnt = [x * (N - x) % mod for x in cnt]
power = 1
ans = 0
for i in range(60):
    ans += power * cnt[i]
    power *= 2
    power %= mod
ans %= mod
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):
    a,b=0,0
    for j in range(N):
        if A[j]%2==0:
            a+=1
        else:
            b+=1
        A[j]=A[j]//2
    ans=(ans+(a*b)*2**i)%MOD
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(n-1):
    for j in range(i+1,n):
        ans+=(a[i]^a[j])%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = [0] * 60
m = 1000000007
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K * x) % 1000000007
        x = (x * x) % 1000000007
        n //= 2
    return (K * x) % 1000000007
mul = [pow_k(2,59-i) for i in range(60)]
for a in A:
    b = bin(a)
    for i in range(1,len(b)-1):
        if b[-i] == '1':
            count[-i] += 1
print(sum([count[i]*(N-count[i])*mul[i]%m for i in range(60)])%m)

Submission status: Time Limit Exceeded

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

nonzero = [0]*60

for i in range(N):
    for j in range(60):
        tmp = (A[i] >> j) & 1
        if tmp != 0:
            nonzero[j] += 1

ans = 0
MOD = 10**9+7

for i in range(60):
    ans += ((N-nonzero[i])*nonzero[i]*(2**i))%MOD
    
print(ans%MOD)

Submission status: Time Limit Exceeded

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

nonzero = [0]*60

for i in range(N):
    for j in range(60):
        tmp = (A[i] >> j) & 1
        if tmp != 0:
            nonzero[j] += 1

ans = 0
MOD = 10**9+7

for i in range(60):
    ans += (N-nonzero[i])*nonzero[i]*pow(2,(i),MOD)%MOD
    
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
A = list(map(int, input().split()))
m = 1000000007
b = [(c[0]^c[1])%m for c in combinations(A,2)]
print(sum(b)%m)

Submission status: Time Limit Exceeded

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

n = 62
D = [0]*n

for i in range(N):
    s = list(bin(A[i])[2:])[::-1]
    for j in range(len(s)):
        D[j] += int(s[j])
ans = 0
for i in range(n):
    ans += D[i]*(N-D[i])*2**i
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

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

n = 100
D = [0]*(n+2)

for i in range(N):
    s = list(bin(A[i])[2:])[::-1]
    for j in range(len(s)):
        D[j] += int(s[j])
ans = 0
for i in range(n):
    ans += D[i]*(N-D[i])*2**i
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


input = sys.stdin.readline

def main():
    N = int(input().rstrip())
    A = list(map(int, input().rstrip().split()))
    M = max(max(A), 1).bit_length()
    A = iter(deque(bin(a)[2:]) for a in A)
    B = [0] * M
    p = 10 ** 9 + 7
    ans = 0

    for n in range(N):
        a = next(A)
        for i in range(len(a)):
            B[i] += int(a.pop())

    for i, b in enumerate(B):
        tmp = b * (N - b) * 2 ** i
        tmp %= p
        ans = ans + tmp
        ans %= p

    print(ans)


if __name__ == '__main__':
    main()