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:
n = int(input())
a = list(map(int, input().split()))

MOD = 10 ** 9 + 7

b = [0] * 60
for x in a:
    for i, temp in enumerate(list(map(int, reversed(bin(x)[2:])))):
        b[i] += temp

ans = 0
d = 1
for x in b:
    ans = (ans + ((x * (n-x)) % MOD) * d) % MOD
    d = d * 2 % MOD

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
d = 1
total = 0
while d < (1 << 60):
  cnt = 0
  for each in A:
    cnt += (each & d) != 0
  total += cnt * (n-cnt) * d
  total %= mod
  d <<= 1
print(total)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32
MOD = 1000000007

def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    m = 60
    x = [0] * m
    for d in map(int, stdin.readline().split()):
        for i in range(m):
            if d & 1:
                x[i] += 1
            d >>= 1
    ans = 0
    for i in range(m - 1, -1, -1):
        ans = (ans * 2 + x[i] * (N - x[i])) % MOD
    print(ans)

main2()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32
MOD = 1000000007

def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    m = 60
    x = np.zeros(m, i8)
    for d in map(int, stdin.readline().split()):
        for i in range(m):
            if d & 1:
                x[i] += 1
            d >>= 1
    ans = 0
    for i in range(m - 1, -1, -1):
        ans = (ans * 2 + x[i] * (N - x[i])) % MOD
    print(ans)

main2()

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
d = 1
total = 0
while d < (1 << 60):
  cnt = 0
  for each in A:
    cnt += str(bin(each & d)).count('1')
  total += cnt * (n-cnt) * d
  total %= mod
  d <<= 1
print(total)

Submission status: Time Limit Exceeded

Solution code:
def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    # 繰り上がり処理ありバージョン
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  def get_ret_from_xs2(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * x
      ret %= 10**9 + 7
    return ret

  # zeros = [1, 1] + [0] * 58  # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  # ones = [2, 2] + [0] * 58 # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  zeros = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      # a_bin = format(a, '060b')
      # a_i_digit_from_right = a_bin[60 - i - 1]
      # if a_i_digit_from_right == '0':
      #   zeros[i] += 1
      # else:
      #   ones[i] += 1

      a_i_digit_from_right = (a >> i) & 0b1
      if a_i_digit_from_right == 0:
        zeros[i] += 1

  # 繰り上がり処理しないでも、各桁で収めてもいいんだ！
  xs = [zeros[i] * (len(a_s) - zeros[i]) for i in range(60)]
  return get_ret_from_xs2(xs)


  # # 繰り上がりのせいで、xsの要素数は60を超えることがあるので注意
  # xs = []
  # i = 0
  # while True:
  #   x_i = 0
  #   if i <= 59:
  #     x_i = (zeros[i] * ones[i])
  #   if i >= 1:
  #     x_i += xs[i - 1] // 2
  #   xs.append(x_i)
  #
  #   if i >= 60 and x_i // 2 == 0:
  #     break
  #
  #   i += 1

  #xs = [2, 3, 1]
  #return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32
MOD = 1000000007

def solve(a, N):
    m = 60
    x = np.zeros(m, i8)
    for d in a:
        for i in range(m):
            if d & 1:
                x[i] += 1
            d >>= 1
    ans = 0
    x = x[::-1]
    for i in range(m):
        ans = (ans * 2 + x[i] * (N - x[i])) % MOD
    print(ans)

def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    a = map(int, stdin.readline().split())
    ans = solve(a, N)

main2()

Submission status: Time Limit Exceeded

Solution code:
def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    # 繰り上がり処理ありバージョン
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  def get_ret_from_xs2(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * x
      ret %= 10**9 + 7
    return ret

  # zeros = [1, 1] + [0] * 58  # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  # ones = [2, 2] + [0] * 58 # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  zeros = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      # a_bin = format(a, '060b')
      # a_i_digit_from_right = a_bin[60 - i - 1]
      # if a_i_digit_from_right == '0':
      #   zeros[i] += 1
      # else:
      #   ones[i] += 1

      a_i_digit_from_right = ((a & (2**i)) >> i) & 0b1
      if a_i_digit_from_right == 0:
        zeros[i] += 1

  # 繰り上がり処理しないでも、各桁で収めてもいいんだ！
  xs = [zeros[i] * (len(a_s) - zeros[i]) for i in range(60)]
  return get_ret_from_xs2(xs)


  # # 繰り上がりのせいで、xsの要素数は60を超えることがあるので注意
  # xs = []
  # i = 0
  # while True:
  #   x_i = 0
  #   if i <= 59:
  #     x_i = (zeros[i] * ones[i])
  #   if i >= 1:
  #     x_i += xs[i - 1] // 2
  #   xs.append(x_i)
  #
  #   if i >= 60 and x_i // 2 == 0:
  #     break
  #
  #   i += 1

  #xs = [2, 3, 1]
  #return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))

Submission status: Time Limit Exceeded

Solution code:
def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    # 繰り上がり処理ありバージョン
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  def get_ret_from_xs2(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * x
      ret %= 10**9 + 7
    return ret

  # zeros = [1, 1] + [0] * 58  # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  # ones = [2, 2] + [0] * 58 # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  zeros = [0] * 60
  ones = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      # a_bin = format(a, '060b')
      # a_i_digit_from_right = a_bin[60 - i - 1]
      # if a_i_digit_from_right == '0':
      #   zeros[i] += 1
      # else:
      #   ones[i] += 1

      a_i_digit_from_right = ((a & (2**i)) >> i) & 0b1
      if a_i_digit_from_right == 0:
        zeros[i] += 1
      else:
        ones[i] += 1

  # 繰り上がり処理しないでも、各桁で収めてもいいんだ！
  xs = [zeros[i] * ones[i] for i in range(60)]
  return get_ret_from_xs2(xs)


  # # 繰り上がりのせいで、xsの要素数は60を超えることがあるので注意
  # xs = []
  # i = 0
  # while True:
  #   x_i = 0
  #   if i <= 59:
  #     x_i = (zeros[i] * ones[i])
  #   if i >= 1:
  #     x_i += xs[i - 1] // 2
  #   xs.append(x_i)
  #
  #   if i >= 60 and x_i // 2 == 0:
  #     break
  #
  #   i += 1

  #xs = [2, 3, 1]
  return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))

Submission status: Time Limit Exceeded

Solution code:
def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  # zeros = [1, 1] + [0] * 58  # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  # ones = [2, 2] + [0] * 58 # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  zeros = [0] * 60
  ones = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      # a_bin = format(a, '060b')
      # a_i_digit_from_right = a_bin[60 - i - 1]
      # if a_i_digit_from_right == '0':
      #   zeros[i] += 1
      # else:
      #   ones[i] += 1

      a_i_digit_from_right = ((a & (2**i)) >> i) & 0b1
      if a_i_digit_from_right == 0:
        zeros[i] += 1
      else:
        ones[i] += 1

  # 繰り上がりのせいで、xsの要素数は60を超えることがあるので注意
  xs = []
  i = 0
  while True:
    x_i = 0
    if i <= 59:
      x_i = (zeros[i] * ones[i])
    if i >= 1:
      x_i += xs[i - 1] // 2
    xs.append(x_i)

    if i >= 60 and x_i // 2 == 0:
      break

    i += 1

  #xs = [2, 3, 1]
  return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))

