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 = [int(_) for _ in input().split()]
const = 10**9 + 7

ans = 0

zero = [0] * 60
one = [0] * 60

for i in range(n):
    for j in range(60):
        if a[i] >> j & 1:
            one[j] += 1
        else:
            zero[j] += 1

ans = 0

for i in range(n):
    j = 0
    while a[i] != 0:
        if a[i] % 2 == 0:
            ans += one[j] * (2**j)
            zero[j] -= 1
        else:
            ans += zero[j] * (2**j)
            one[j] -= 1
        a[i] //= 2
        j += 1
    ans %= const

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
const = 10**9 + 7

ans = 0

zero = [0] * 60
one = [0] * 60

for i in range(n):
    for j in range(60):
        if a[i] >> j & 1:
            one[j] += 1
        else:
            zero[j] += 1

ans = 0

for i in range(n):
    j = 0
    while a[i] != 0:
        if a[i] % 2 == 0:
            ans += one[j] * (2**j)
            zero[j] -= 1
        else:
            ans += zero[j] * (2**j)
            one[j] -= 1
        ans %= const
        a[i] //= 2
        j += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
const = 10**9 + 7

ans = 0

for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        ans += a[i]^a[j]
        ans %= const

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))
p = 7 + 10**9
b = 60

x = np.zeros((n, b), np.int)
for i in range(n):
    x[i] = np.array(list(bin(a[i])[2:].zfill(b)), int)

s = np.sum(x, axis=0)

pow2 = (2 ** np.array(list(range(b)), np.int64))[::-1]

ans = s%p * (n-s)%p * (pow2%p)
print(np.sum(ans) % p)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
c0_1 = []
for i in range(60):
    c0_1.append([0,0])
for i in range(N):
    A[i] = list(str(bin(A[i]))[2:].zfill(60))
    for j in range(60):
        if A[i][j] == "0":
            c0_1[j][0] += 1
        else:
            c0_1[j][1] += 1

ans = 0
for i in range(60):
    ans += (c0_1[i][0] * c0_1[i][1]) * (2**(59-i))
    ans %= 10**9 + 7
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(n-1):
    ai = a.pop()
    ans += sum(list(map(lambda x: x ^ ai, a)))

print(ans % p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

div = 10 ** 9 + 7

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ai = bin(a[i])
        aj = bin(a[j])
        ai = ai[2:]
        aj = aj[2:]
        dif = len(ai) - len(aj)
        if dif > 0:
            add = ''
            for _ in range(dif):
                add += '0'
            aj = add + aj
        elif dif < 0:
            add = ''
            for _ in range(-dif):
                add += '0'
            ai = add + ai
        xor = ['0' for _ in range(len(ai))]
        for k in range(len(ai)):
            if ai[k] != aj[k]:
                xor[k] = '1'
        plus = '0b'
        for k in range(len(ai)):
            plus += xor[k]
        plus = int(plus, 2)
        ans += plus
        ans %= div

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array([], dtype=np.int64)
a_ = list(map(int, input().split()))
for i in a_:
    a = np.append(a, i)
m = 10**9+7
ans = 0
for k in range(0, 61):
    b = (a>>k) & 1
    res = np.count_nonzero(b)
    ans += res*(n-res)*2**k
print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
blist=[0]*61
plist=[(2**i)%mod for i in range(61)]
for i in range(n):
  tmp=arr[i]
  pos=0
  while tmp!=0:
    if tmp%2==1:
      blist[pos]+=1
      tmp-=1
    tmp=tmp//2
    pos+=1
ans=0
for i in range(61):
  ans+=(plist[i]*blist[i])*(n-blist[i])+(plist[i]*(n-blist[i]))*blist[i]
  ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
blist=[0]*61
plist=[2**i for i in range(61)]
for i in range(n):
  tmp=arr[i]
  pos=0
  while tmp!=0:
    if tmp%2==1:
      blist[pos]+=1
      tmp-=1
    tmp=tmp//2
    pos+=1
ans=0
for i in range(n):
  flag=format(arr[i],'b')
  if len(flag)!=61:
    flag='0'*(61-len(flag))+flag
  flag=flag[::-1]
  for j in range(61):
    c=int(flag[j])
    if c==1:
      ans+=plist[j]*(n-blist[j])
      ans%=mod
    else:
      ans+=plist[j]*blist[j]
      ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(lambda x: format(int(x), "060b"), input().split()))
