Problem:


Score : 400 points

Problem Statement

We have N integers. The i-th integer is A_i.

Find \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

2 \leq N \leq 3 \times 10^5

0 \leq A_i < 2^{60}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the value \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

Sample Input 1

3
1 2 3

Sample Output 1

6

We have (1\mbox{ XOR } 2)+(1\mbox{ XOR } 3)+(2\mbox{ XOR } 3)=3+2+1=6.

Sample Input 2

10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

237

Sample Input 3

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

Sample Output 3

103715602

Print the sum modulo (10^9+7).



Sample input:
3
1 2 3


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
#n,m=input_list()
tmp=input_list()
f_num=60
a=[bin(i)[2:].zfill(f_num) for i in tmp]
mod=10**9+7
ans=0
for keta_i in range(f_num):
    tmp=[0,0]
    for n_i in range(n):
        ind=int(a[n_i][keta_i])
        tmp[ind]+=1

    cal=(tmp[0]*tmp[1]*pow(2,f_num-keta_i-1,mod))%mod
    ans+=cal
    # if cal>0:
    #     print(keta_i,f_num-keta_i-1)
    #     print(cal)
    #     print(tmp)
    tmp=[0,0]

ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
#n,m=input_list()
tmp=input_list()
f_num=60
a=[bin(i)[2:].zfill(f_num) for i in tmp]
mod=10**9+7
ans=0
for keta_i in range(f_num):
    tmp=[0,0]
    for n_i in range(n):
        ind=int(a[n_i][keta_i])
        tmp[ind]+=1

    cal=(tmp[0]*tmp[1]*pow(2,f_num-keta_i-1,mod))%mod
    ans+=cal
    # if cal>0:
    #     print(keta_i,f_num-keta_i-1)
    #     print(cal)
    #     print(tmp)
    tmp=[0,0]

ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())))
for i,x in enumerate(l):
  l[i]=format(x,'63b')
memo=[0]*63
for i in range(63):
  for j in range(n):
    if l[j][i]=='1':
      memo[-i-1]+=1
now=1
ans=0
mod=10**9+7
for x in memo:
  ans+=(now*x*(n-x))%mod
  now*=2
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def change_n_shinsu(x, n):
    ans = ''
    while True:
        shou = x // n
        amari = x % n
        if shou == 0 and amari == 0:
            break
        ans = str(amari) + ans
        x = shou
    ans = ans.zfill(60)
    return ans

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

zero = [0 for i in range(60)]
one = [0 for i in range(60)]

for i in range(n):
    ai = change_n_shinsu(a[i], 2)
    for j in range(60):
        if ai[j] == '0':
            zero[j] += 1
        else:
            one[j] += 1

zero = zero[::-1]
one = one[::-1]

ans = 0
for i in range(60):
    kumi = (zero[i] * one[i]) % mod
    num = pow(2, i, mod)
    ans += (kumi * num) % mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    readline = sys.stdin.buffer.readline
    N = int(readline())
    A = list(map(int, readline().split()))

    MOD = 10**9 + 7

    ans = 0
    M = len(bin(max(A)))-2
    B = [bin(A[i])[2:].zfill(M) for i in range(N)]
    bin1 = [0 for _ in range(M)]

    for d in range(M):
        for b in B:
            if b[-(d+1)] == "1":
                bin1[-(d+1)] += 1
        ans += pow(2, d, MOD) * bin1[-(d+1)] * (N - bin1[-(d+1)])
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    readline = sys.stdin.buffer.readline
    N = int(readline())
    A = list(map(int, readline().split()))

    MOD = 10**9 + 7

    ans = 0
    M = len(bin(max(A)))-2
    B = [bin(A[i])[2:].zfill(M) for i in range(N)]
    bin1 = [0 for _ in range(M)]

    for d in range(M):
        for i in range(N):
            if B[i][-(d+1)] == "1":
                bin1[-(d+1)] += 1
        ans += pow(2, d, MOD) * bin1[-(d+1)] * (N - bin1[-(d+1)])
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    readline = sys.stdin.buffer.readline
    N = int(readline())
    A = list(map(int, readline().split()))

    MOD = 10**9 + 7

    ans = 0
    M = len(bin(max(A))[2:])
    B = [bin(A[i])[2:].zfill(M) for i in range(N)]
    bin1 = [0 for _ in range(M)]

    for d in range(M):
        for i in range(N):
            if B[i][-(d+1)] == "1":
                bin1[-(d+1)] += 1
        ans += pow(2, d, MOD) * bin1[-(d+1)] * (N - bin1[-(d+1)])
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    MOD = 10**9 + 7

    ans = 0
    M = len(bin(max(A))[2:])
    B = [bin(A[i])[2:].zfill(M) for i in range(N)]
    bin1 = [0 for _ in range(M)]

    for d in range(M):
        bin1[-(d+1)] = sum([int(B[i][-(d+1)]) for i in range(N)])
        ans += pow(2, d, MOD) * bin1[-(d+1)] * (N - bin1[-(d+1)])
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