Submission status: Time Limit Exceeded

Solution code:
def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  # zeros = [1, 1] + [0] * 58  # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  # ones = [2, 2] + [0] * 58 # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  zeros = [0] * 60
  ones = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      a_bin = format(a, '060b')
      a_i_digit_from_right = a_bin[60 - i - 1]
      if a_i_digit_from_right == '0':
        zeros[i] += 1
      else:
        ones[i] += 1

  # 繰り上がりのせいで、xsの要素数は60を超えることがあるので注意
  xs = []
  i = 0
  while True:
    x_i = 0
    if i <= 59:
      x_i = (zeros[i] * ones[i])
    if i >= 1:
      x_i += xs[i - 1] // 2
    xs.append(x_i)

    if i >= 60 and x_i // 2 == 0:
      break

    i += 1

  #xs = [2, 3, 1]
  return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


def main(n: int, a: list):
    ans = 0

    for f, l in combinations(a, 2):
        ans += f ^ l

    if ans > 10**9 + 7:
        print(ans % (10**9 + 7))
    else:
        print(ans)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    main(n, a)

Submission status: Time Limit Exceeded

Solution code:

#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
*l, = map(int,input().split())
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  m = l[i]
  for j in range(60):
    lone[j] += m%2
    m=m>>1
    if m==0:
      continue
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:

#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
*l, = map(int,input().split())
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  m = l[i]
  for j in range(60):
    lone[j] += m%2
    m=m>>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,*a=map(int,open(0).read().split())