Num = 10**9 + 7
digit = [0 for i in range(60)]
for a in A:
  for i in range(60):
    if a[i] == "1":
      digit[i] += 1
#print(digit)
ans = 0
for i in range(60):
  ans = (ans * 2 + digit[i] * (N-digit[i])) %Num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(lambda x: format(int(x), "060b"), input().split()))
Num = 10**9 + 7
digit = [[0, 0] for i in range(60)]
for a in A:
  for i in range(60):
    digit[i][int(a[i])] += 1
#print(digit)
ans = 0
for i in range(60):
  ans = (ans * 2 + digit[i][0] * digit[i][1])
print(ans %Num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(lambda x: format(int(x), "060b"), input().split()))
Num = 10**9 + 7
digit = [[0, 0] for i in range(60)]
for a in A:
  for i in range(60):
    digit[i][int(a[i])] += 1
#print(digit)
ans = 0
for i in range(60):
  ans = (ans * 2 + digit[i][0] * digit[i][1]) % Num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
counter = [0] * 60
for i in range(N):
    bA = bin(A[i])
    for j in range(len(bA)-2):
        if bA[j+2] == '1':
            counter[60+j-(len(bA)-2)] += 1
res = 0
for i in range(60):
    res += (((counter[i] * (N-counter[i])) % (10**9+7)) * ((2 ** (59-i))) % (10**9+7))