ans = 0
M = len(bin(max(A))[2:])
B = [bin(A[i])[2:].zfill(M) for i in range(N)]
bin1 = [0 for _ in range(M)]

for d in range(M):
    bin1[-(d+1)] = sum([int(B[i][-(d+1)]) for i in range(N)])
    ans += pow(2, d, MOD) * bin1[-(d+1)] * (N - bin1[-(d+1)])
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

ans = 0
M = len(bin(max(A))[2:])
B = [bin(A[i])[2:].zfill(M) for i in range(N)]
bin1 = [0 for _ in range(M)]

for d in range(M):
    bin1[d] = sum([int(B[i][d]) for i in range(N)])

for d in range(M):
    ans += pow(2, d, MOD) * bin1[-(d+1)] * (N - bin1[-(d+1)])
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 10**9 + 7

ans = 0
M = len(bin(max(A))[2:])

B = [bin(A[i])[2:].zfill(M) for i in range(N)]
bin1 = [0 for _ in range(M)]

for d in range(M):
    bin1[d] = sum([int(B[i][d]) for i in range(N)])

for d in range(M):
    ans += pow(2, d, MOD) * bin1[-(d+1)] * (N - bin1[-(d+1)])
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

ans = 0
M = len(bin(max(A))[2:])

bin1 = [0 for _ in range(M)]

for i in range(N):
    b = bin(A[i])[2:].zfill(M)
    for d in range(M):
        bin1[d] += int(b[d])

for d in range(M):
    ans += pow(2, d, MOD) * bin1[-(d+1)] * (N - bin1[-(d+1)])
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

ans = 0
M = len(bin(max(A))[2:])

for d in range(1, M+1):
    res = 0
    res = sum([int(bin(A[i])[2:].zfill(M)[-d]) for i in range(N)])
    ans += pow(2, d-1, MOD) * res * (N-res)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

ans = 0
M = len(bin(max(A))[2:])

for d in range(1, M+1):
    #print("d", d)
    res = 0
    for i in range(N):
        bit = bin(A[i])[2:].zfill(M)[-d]
        #print(bin(A[i])[2:].zfill(M), bit)
        res += int(bit)
    #res = sum([int(bin(A[i])[2:].zfill(M)[-d]) for i in range(N)])
    ans += pow(2, d-1, MOD) * res * (N-res)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
mod = int(1e9+7)
for i in range(61):
    tmp = 0
    for j in A:
        tmp += (j>>i)&1
    ans += (N-tmp)*tmp*pow(2,i,mod)

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
for k in range(60):
  t=1<<k
  z=o=0
  for i in a:
    if i&t:o+=1
    else:z+=1
  ans=(ans+(z*o*t))%mod
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7

    digit_0 = [0] * 60
    digit_1 = [0] * 60

    for i in range(N):
        for j in range(60):
            if (A[i] >> j) & 1:
                digit_1[j] += 1
            else:
                digit_0[j] += 1
    
    ans = 0
    for j in range(60):
        ans += ((digit_0[j] * digit_1[j] % p) * pow(2,j,p) % p)
        ans %= p
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
maxketa = max([len(bin(a[i])) for i in range(n)])-2
mod = 10**9+7
ans = 0
for i in range(maxketa):
	ones = 0
	for j in range(n):
		if (a[j] >> i) & 1:
			ones += 1
	ans = (ans + (n-ones)*ones*(2**i)) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