c=0
for i in range(61):t=sum(2**i&b and 1for b in a);c+=t*(n-t)*2**i
print(c%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,*a=map(int,open(0).read().split())
  c=0
  for i in range(61):
    i=2**i
    t=sum(i&b>0for b in a)
    c=(c+t*(n-t)*i)%(10**9+7)
  print(c)
main()

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
n,*a=map(int,open(0).read().split())
c=0
for i in range(61):
  i=2**i
  t=sum(i&b>0for b in a)
  c=(c+t*(n-t)*i)%(10**9+7)
print(c)

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
n,*a=map(int,open(0).read().split())
b=[0]*61
for c in a:
  for i in range(61):b[i]+=2**i&c>0
print(sum(pow(2,i,M)*c*(n-c)%M for i,c in enumerate(b))%M)

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
n,*a=map(int,open(0).read().split())
b=[0]*61
for c in a:
  for i in range(61):b[i]+=2**i&c>0
print(sum(pow(2,i,M)*c*(n-c)for i,c in enumerate(b))%M)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
b=[0]*61
for c in a:
  for i in range(61):b[i]+=2**i&c>0
print(sum(2**i*c*(n-c)for i,c in enumerate(b))%(10**9+7))

Submission status: Time Limit Exceeded

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

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)

Submission status: Time Limit Exceeded

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

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-x*(x-1)*pow(2,c,mod))%mod
print(ans)

Submission status: Time Limit Exceeded

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

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-x*(x-1)*(2**c))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().split()
A = []
Su = 0
for c in S:
    A.append(int(c))
for i in range(N):
    # print(i)
    B = int(bin(A[i])[2:])
    for j in range(i+1, N):
        C = int(bin(A[j])[2:])
        D = str(B+C)
        D = D.replace("2", "0")
        Su += int(D, 2)%(10**9+7)
print(Su % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
s = 0
c = 1
while max(A) != 0:
    #print(max(A))
    s0 = 0
    s1 = 0
    for i,j in enumerate(A):
        A[i],mod = divmod(j,2)
        if mod==1:
            s1 +=1
        else:
            s0 +=1
    s = (s+(s0*s1*c)%(10**9+7))%(10**9+7)
    c *= 2
print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
s = 0
c = 1
while max(A) != 0:
    #print(max(A))
    s0 = 0
    s1 = 0
    for i,j in enumerate(A):
        if True:
            A[i],mod = divmod(j,2)
            #print(mod)
            if mod==1:
                s1 +=1
            else:
                s0 +=1
        #print(s0,s1)
    s = (s+(s0*s1*c))%(10**9+7)
    c *= 2
print(s)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())))
bitlist=[]
num=l[-1]
b1=[]
while num!=0:
  b1.append(num%2)
  num//=2
bitlist.append(b1)
for i in range(2,n+1):
  num=l[-i]
  b1=[]
  while num!=0 or len(b1)<len(bitlist[0]):
    b1.append(num%2)
    num//=2
  bitlist.append(b1)
d={}
for i in range(len(bitlist[0])):
  d[i]=0
  for j in range(n):
    d[i]+=bitlist[j][i]
ans=0
table=[1]
for i in range(60):
  table.append((2*table[-1])%(10**9+7))
for i in d: 
  ans=(ans+table[i]*(n-d[i])*d[i])%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

ans = 0
# 各ビット独立で考える
for i in range(60):
    bit = 1 << i
    cnt1 = 0
    for a in A:
        # このビットが立っている場所を数える
        if a & bit:
            cnt1 += 1
    cnt0 = N - cnt1
    # 0ビットの数 * 1ビットの数 で1になるペア数
    cnt = cnt0 * cnt1 % MOD
    ans += cnt * bit % MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())))
bitlist=[]
num=l[-1]
b1=[]
while num!=0:
  b1.append(num%2)
  num//=2
bitlist.append(b1)
for i in range(2,n+1):
  num=l[-i]
  b1=[]
  while num!=0 or len(b1)<len(bitlist[0]):
    b1.append(num%2)
    num//=2
  bitlist.append(b1)
d={}
for i in range(len(bitlist[0])):
  d[i]=0
  for j in range(n):
    d[i]+=bitlist[j][i]
ans=0
for i in d:
  ans=(ans+(2**i)*(n-d[i])*d[i])%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
s = 0

for i in range(N):
    for j in range(i+1,N):
        c = 1
        q1,mod1 = divmod(A[i],2)
        q2,mod2 = divmod(A[j],2)
        g = 1
        while g != 0:
            if mod1 ^ mod2:
                #print(A[i],A[j])
                #print("a")
                s += c
                s = s%(10**9+7)
            g = max(q1,q2)
            q1,mod1 = divmod(q1,2)
            q2,mod2 = divmod(q2,2)
            c*=2