print(res%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n =int(input())
    al = list(map(int,input().split()))

    res = 0
    bits = [[0]*2 for _ in range(60)]
    for a in al:
        for i in range(60):
            bits[i][int(bin(a >> i)[-1])] += 1

    res = 0

    for i in range(60):
        res += bits[i][0] * bits[i][1]  * (2 ** i)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

res = 0
bits = [[0]*2 for _ in range(60)]
for a in al:
    for i in range(60):
        bits[i][int(bin(a >> i)[-1])] += 1

res = 0

for i in range(60):
    res += bits[i][0] * bits[i][1]  * (2 ** i) % (10 ** 9 + 7)

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

Submission status: Time Limit Exceeded

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

res = 0
bits = [[0]*2 for _ in range(60)]
for a in al:
    for i in range(60):
        bits[i][int(bin(a >> i)[-1])] += 1

res = 0

for i in range(60):
    res += bits[i][0] * bits[i][1]  * (2 ** i)

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

Submission status: Time Limit Exceeded

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

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

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

    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

mod = 10**9+7

bin_a = []

for i in range(n):
    bin_a.append(format(a[i],'060b'))

ans = 0

for i in range(60):
    one = 0
    zero = 0
    for j in range(n):
        #print(bin_a[j])
        if bin_a[j][i] == '1':
            one += 1
        else:
            zero += 1
    #print(i,zero,one)
    ans += zero * one * (2**(59-i))
    
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
ba = np.array([[int(j) for j in list(format(i,'b').zfill(60))] for i in a]).T
mod = 10**9+7

#2^iをmodで割った余りを出しておく
twos = [1]
for i in range(1,60):
    twos.append((twos[i-1]*2)%mod)

#各baのbitごとに0の個数を求める
c0 = np.sum(ba, axis=1)

#答えは各bitごとの(0の数)*(1の数)より求まる
ans = 0
for i in range(60):
    ans += (((c0[59-i]*(n-c0[59-i]))%mod)*twos[i])%mod

ans %= mod
print(int(ans))

Submission status: Time Limit Exceeded

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

#2^iをmodで割った余りを出しておく
twos = [1]
for i in range(1,60):
    twos.append((twos[i-1]*2)%mod)

#各baのbitごとに0の個数と1の個数を求める
c0 = [0]*60
for i in range(n):
    for j in range(60):
        if a[i]%2 == 0:
            c0[j] += 1
        a[i] //= 2

#答えは各bitごとの(0の数)*(1の数)より求まる
ans = 0
for i in range(60):
    ans += (((c0[i]*(n-c0[i]))%mod)*twos[i])%mod

ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
ba = [format(i,'b').zfill(60) for i in a]
mod = 10**9+7

#2^iをmodで割った余りを出しておく
twos = [1]
for i in range(1,60):
    twos.append((twos[i-1]*2)%mod)

#各baのbitごとに0の個数と1の個数を求める
c0 = [0]*60
c1 = [0]*60
for i in range(n):
    for j in range(60):
        if ba[i][j] == "0":
            c0[59-j] += 1
        else:
            c1[59-j] += 1

#答えは各bitごとの(0の数)*(1の数)より求まる
ans = 0
for i in range(60):
    ans += (((c0[i]*c1[i])%mod)*twos[i])%mod

ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    MOD = 10**9 + 7
    
    N = int(input())
    A = list(map(int, input().split()))
    
    import numpy as np
    
    count = np.zeros((N+1, 60, 2), dtype='int')
    
    b = np.zeros(60, dtype='int')
    b[0] = 1
    for i in range(1, 60): b[i] = b[i-1] * 2 % MOD
    
    for i in range(1, N+1):
        count[i] = np.copy(count[i-1])
        a = A[i-1]
        for j in range(60):
            count[i][j][a%2] += 1
            a >>= 1
        
    ans = 0
    
    n = np.zeros(60, dtype='int')
    for i in range(1, N):
        c = count[N]-count[i]
        a = A[i-1]
        for j in range(60):
            n[j] = c[j][0] if a % 2 else c[j][1]
            a >>= 1
        ans = (ans + np.sum(n*b)) % MOD
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

maxdig = 60
mod = 10**9+7

ans = 0
for i in range(60+1):
  cnt1 = 0
  for a in A:
    if (a >> i) & 1:
      cnt1 += 1
  ans += (cnt1*(N-cnt1)*(1<<i))
  ans = ans%mod

print(ans)

Submission status: Time Limit Exceeded

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

maxdig = 60

ans = 0
for i in range(60+1):
  d = 2**i
  cnt1 = 0
  for a in A:
    if (a >> i) & 1:
      cnt1 += 1
  ans += (cnt1*(N-cnt1)*d)
  ans = ans%1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import log2

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

maxdig = 60

ans = 0
for i in range(60, -1, -1):
  d = 2**i
  cnt1 = 0
  for j in range(N):
    if A[j]//d > 0:
      cnt1 += 1
      A[j] -= d
  ans += (cnt1*(N-cnt1)*d)
  ans = ans%1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())

mod = 10**9 + 7

cnt = [0] * 61
for a in A:
    for i in range(61):
        if a >> i & 1:
            cnt[i] += 1

ans = 0
p = 1
for i in cnt:
    ans = (ans + (p * i * (N - i)) % mod) % mod
    # ans %= mod
    p = p * 2 % mod
    # p %= mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, *A = map(int, sys.stdin.read().split())

mod = 10**9 + 7
ans = 0
for n, i in enumerate(A[:-1]):
    for j in A[n + 1:]:
        ans += i ^ j
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

max_digits = 60  # 最大桁数は60
MOD = 10**9 + 7

# format関数で10進数から2進数に変換
bin_arr = np.array(list(map(lambda x: list(format(x, 'b').zfill(max_digits))[::-1], a)), dtype='int')

ans = 0
n_mod = n % MOD
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    one_mod = np.count_nonzero(bin_arr[:, i]) % MOD
    radix_mod = 2**i % MOD
    ans += (radix_mod * one_mod * (n_mod - one_mod)) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 10**9 + 7

# format関数で10進数から2進数に変換
max_digits = len(format(max(a), 'b'))  # 最大桁数

# 各位の1の数を記録していく
counter = []
for i in range(n):
    counter.append(list(format(a[i], 'b').zfill(max_digits))[::-1])  # 逆順にする 
cnt_arr = np.array(counter, dtype='int')

