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:
m = 10**9 + 7
n = int(input())
seq = [bin(int(x))[2:].zfill(61) for x in input().split()]
cnt = [[0,0] for i in range(61)]
for s in seq:
    for i in range(61):
        if s[i] == '0':
            cnt[i][0] += 1
        else:
            cnt[i][1] += 1
ans = 0
for i in range(61):
  ans += cnt[-i-1][0]*cnt[-i-1][1]*(2**i)
  ans = ans % m
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    *A, = map(int, input().split())
    ans = 0
    B = [0] * 61
    for k, a in enumerate(A):
        *la, = map(int, list(bin(a))[2:])
        j = 0
        for i in range(61-len(la), 61):
            B[i] += la[j]
            j += 1

    ans = 0
    mod = 10**9 + 7
    for i, b in enumerate(B):
        ans += b * (len(A)-b) * 2**(60-i) % mod
    print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    *A, = map(int, input().split())
    ans = 0
    B = [0] * 61
    for k, a in enumerate(A):
        la = list(bin(a))[2:]
        j = 0
        for i in range(61-len(la), 61):
            B[i] += int(la[j])
            j += 1

    ans = 0
    mod = 10**9 + 7
    for i, b in enumerate(B):
        ans += b * (len(A)-b) * 2**(60-i) % mod
    print(ans % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, log2

input = sys.stdin.readline

def main():
    MOD = 10**9 + 7
    
    N = int(input())
    A = list(map(int, input().split()))
    K = ceil(log2(max(max(A), 1)))
    nums = [[0,0] for i in range(K)]
    ks = [(i, 2**i) for i in range(K)]
    
    for i, a in enumerate(A):
        for j, k in ks:
            n = a & k > 0
            nums[j][n] += 1
    ans = 0
    
    for a in A:
        for j, k in ks:
            n = a & k > 0
            nums[j][n] -= 1
            ans += k * nums[j][not n] % MOD
            
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

mod = 10**9+7

array = [0] * 60

for i in a:
    for j in range(len(bin(i))-2):
        # print(bin(i),i >> j & 1)
        array[j] += (i >> j) & 1

ans = 0
# print(array)

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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*A, = map(int, input().split())
ans = 0
B = [0] * 61
for k, a in enumerate(A):
    la = list(bin(a))[2:]
    j = 0
    for i in range(61-len(la), 61):
        B[i] += int(la[j])
        j += 1

ans = 0
mod = 10**9 + 7
for i, b in enumerate(B):
    ans += b * (len(A)-b) * 2**(60-i) % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
d = defaultdict(lambda:0)
ans = 0
for a in A:
    a = bin(a)[2:]
    for i in range(len(a)):
        if a[-i-1]=='1':
            d[i] += 1

for a in A:
    a = (60-len(bin(a))+2)*'0'+bin(a)[2:]
    for i in d:
        if a[-i-1]=='0':
            ans += pow(2,i,mod)*d[i]
        else:
            ans += pow(2,i,mod)*(N-d[i])

ans *= pow(2,mod-2,mod)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
# 各bitの1の総数を数える
ones = [0] * 61
for a in a_list:
    for i, b in enumerate(bin(a)[:1:-1]):
        ones[i] += int(b)
ans = 0
for i, k in enumerate(ones):
    ans += 2 ** i * k * (n - k)
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
ans = 0
for i in range(61):
    k = 0
    for a in a_list:
        if a & 2 ** i != 0:
            k += 1
    ans += k * (n - k) * 2 ** i
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

result = 0
for b in range(60):
  bs = sum((e >> b) & 1 for e in A)
  result = (result + bs * (N - bs) * (1 << b)) % 1000000007
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
md = len(bin(max(a)))
ans = 0
for d in range(md):
    cnt1 = sum([1 for i in a if ((i>>d)&1)]) # a内の全ての要素の d bit目の1の個数を数える
    ans += cnt1 * (n-cnt1) * (1<<d)          # 求めるべきは (0の個数)*(1の個数)をd bit目にそのまま収めたものを足し合わせたもの (?)
    ans %= mod                               # mod 取っておく
    
print(ans%mod)

Submission status: Time Limit Exceeded

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

s = 0
for i in range(n - 1):
    for j in range(i, n):
        s += a[i] ^ a[j]
print(s % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

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

threshold = 10**9+7
if total < threshold:
    print(total)
else:
    print(total%threshold)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from functools import reduce

# input
n = int(input())
alist = list(map(int, input().split()))

# processing
l = []

i = 0
while i < n-1:
    j = i + 1
    while j < n:
        l.append(alist[i]^alist[j])
        j+=1
    i+=1

# output
print(reduce(lambda x, y: x+y, l) % (10**9+7))

Submission status: Time Limit Exceeded

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

ans = 0
m = 1
for i in range(60):
    bits = sum(((a >> i) & 1 for a in A))
    ans += (bits * (N - bits) * m)
    ans %= MOD
    m <<= 1
print(ans % MOD)

Submission status: Time Limit Exceeded

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

ans = 0
for k in range(61):
    N1 = 0
    N1 = sum(1 for a in A if ( (a >> k) & 1))
    ans += (((1<<k)) *(N-N1) *N1)
    ans %= M    

print(int(ans))

Submission status: Time Limit Exceeded

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

ans = 0
for k in range(60):
    N1 = 0
    N1 = sum(1 for a in A if ( (a >> k) & 1))
    N0 = N-N1
    ans += (((1<<k)) *N0 *N1)
    ans %= M    

print(int(ans))

Submission status: Time Limit Exceeded

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

ans = 0
for k in range(60):
    N1 = 0
    for a in A:
        if (a >> k) & 1:
            N1 += 1
    N0 = N-N1
    ans += (((1<<k)) *N0 *N1)
    ans %= M    

print(int(ans))

Submission status: Time Limit Exceeded

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

ans = 0
for k in range(60):
    N1 = 0
    N1 = sum(( (a >> k) & 1) for a in A )
    N0 = N-N1
    ans += (((1<<k)%M) *N0 *N1) % M

ans %= M    
print(int(ans))

Submission status: Time Limit Exceeded

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

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

ans %= M    
print(int(ans))

Submission status: Time Limit Exceeded

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

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

ans %= M    
print(int(ans))

Submission status: Time Limit Exceeded

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

k=[0]*60
K=[0]*60
for i in range(N):
  t=A[i]
  for j in range(60):
    if t%2==1:
      k[j]+=1
    t=t//2
    if t<1:
      break
a=1
sumxor=0
for i in range(60):
  K[i]=k[i]*(N-k[i])
  a=a%(10**9+7)
  sumxor=(sumxor+K[i]*a%(10**9+7))%(10**9+7)
  a=a*2
print(sumxor)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = str(input()).split(' ')
a_s = [int(a) for a in As]

sum = 0
index = 0
for Ai in a_s:
  for Aj in a_s[index+1:]:
    sum += Ai ^ Aj
  index += 1

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

Submission status: Time Limit Exceeded

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

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

ans = 0
for k in range(60):
    x = 0
    x0 = 0
    x1 = 0
    for a in A:
        x = format(a>>k&1,'b')
        if x == '0':
            x0 += 1
        else:
            x1 += 1

    p = x0*x1
    for _ in range(k):
        p *= 2 % (10**9+7)
    ans += p

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

Submission status: Time Limit Exceeded

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

ans = 0
for k in range(60):
    x = 0
    x0 = 0
    x1 = 0
    for a in A:
        x = format(a>>k&1,'b')
        if x == '0':
            x0 += 1
        else:
            x1 += 1

    p = x0*x1
    for _ in range(k):
        p *= 2 % (10**9+7)
    ans += p

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

Submission status: Time Limit Exceeded

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

ans = 0
for k in range(60):
    x = 0
    x0 = 0
    x1 = 0
    for a in A:
        x = format(a>>k&1,'b')
        if x == '0':
            x0 += 1
        else:
            x1 += 1

    ans += ((2**k)*x0*x1)%(10**9+7)

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

Submission status: Time Limit Exceeded

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

ans = 0
for k in range(60):
    x = 0
    x0 = 0
    x1 = 0
    for a in A:
        #x = format(a>>k&1,'b')
        x = bin(a>>k&1)
        if x == '0b1':
            x0 += 1
        else:
            x1 += 1

    ans += ((2**k)*x0*x1)

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

Submission status: Time Limit Exceeded

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

ans = 0
for k in range(60):
    x = 0
    x0 = 0
    x1 = 0
    for a in A:
        x = format(a>>k&1,'b')
        if x == '0':
            x0 += 1
        else:
            x1 += 1

    ans += ((2**k)*x0*x1)

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()))
A2   = [0]*N
BitNum = [0]*(61)