print(s)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
n = int(input())
a = list(map(lambda x: format(int(x), "b").zfill(60), input().split()))

ans = 0
for i in range(60):
    cnt = 0
    for j in a:
        if j[- i - 1] == "1":
            cnt += 1
    tmp = cnt * (n - cnt)
    for _ in range(i):
        tmp = tmp * 2 % mod
    ans += tmp
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys, os
import collections

MOD = 10 ** 9 + 7

def solve(input_stream):
  N = read_int(input_stream)
  numbers = read_ints(input_stream)
  ans = 0
  for target_bit in range(60):
    count = [0] * 2
    for index in range( len(numbers) ):
      ans += ( count[ (numbers[index] >> target_bit & 1) ^ 1 ] ) << target_bit
      count[ numbers[index] >> target_bit & 1] += 1
  return [str(ans % MOD)]


def read_ints(input_stream):
  return [i for i in map(int, input_stream.readline().strip().split())]

def read_int(input_stream):
  return int(input_stream.readline().strip())


if __name__ == "__main__":
    outputs = solve(sys.stdin)
    for line in outputs:
      print(line)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
n = int(input())
a = list(map(lambda x: format(int(x), "b").zfill(60), input().split()))

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

Submission status: Time Limit Exceeded

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

for i in range(60):
    assert np.count_nonzero(arr & 1) == sum(arr & 1)
    c1 = np.count_nonzero(arr & 1)
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1
print(s % mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  ones = 0
  for i in A:
    if i>>j & 1:
      ones += 1
  ans += 2**j*((n-ones)*ones)
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()))

n_bit = max(a).bit_length()
b = [(1 << j) % MOD for j in range(n_bit)]

ans = 0
bit = [0] * n_bit
for i in range(n):
    for j in range(n_bit):
        if (a[i] >> j) & 1:
            ans += b[j] * (i - bit[j])
            bit[j] += 1
        else:
            ans += b[j] * bit[j]
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

n_bit = max(a).bit_length()
ans = 0
bit = [0] * n_bit
for i in range(n):
    for j in range(n_bit):
        if (a[i] >> j) & 1:
            ans += (1 << j) * (i - bit[j])
        else:
            ans += (1 << j) * bit[j]
        ans %= MOD

        if (a[i] >> j) & 1:
            bit[j] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

ones = [0] * 60
m = 10 ** 9 + 7

for Ai in A:
    for digit in range(len(bin(Ai)) - 2):
        ones[digit] += ((Ai >> digit) & 1)

res = 0
for i, num in enumerate(ones):
    res += (1 << i) * num * (N - num)

print(res % m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

ones = [0] * 60
m = 10 ** 9 + 7

for Ai in A:
    for digit in range(len(bin(Ai)) - 2):
        ones[digit] += ((Ai >> digit) & 1)

res = 0
for i, num in enumerate(ones):
    res = (res + (1 << i) * num * (N - num)) % m

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

ones = [0] * 60
m = 10 ** 9 + 7

for Ai in A:
    for digit in range(60):
        ones[digit] += ((Ai >> digit) & 1)

res = 0
for i, num in enumerate(ones):
    res = (res + (1 << i) * num * (N - num)) % m

print(res)

Submission status: Time Limit Exceeded

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

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

mod = 10**9 + 7

res = 0

for i in range(60):
    count = 0
    for j in range(N):
        if ((A[j] >> i) & 1):
            count += 1
    res += (N - count) * count * 2 ** i 
    res %= 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(n):
    for j in range(i,n):
        if i != j:
            ans += a[i] ^ a[j]
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
import numpy as np
A = np.array(list(map(lambda x:list('{:060b}'.format(int(x))),input().split()))).T
ans = 0
mod = 10**9+7
for d in range(60):
  c = list(A[d]).count('0')
  ans += 2**(59-d)*c*(n-c)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())

numbers = map(int, input().split())

res = 0
for pair in combinations(numbers, 2):
    res += pair[0] ^ pair[1]

p = 10 ** 9 + 7
print(res % p)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

num = [[0, 0] for _ in range(60)]

for Ai in A:
    for digit in range(60):
        if (Ai >> digit) & 1:
            num[digit][1] += 1
        else:
            num[digit][0] += 1

res = 0
for i, p in enumerate(num):
    res += (1 << i) * p[0] * p[1]

m = 10 ** 9 + 7
print(res % m)

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()