ans = 0
n_mod = n % MOD
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    one_mod = np.count_nonzero(cnt_arr[:, i]) % MOD
    radix_mod = 2**i % MOD
    ans += (radix_mod * one_mod * (n_mod - one_mod)) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 10**9 + 7

# format関数で10進数から2進数に変換
max_digits = len(format(max(a), 'b'))  # 最大桁数

# 各位の1の数を記録していく
counter = []
for i in range(n):
    counter.append(list(format(a[i], 'b').zfill(max_digits))[::-1])  # 逆順にする 
cnt_arr = np.array(counter, dtype='int')

ans = 0
n_mod = n % MOD
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    one_num = np.count_nonzero(cnt_arr[:, i]) % MOD
    ans += (2**i * one_num * (n_mod - one_num)) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 10**9 + 7

# format関数で10進数から2進数に変換
max_digits = len(format(max(a), 'b'))  # 最大桁数

# 各位の1の数を記録していく
counter = []
for i in range(n):
    counter.append(list(format(a[i], 'b').zfill(max_digits))[::-1])  # 逆順にする 
cnt_arr = np.array(counter, dtype='int')

ans = 0
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    one_num = np.count_nonzero(cnt_arr[:, i]) % MOD
    ans += (2**i * one_num * (n - one_num)) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 10**9 + 7

# format関数で10進数から2進数に変換
max_digits = len(format(max(a), 'b'))  # 最大桁数

# 各位の1の数を記録していく
counter = []
for i in range(n):
    counter.append(list(format(a[i], 'b').zfill(max_digits))[::-1])  # 逆順にする 
cnt_arr = np.array(counter, dtype='int')

ans = 0
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    one_num = np.count_nonzero(cnt_arr[:, i])
    ans += (2**i * one_num * (n - one_num)) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

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

# format関数で10進数から2進数に変換
max_digits = len(format(max(a), 'b'))  # 最大桁数

# 各位の1の数を記録していく
counter = [0]*max_digits
for i in range(n):
    for i, b in enumerate(format(a[i], 'b')[::-1]):
        counter[i] += int(b)
        
MOD = 10**9 + 7