for i in range(1,61):
    A2 = [0] * N
    for j in range(N):
        A2[j] = A[j] % 2
        A[j] //= 2
    BitNum[i] = sum(A2)

ans = 0
beki = 0
for i in range(1,61):
    x = BitNum[i]
    y = N - x
    ans += (x*y)*(2**beki)
    ans %= MOD
    beki += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
inputList = input().split()

sum = 0
for i in range(a - 1):
  for j in range(i + 1, a):
    sum += int(inputList[i]) ^ int(inputList[j])

print(sum % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
inputList = input().split()


index = 0
sum = 0
for i in range(a - 1):
  for j in range(i + 1, a):
    sum += (int(inputList[i]) ^ int(inputList[j]))

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

Submission status: Time Limit Exceeded

Solution code:
a = input()
inputList = input().split()


index = 0
sum = 0
for i in inputList:
  if index == len(inputList) - 1:
    break
  for j in inputList[index+1:]:
    sum += (int(i) ^ int(j))
  index += 1

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

Submission status: Time Limit Exceeded

Solution code:
# from heapq import heappush, heappop, heapify
# from collections import deque, defaultdict, Counter
# import itertools
# from itertools import permutations, combinations, accumulate
import sys
# import bisect
# import string
# import math
# import time
# from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


# YN = ['No', 'Yes']
MOD = 10**9+7
# inf = float('inf')
# IINF = 10**10
# l_alp = string.ascii_lowercase
# u_alp = string.ascii_uppercase
# ts = time.time()
# sys.setrecursionlimit(10**6)
# nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

# xor
# n + i = n ^ i implies n & i = 0


# def sumXOR(arr,  n):
#     _sum = 0
#     for i in range(0, 64):
#         zc = 0
#         oc = 0

#         # Individual sum at each bit position
#         idsum = 0
#         for j in range(0, n):
#             if (arr[j] % 2 == 0):
#                 zc = zc + 1
#             else:
#                 oc = oc + 1
#             arr[j] = arr[j] >> 1

#         # calculating individual bit sum
#         idsum = oc * zc * (1 << i)
#         print(zc, oc, idsum)

#         # final sum
#         _sum = _sum + idsum
#         _sum %= MOD

#     return _sum


def main():
    N = I()
    A = list(MI())
    BIT = 61
    C = [[0] * BIT for i in range(N+1)]
    ans = 0

    for i in range(N):
        bit = 1
        for j in range(BIT):
            if A[i] & bit:
                C[i+1][j] = C[i][j] + 1
            else:
                C[i+1][j] = C[i][j]
            bit = bit << 1

    for i in range(N):
        bit = 1
        for j in range(BIT):
            oc = C[N][j] - C[i][j]
            # print('b', ans, i, j, bit, oc)
            if A[i] & bit:
                zc = N - i - oc
                ans += bit * zc
            elif oc != 0:
                ans += bit * oc
            ans %= MOD
            bit = bit << 1
            # print('a', ans, i, j, bit, oc)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# from heapq import heappush, heappop, heapify
# from collections import deque, defaultdict, Counter
# import itertools
# from itertools import permutations, combinations, accumulate
import sys
# import bisect
# import string
# import math
# import time
# from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


# YN = ['No', 'Yes']
MOD = 10**9+7
# inf = float('inf')
# IINF = 10**10
# l_alp = string.ascii_lowercase
# u_alp = string.ascii_uppercase
# ts = time.time()
# sys.setrecursionlimit(10**6)
# nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

# xor
# n + i = n ^ i implies n & i = 0


# def sumXOR(arr,  n):
#     _sum = 0
#     for i in range(0, 64):
#         zc = 0
#         oc = 0

#         # Individual sum at each bit position
#         idsum = 0
#         for j in range(0, n):
#             if (arr[j] % 2 == 0):
#                 zc = zc + 1
#             else:
#                 oc = oc + 1
#             arr[j] = arr[j] >> 1

#         # calculating individual bit sum
#         idsum = oc * zc * (1 << i)
#         print(zc, oc, idsum)

#         # final sum
#         _sum = _sum + idsum
#         _sum %= MOD

#     return _sum


def main():
    N = I()
    A = list(MI())
    BIT = 61
    C = [[0] * (N+1) for i in range(BIT)]
    ans = 0

    for i in range(N):
        bit = 1
        for j in range(BIT):
            if A[i] & bit:
                C[j][i+1] = C[j][i] + 1
            else:
                C[j][i+1] = C[j][i]
            bit = bit << 1

    for i in range(N):
        bit = 1
        for j in range(BIT):
            oc = C[j][N] - C[j][i]
            # print('b', ans, i, j, bit, oc)
            if A[i] & bit:
                zc = N - i - oc
                ans += bit * zc
            elif oc != 0:
                ans += bit * oc
            ans %= MOD
            bit = bit << 1
            # print('a', ans, i, j, bit, oc)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# from heapq import heappush, heappop, heapify
# from collections import deque, defaultdict, Counter
# import itertools
# from itertools import permutations, combinations, accumulate
import sys
# import bisect
# import string
# import math
# import time
# from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


# YN = ['No', 'Yes']
MOD = 10**9+7
# inf = float('inf')
# IINF = 10**10
# l_alp = string.ascii_lowercase
# u_alp = string.ascii_uppercase
# ts = time.time()
# sys.setrecursionlimit(10**6)
# nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

# xor
# n + i = n ^ i implies n & i = 0


# def sumXOR(arr,  n):
#     _sum = 0
#     for i in range(0, 64):
#         zc = 0
#         oc = 0

#         # Individual sum at each bit position
#         idsum = 0
#         for j in range(0, n):
#             if (arr[j] % 2 == 0):
#                 zc = zc + 1
#             else:
#                 oc = oc + 1
#             arr[j] = arr[j] >> 1

#         # calculating individual bit sum
#         idsum = oc * zc * (1 << i)
#         print(zc, oc, idsum)

#         # final sum
#         _sum = _sum + idsum
#         _sum %= MOD

#     return _sum


def main():
    N = I()
    A = list(MI())
    BIT = 61
    C = [[0] * (N+1) for i in range(BIT)]
    ans = 0

    for i in range(N):
        for j in range(BIT):
            bit = 1 << j
            if A[i] & bit:
                C[j][i+1] = C[j][i] + 1
            else:
                C[j][i+1] = C[j][i]

    for i in range(N):
        for j in range(BIT):
            oc = C[j][N] - C[j][i]
            bit = 1 << j
            # print('b', ans, i, j, bit, oc)
            if A[i] & bit:
                zc = N - i - oc
                ans += bit * zc
            elif oc != 0:
                ans += bit * oc
            ans %= MOD
            # print('a', ans, i, j, bit, oc)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

# xor
# n + i = n ^ i implies n & i = 0


def sumXOR(arr,  n):
    _sum = 0
    for i in range(0, 64):
        zc = 0
        oc = 0

        # Individual sum at each bit position
        idsum = 0
        for j in range(0, n):
            if (arr[j] % 2 == 0):
                zc = zc + 1
            else:
                oc = oc + 1
            arr[j] = arr[j] >> 1

        # calculating individual bit sum
        idsum = oc * zc * (1 << i)
        print(zc, oc, idsum)

        # final sum
        _sum = _sum + idsum
        _sum %= MOD

    return _sum


def main():
    N = I()
    A = list(MI())
    BIT = 61
    C = [[0] * (N+1) for i in range(BIT)]
    ans = 0

    for i in range(N):
        for j in range(BIT):
            bit = 1 << j
            if A[i] & bit:
                C[j][i+1] = C[j][i] + 1
            else:
                C[j][i+1] = C[j][i]

    for i in range(N):
        for j in range(BIT):
            oc = C[j][N] - C[j][i]
            bit = 1 << j
            # print('b', ans, i, j, bit, oc)
            if A[i] & bit:
                zc = N - i - oc
                ans += bit * zc
            elif oc != 0:
                ans += bit * oc
            ans %= MOD
            # print('a', ans, i, j, bit, oc)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

# xor
# n + i = n ^ i implies n & i = 0


def sumXOR(arr,  n):
    _sum = 0
    for i in range(0, 64):
        zc = 0
        oc = 0

        # Individual sum at each bit position
        idsum = 0
        for j in range(0, n):
            if (arr[j] % 2 == 0):
                zc = zc + 1
            else:
                oc = oc + 1
            arr[j] = arr[j] >> 1

        # calculating individual bit sum
        idsum = oc * zc * (1 << i)
        print(zc, oc, idsum)

        # final sum
        _sum = _sum + idsum
        _sum %= MOD

    return _sum


def main():
    N = I()
    A = list(MI())
    BIT = 61
    C = [[0] * (N+1) for i in range(BIT)]
    AC = [None for i in range(BIT)]
    ans = 0

    for i in range(N):
        for j in range(BIT):
            bit = 1 << j
            if A[i] & bit:
                C[j][i+1] = C[j][i] + 1
            else:
                C[j][i+1] = C[j][i]

    for i in range(N):
        for j in range(BIT):
            oc = C[j][N] - C[j][i]
            bit = 1 << j
            # print('b', ans, i, j, bit, oc)
            if A[i] & bit:
                zc = N - i - oc
                ans += bit * zc
            elif oc != 0:
                ans += bit * oc
            ans %= MOD
            # print('a', ans, i, j, bit, oc)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

# xor
# n + i = n ^ i implies n & i = 0


def sumXOR(arr,  n):
    _sum = 0
    for i in range(0, 64):
        zc = 0
        oc = 0

        # Individual sum at each bit position
        idsum = 0
        for j in range(0, n):
            if (arr[j] % 2 == 0):
                zc = zc + 1
            else:
                oc = oc + 1
            arr[j] = arr[j] >> 1

        # calculating individual bit sum
        idsum = oc * zc * (1 << i)
        print(zc, oc, idsum)

        # final sum
        _sum = _sum + idsum
        _sum %= MOD

    return _sum


def main():
    N = I()
    A = list(MI())
    BIT = 60
    C = [[0] * N for i in range(BIT)]
    AC = [None for i in range(BIT)]
    ans = 0

    for i in range(N):
        for j in range(BIT):
            bit = 1 << j
            if A[i] & bit:
                C[j][i] = 1

    for j in range(BIT):
        AC[j] = list(accumulate([0] + C[j]))

    for i in range(N):
        for j in range(BIT):
            oc = AC[j][N] - AC[j][i]
            zc = N - i - oc
            bit = 1 << j
            # print('b', ans, i, j, bit, oc)
            if A[i] & bit:
                ans += bit * zc
            elif oc != 0:
                ans += bit * oc
            ans %= MOD
            # print('a', ans, i, j, bit, oc)

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

# xor
# n + i = n ^ i implies n & i = 0


def sumXOR(arr,  n):
    _sum = 0
    for i in range(0, 64):
        zc = 0
        oc = 0

        # Individual sum at each bit position
        idsum = 0
        for j in range(0, n):
            if (arr[j] % 2 == 0):
                zc = zc + 1
            else:
                oc = oc + 1
            arr[j] = arr[j] >> 1

        # calculating individual bit sum
        idsum = oc * zc * (1 << i)
        print(zc, oc, idsum)

        # final sum
        _sum = _sum + idsum
        _sum %= MOD

    return _sum


def main():
    N = I()
    A = list(MI())
    C = [[0] * N for i in range(64)]
    AC = [None for i in range(64)]
    ans = 0

    for i in range(N):
        for j in range(64):
            bit = 1 << j
            if A[i] & bit:
                C[j][i] = 1

    for j in range(64):
        AC[j] = list(accumulate([0] + C[j]))

    for i in range(N):
        for j in range(64):
            oc = AC[j][N] - AC[j][i]
            zc = N - i - oc
            bit = 1 << j
            # print('b', ans, i, j, bit, oc)
            if A[i] & bit:
                ans += bit * zc
            elif oc != 0:
                ans += bit * oc
            ans %= MOD
            # print('a', ans, i, j, bit, oc)

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


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


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


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


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


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

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

def bai(i):
    i[0] *= 2
    i[0] = int(i[0])
    return i[0]

tmp = [1/2]
bit_nums = list(zip(*[list(i.zfill(max_length)) for i in bit_nums]))
sum_ones = [lst.count("1") for lst in bit_nums]
multiples = [i * (length - i) for i in sum_ones]

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


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


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


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


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


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

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


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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


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


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


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


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


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

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

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

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