import numpy as np


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return np.array(ret_r, dtype='int')


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = np.zeros(n, dtype='int')
ans = 0
for a in A:
    n_1_ls += ret_binary(a)


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
MOD = 10 ** 9 + 7
#1番目以降(N個の数)のbitの格桁の合計
l = np.array([0] * 60)
for i in range(N):
    s = np.array(list(map(int, list(str(bin(A[i]))[2:].rjust(60, '0')))))
    #print(s)
    l = l + s
l2 = np.array([0] * 60)
#print(l)
for i in range(N-1):
    s = np.array(list(map(int, list(str(bin(A[i]))[2:].rjust(60, '0')))))
    x = N - 1 - i
    l -= s
    l2 += s * (x-l)
    l2 += (1-s) * l
    
answer = 0
#print(l2)
l2 = l2.tolist()
for i in range(60):
    answer += 2 ** (59-i) * l2[i]
    answer %= MOD
#print(l)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(lambda x: '{:060b}'.format(int(x)), input().split()))
ans = 0
mod = 10**9+7
for d in range(60):
  cnt = 0
  for i in range(n):
    if a[i][d] == '1':
      cnt += 1
  ans += 2 ** (59-d) * cnt * (n - cnt)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input()) 
A = [ bin(int(i))[2:].zfill(60) for i in input().split()] 

mod = 10**9+7
c = [0]*60
for i in A:
  for j in range(60):
    if i[j] == '1':
      c[-1-j] +=1     
ans = 0
for i in range(60):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    mod = 10 ** 9 + 7

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

    ret = 0
    for j in range(60):
        cnt1 = sum((x >> j) & 1 for x in a)
        cnt0 = n - cnt1
        ret = (ret + cnt0 * cnt1 * (1 << j)) % mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
MOD = 10 ** 9 + 7
#1番目以降(N個の数)のbitの格桁の合計
l = [0] * 60
for i in range(N):
    s = list(str(bin(A[i]))[2:].rjust(60, '0'))
    #print(s)
    for j in range(60):
        if s[j] == '1':
            l[j] += 1
l2 = [0] * 60
#print(l)
for i in range(N-1):
    s = list(str(bin(A[i]))[2:].rjust(60, '0'))
    x = N - 1 - i
    for j in range(60):
        if s[j] == '1':
            l[j] -= 1
            l2[j] += x - l[j]
        else:
            l2[j] += l[j]
answer = 0
#print(l2)
for i in range(60):
    answer += 2 ** (59-i) * l2[i]
    answer %= MOD
#print(l)
print(answer)

Submission status: Time Limit Exceeded

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

    P = 10**9+7
    bit = [0 for i in range(60)]

    # 各bit独立に1が何個あるか数える
    for a in A:
        S = bin(a)
        for j in range(1,len(S)-1):
            if S[-1*j] == '1':
                bit[j-1] += 1

    # 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
    ans = 0
    for i,a in enumerate(bit):
        ans += a*(N-a)*(2**i)
        ans %= P

    print(ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

d = []
for j in range(60):
  d.append(0)

A = [int(_) for _ in input().split()]

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

sum = 0
for i in range(N):
  for j in range(60):
    if (A[i] & (1 << j)) != 0:
      sum += (1 << j) * (N - i - d[j])
      d[j] -= 1
    else:
      sum += (1 << j) * d[j]

print(sum % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
MOD = 10 ** 9 + 7
#1番目以降(N個の数)のbitの格桁の合計
l = [0] * 60
for i in range(N):
    s = list(str(bin(A[i]))[2:].rjust(60, '0'))
    #print(s)
    for j in range(60):
        if s[j] == '1':
            l[j] += 1
l2 = [0] * 60
#print(l)
for i in range(N-1):
    s = list(str(bin(A[i]))[2:].rjust(60, '0'))
    for j in range(60):
        if s[j] == '1':
            l[j] -= 1
            l2[j] += N - 1 - i - l[j]
        else:
            l2[j] += l[j]
answer = 0
#print(l2)
for i in range(60):
    answer += 2 ** (59-i) * l2[i]
    answer %= MOD
#print(l)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input()) 
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7
c = [0]*k
for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    if bit[j] == '0':
      c[-1-j] +=1     
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input()) 
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7
c = [0]*k
for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    c[-1-j] +=int(bit[j])    
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)

Submission status: Time Limit Exceeded

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

P = 10**9+7
bit = [0 for i in range(60)]

# 各bit独立に1が何個あるか数える
for a in A:
    S = bin(a)
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
ans = 0
for i,a in enumerate(bit):
    ans += a*(N-a)*(2**i)
    ans %= P

print(ans)