ans = 0
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    ans += (2**i * counter[i] * (n - counter[i])) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [(2 ** (leng - j - 1)) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 7 + 10**9
A = []
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    A.append(list(map(int, format(a[i], 'b').zfill(leng))))
for i in range(leng):
    bit_acc[i] = sum([A[j][i] for j in range(n)]) 
ans = 0
p = [pow(2,leng - j - 1,mod) for j in range(leng)]
for i in range(n):
    for j in range(leng):
        if A[i][j] == 1:
            ans += (n - bit_acc[j]) * p[j]
        else:
            ans += bit_acc[j] * p[j]
        ans %= mod
print((ans * 500000004) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 7 + 10**9
A = []
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    A.append(list(map(int, format(a[i], 'b').zfill(leng))))
for i in range(leng):
    bit_acc[i] = sum([A[j][i] for j in range(n)]) 
ans = 0
p = [pow(2,leng - j - 1,mod) for j in range(leng)]
for i in range(n):
    for j in range(leng):
        if A[i][j] == 1:
            ans += (n - bit_acc[j]) * p[j]
        else:
            ans += bit_acc[j] * p[j]
print((ans * 500000004) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 7 + 10**9
A = []
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    A.append(list(map(int, format(a[i], 'b').zfill(leng))))
for i in range(leng):
    bit_acc[i] = sum([A[j][i] for j in range(n)]) 
ans = 0
for i in range(n):
    for j in range(leng):
        if A[i][j] == 1:
            ans += (n - bit_acc[j]) * pow(2,leng - j - 1,mod)
        else:
            ans += bit_acc[j] * pow(2,leng - j - 1,mod)
print((ans * 500000004) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 7 + 10**9
A = []
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    A.append(list(map(int, format(a[i], 'b').zfill(leng))))
for i in range(leng):
    bit_acc[i] = sum([A[j][i] for j in range(n)]) 
ans = 0
for i in range(n):
    for j in range(leng):
        if A[i][j] == 1:
            ans += (n - bit_acc[j]) * pow(2,leng - j - 1)
        else:
            ans += bit_acc[j] * pow(2,leng - j - 1)
print((ans * 500000004) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 7 + 10**9
A = []
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    A.append(list(map(int, format(a[i], 'b').zfill(leng))))
for i in range(leng):
    bit_acc[i] = sum([A[j][i] for j in range(n)]) 
ans = 0
for i in range(n):
    for j in range(leng):
        if A[i][j] == 1:
            ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
        else:
            ans += bit_acc[j] * (2 ** (leng - j - 1))
print((ans * 500000004) % mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        # 先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
            else:
                ans += bit_acc[j] * (2 ** (leng - j - 1))
            ans %= mod
    print((ans * 500000004) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
            else:
                ans += bit_acc[j] * (2 ** (leng - j - 1))
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
            else:
                ans += bit_acc[j] * (2 ** (leng - j - 1))
        ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
            else:
                ans += bit_acc[j] * (2 ** (leng - j - 1))
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    #先頭から二進数を0埋めした
    bit_data = format(a[i], 'b').zfill(leng)
    for j in range(leng):
        if bit_data[j] == '1':
            bit_acc[j] += 1
ans = 0
for i in range(n):
    bit_data = format(a[i], 'b').zfill(leng)
    for j in range(leng):
        if bit_data[j] == '1':
            ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
        else:
            ans += bit_acc[j] * (2 ** (leng - j - 1))
        ans %= mod
print((ans * 500000004) % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))

sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i]^A[j]

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

Submission status: Time Limit Exceeded

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

sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i]^A[j]

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
v=[0]*64
ans=0
mod=1000000007
zero=0
one=0

index=n-1
while index>=0:
	for k in range(61):
		one=v[k]
		zero=n-1-index-one
		tmp=1<<k
		if((a[index]&tmp)==0):
			ans=(ans+tmp*one)%mod
		else:
			ans=(ans+tmp*zero)%mod
			v[k]=v[k]+1
	index-=1


print(ans)
print()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
v=[0]*64
ans=0
mod=1000000007
zero=0
one=0

index=n-1
while index>=0:
	for k in range(64):
		one=v[k]
		zero=n-1-index-one
		if((a[index]&(1<<k))==0):
			ans=(ans+(1<<k)*one)%mod
		else:
			ans=(ans+(1<<k)*zero)%mod
			v[k]=v[k]+1
	index-=1


print(ans)

Submission status: Time Limit Exceeded

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

p = int(1e9+7)
res = 0

for i in range(60):
    zc = 0
    oc = 0
    for j in range(len(A)):
        if A[j] % 2 == 0:
            zc += 1
        else:
            oc += 1
        A[j] = A[j] >> 1

    res += zc*oc*2**i
    res %= p

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(map(lambda x: format(x, '0b').zfill(60), A))

p = int(1e9+7)
res = 0
d = [0]*60

for a in A:
    for i in range(60):
        d[i] += int(a[i])

for i, d in enumerate(d[::-1]):
    res += d*(N-d)*2**i
    res %= p

print(res)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split()))
A = list(map(lambda x: format(x, '0b').zfill(60), A))
res = 0

for i in range(60):
    one = 0
    for a in A:
        one += int(a[-(i+1)])
    res += one*(N-one)*2**i
    res %= p

print(res)

Submission status: Time Limit Exceeded

Solution code:
def xor(a, b):
    xor = a ^ b
    return xor


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

count = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        count += xor(a[i], a[j])

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

Submission status: Time Limit Exceeded

Solution code:
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            n = (n - 1) // 2
        else:
            x = x ** 2
            n = n // 2

    return K * x


MOD = 10**9 + 7

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

res = 0
for d in range(60):
    n0, n1 = 0, 0
    for i in range(N):
        if (An[i] >> d) & 1:
            n1 += 1
        else:
            n0 += 1

    temp = pow_k(2, d) % MOD
    temp *= (n0*n1) % MOD
    res = (res + temp) % MOD

print(res)