maxketa = max([len(bin(a[i])) for i in range(n)])-2
array = [[(a[j]>>i) & 1 for j in range(n)] for i in range(maxketa)]
"""
arrayは逆順に並んでることに注意
"""
mod = 10**9+7
tmparrayc = [Counter(array[i]) for i in range(maxketa)]
ans = sum([tmparrayc[i][0]*tmparrayc[i][1]*(2**i) % mod for i in range(maxketa)]) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
A.sort(reverse=True)

mod=10**9+7
keta=[0]*60

for i in range(N):
    for j in range(60):    
        keta[j]+=((A[i]>>j)&1)

ans=0

mod_div2=[0]*60
mod_div2[0]=1
for i in range(1,60):
    mod_div2[i]=(2*mod_div2[i-1])%mod
    
for i in range(len(A)):
    keta_max=0
    for j in range(60):
        if(1<=(A[i]//(2**j))):
            keta_max=j+1
    for j in range(keta_max):
            if((A[i]>>j)&1):
                keta[j]-=1
                ans+=mod_div2[j]*(len(A)-i-1-keta[j])
            else:
                ans+=mod_div2[j]*keta[j]
            ans%=mod


print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
A.sort(reverse=True)

mod=10**9+7
keta=[0]*60

for i in range(N):
    for j in range(60):    
        keta[j]+=((A[i]>>j)&1)

ans=0
for i in range(len(A)):
    keta_max=0
    for j in range(60):
        if(1<=(A[i]//(2**j))):
            keta_max=j+1
    for j in range(keta_max):
            if((A[i]>>j)&1):
                keta[j]-=1
                ans+=(2**j)*(len(A)-i-1-keta[j])
            else:
                ans+=(2**j)*keta[j]
            ans%=mod


print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
s=[0 for i in range(60)]
def totwo(x):
  return [int(x&(2**i)>0) for i in range(60)]

n=int(input())
a=list(map(lambda x:totwo(int(x)),input().split()))

d=[a[0][i] for i in range(60)]
for i in range(1,n):
  for j in range(60):
    if a[i][j]:
      s[j]+=i-d[j]
    else:
      s[j]+=d[j]
    d[j]+=a[i][j]

ss=0
r=1
mod=10**9+7
for i in range(60):
  ss=(ss+r*s[i])%mod
  r=(r*2)%mod
print(ss)

Submission status: Time Limit Exceeded

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

acc = [0] * MAX
ans = [0] * MAX

num = a[0]
for i in range(MAX):
    if num & 1:
        acc[i] = 1
    num >>= 1

for i, e in enumerate(a[1:], 1):
    for j in range(MAX):
        if e & 1:
            ans[j] += i - acc[j]
            acc[j] += 1
        else:
            ans[j] += acc[j]

        e >>= 1

ans_num = 0
for i, e in enumerate(ans):
    ans_num += pow(2, i, mod) * e
    ans_num %= mod

print(ans_num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main2():
    ketaone = [0]*61
    MOD = 10**9 + 7
    n = int(input())
    A=[int(i) for i in input().split()]

    for i in A:
        for j in range(61):
            if i&(1<<j):
                ketaone[j]+=1
    res = 0

    for i in range(61):
        res = res + (ketaone[i]*(n-ketaone[i])*(2**i))%MOD
        res%=MOD
    print(res)


def main1():
    n = int(input())
    lis = [[] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            lis[i].append(list(map(int, input().split())))
    res = 0

    for i in range(1<<n):
        f = True
        uso=set()
        syo=set()
        tmp=0
        for j in range(n):
            if(i&(1<<j)):
                tmp+=1
                for k in lis[j]:
                    if (i&(1<<(k[0]-1))) and k[1]==0:
                        f=False
                    if k[1]==1 and not (i&(1<<k[0]-1)):
                        f=False
        if f:
            res = max(res,tmp)
    print(res)


if __name__ == '__main__':
    main2()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    MOD = 10**9 + 7
    t = 0
    k = max(A)
    while k>0:
        k=k//2
        t+=1

    bisu = [0]*(t+1)
    zerobi = [0]*(t+1)
    res = 0
    for i in range(n):
        for j in range(t+1):
            if A[i]&(1<<j):
                bisu[j]+=1

    for i in range(t+1):
        res = res + (bisu[i]*(n-bisu[i])*(2**i))%MOD
    print(res%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
O=[0]*61
Z=[0]*61
for a in A:
	for i in range(61):
		if (1<<i)&a:
			O[i]+=1
		else:
			Z[i]+=1
	
R=0
for i in range(61):
	R+=pow(2,i,MOD)*O[i]%MOD*Z[i]%MOD
	R%=MOD

print(R)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
O=[0]*61
Z=[0]*61
for a in A:
	for i in range(61):
		if (1<<i)&a:
			O[i]+=1
		else:
			Z[i]+=1

L=[0]*61
for i in range(61):
	L[i]=O[i]*Z[i]
	
R=0
for i in range(61):
	R+=pow(2,i,MOD)*L[i]
	R%=MOD
print(R)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    two_factor = 1
    for d in range(60):
        even = 0
        odd = 0
        for i in range(n):
            if a[i] & (1 << d):
                odd += 1
            else:
                even += 1
        add = (odd * even) % Mod * two_factor % Mod
        ans += add
        ans %= Mod
        two_factor = (two_factor * 2) % Mod
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Time Limit Exceeded

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

cnt = [0] * 65

for x in a:
  i = 0
  while x:
    if x % 2:
      cnt[i] += 1
    x //= 2
    i += 1
      
ans = 0
for i in range(len(cnt)-1, -1, -1):
  ans *= 2
  ans += cnt[i] * (n-cnt[i])
  ans %= mod
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
n = int(input())
a = list(map(lambda x: format(int(x), 'b'), input().split()))

cnt = [0] * 65

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

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

mb=format(max(a),'b')
arr=[0]*len(mb)

for i in range(n):
    b=format(a[i],'b')
    for j in range(len(b)):
        if b[-j-1]=='1':
            arr[j]+=1

ans=0

for i in range(len(mb)):
    ans+=(arr[i]*(n-arr[i])*(2**i))%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

mb=format(max(a),'b')
arr=[0]*len(mb)

for i in range(n):
    b=format(a[i],'b')
    for j in range(len(b)):
        if b[-j-1]=='1':
            arr[j]+=1

ans=0

for i in range(len(mb)):
    ans+=arr[i]*(n-arr[i])*(2**i)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(lambda x: format(int(x), '060b'), input().split(' ')))
mod = 10 ** 9 + 7
one = [0]*60
ans = 0
for i in A:
    for n, j in enumerate(i[::-1]):
        if int(j):
            one[n] += 1
for n,i in enumerate(one):
    ans = (ans + 2**n *i*(N-i))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9) + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(60):
    cnt = 0
    for j in range(n):
        if a[j] >> i & 1 == 1:
            cnt += 1
    ans += (cnt * (n-cnt) * (2**i)) % MOD
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
a=0
c=0
m=max(A)
while(m):
    o=sum(map(lambda x:x&1,A))
    a+=(n-o)*o*2**c
    A=list(map(lambda x:x>>1,A))
    c+=1
    a%=10**9+7
    m//=2
print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
import numpy as np
#======================================================#
MOD=10**9+7
def main():
    n = II()
    aa = np.array(MII())
    ans = 0
    for i in range(60):
        cnt1 = int(sum(aa&1))
        ans += cnt1*(n-cnt1)*(2**i)
        aa >>= 1
    print(ans%MOD)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=A[i]^A[j]
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  a=list(map(lambda x:list(map(int,list(bin(int(x))[2:]))),input().split()))
  mod=pow(10,9)+7
  ans=0
  len_ai=[]
  for ai in a:
    len_ai.append(len(ai))
  for i in range(61):# 2^iの位
    bit1=0
    for j in range(n):
      if len_ai[j]>=i+1:
        bit1+=a[j][-i-1]
    ans+=(pow(2,i,mod)*bit1*(n-bit1))%mod
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=np.array(list(map(lambda x:list(map(int,list(('0'*62+bin(int(x))[2:])[-62:]))),input().split())),np.int64)
mod=pow(10,9)+7
b=np.sum(a,axis=0)
ans=0
for i in range(61):# 2^iの位
  ans+=(pow(2,i,mod)*b[-i-1]*(n-b[-i-1]))%mod
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=list(map(lambda x:list(map(int,list(bin(int(x))[2:]))),input().split()))
  mod=pow(10,9)+7
  ans=0
  len_ai=[]
  for ai in a:
    len_ai.append(len(ai))
  for i in range(61):# 2^iの位
    bit1=0
    for j in range(n):
      if len_ai[j]>=i+1:
        bit1+=a[j][-i-1]
    ans+=(pow(2,i,mod)*bit1*(n-bit1))%mod
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=list(map(lambda x:bin(int(x))[2:],input().split()))
  mod=pow(10,9)+7
  ans=0
  len_ai=[]
  for ai in a:
    len_ai.append(len(ai))
  for i in range(61):# 2^iの位
    bit1=0
    for j in range(n):
      if len_ai[j]>=i+1:
        bit1+=int(a[j][-i-1])
    ans+=pow(2,i)*bit1*(n-bit1)
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=np.array(list(map(lambda x:list(map(int,list(('0'*62+bin(int(x))[2:])[-62:]))),input().split())),np.int64)
mod=pow(10,9)+7
ans=0
for i in range(61):# 2^iの位
  bit1=np.sum(a[:,-i-1])
  b=pow(2,i,mod)
  b*=bit1
  b%=mod
  b*=n-bit1
  b%=mod
  ans+=b
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(lambda x:('0'*62+bin(int(x))[2:])[-62:],input().split()))
mod=pow(10,9)+7
ans=0
for i in range(61):# 2^iの位
  bit1=0
  for ai in a:
    bit1+=int(ai[-i-1])
  ans+=pow(2,i,mod)*bit1*(n-bit1)
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(lambda x:('0'*62+bin(int(x))[2:])[-62:],input().split()))
mod=pow(10,9)+7
ans=0
for i in range(61):# 2^iの位
  bit1=0
  for ai in a:
    bit1+=int(ai[-i-1])
  ans+=pow(2,i)*bit1*(n-bit1)
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    m = max(a)
    l = len(bin(m)) - 2
    y = [list(bin(i)[2:].zfill(l)) for i in a]

    mod = 10 ** 9 + 7
    ans = 0
    for i, j in enumerate(zip(*y)):
        o = j.count('1')
        z = n - o
        ans += z * o * pow(2, l - i - 1, mod)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input()) #3* 10**5
A_list = [int(e) for e in input().split()] #<=2**60

MOD_BY = 10**9 + 7
#愚直解だと 3* 10**5 C 2 ≒ 9 * 10**10 でTLEする。

#bit毎に考える
max_bit = len(bin(max(A_list))[2:])
bit_array = list()

for i in range(N): #3* 10**5
    bit_list = list(bin(A_list[i])[2:])
    bit_list = [int(i) for i in bit_list]
    
    if len(bit_list) < max_bit:
        bit_list = [0 for _ in range(max_bit-len(bit_list))] + bit_list

    bit_array.append(bit_list)

#print(bit_array)

bit_sum_list = [sum([row[i] for row in bit_array]) for i in range(max_bit)]
##print(bit_sum_list)

ans = 0
 
for i in range(N-1): #3* 10**5
    for j in range(max_bit):  #60
        if bit_array[i][j] == 0:
            ans += bit_sum_list[j] * 2**(max_bit - j - 1) % MOD_BY
        elif bit_array[i][j] == 1:
            ans += (N - i - bit_sum_list[j]) * 2**(max_bit - j - 1) % MOD_BY
            bit_sum_list[j] -= 1
        
        ans %= MOD_BY
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input()) #3* 10**5
A_list = [int(e) for e in input().split()] #<=2**60

MOD_BY = 10**9 + 7
#愚直解だと 3* 10**5 C 2 ≒ 9 * 10**10 でTLEする。

#bit毎に考える
max_bit = len(bin(max(A_list))[2:])
bit_sum_list = [0 for _ in range(max_bit)] #60
bit_list = [list() for _ in range(N)] #3* 10**5

for i in range(N): #3* 10**5
    bit_array = str(bin(A_list[i])[2:]).zfill((max_bit))
    
    for j in range(max_bit): #60
        inted_bit = int(bit_array[j])
        bit_sum_list[j] += inted_bit
        bit_list[i].append(inted_bit)
        
ans = 0

for i in range(N-1): #3* 10**5
    for j in range(max_bit):  #60
        if bit_list[i][j] == 0:
            ans += bit_sum_list[j] * 2**(max_bit - j - 1) % MOD_BY
        elif bit_list[i][j] == 1:
            ans += (N - i - bit_sum_list[j]) * 2**(max_bit - j - 1) % MOD_BY
            bit_sum_list[j] -= 1
            
        ans %= MOD_BY
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input()) #3* 10**5
A_list = [int(e) for e in input().split()] #<=2**60

MOD_BY = 10**9 + 7
#愚直解だと 3* 10**5 C 2 ≒ 9 * 10**10 でTLEする。

#bit毎に考える
max_bit = len(bin(max(A_list))[2:])
bit_sum_list = [0 for _ in range(max_bit)] #60
bit_list = [list() for _ in range(N)] #3* 10**5

for i in range(N): #3* 10**5
    bit_array = str(bin(A_list[i])[2:]).zfill((max_bit))
    
    for j in range(max_bit): #60
        inted_bit = int(bit_array[j])
        bit_sum_list[j] += inted_bit
        bit_list[i].append(inted_bit)
        
ans = 0

for i in range(N-1): #3* 10**5
    for j in range(max_bit):  #60
        if bit_list[i][j] == 0:
            ans += bit_sum_list[j] * 2**(max_bit - j - 1) % MOD_BY
        elif bit_list[i][j] == 1:
            ans += (N - i - bit_sum_list[j]) * 2**(max_bit - j - 1) % MOD_BY
            bit_sum_list[j] -= 1
            
        ans %= MOD_BY
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input()) #3* 10**5
A_list = [int(e) for e in input().split()] #<=2**60

MOD_BY = 10**9 + 7
#愚直解だと 3* 10**5 C 2 ≒ 9 * 10**10 でTLEする。

#bit毎に考える
max_bit = len(bin(max(A_list))[2:])
bit_sum_list = [0 for _ in range(max_bit)]
bit_list = [list() for _ in range(N)]

for i in range(N):
    bit_array = str(bin(A_list[i])[2:]).zfill((max_bit))
    
    for j in range(max_bit):
        inted_bit = int(bit_array[j])
        bit_sum_list[j] += inted_bit
        bit_list[i].append(inted_bit)
        
ans = 0

for i in range(N-1):    
    for j in range(max_bit):
        if bit_list[i][j] == 0:
            ans += bit_sum_list[j] * 2**(max_bit - j - 1)
        elif bit_list[i][j] == 1:
            ans += (N - i - bit_sum_list[j]) * 2**(max_bit - j - 1)
            bit_sum_list[j] -= 1
            
        ans %= MOD_BY
            
print(ans)