Problem:


Score : 400 points

Problem Statement

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

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

What is \mbox{ XOR }?

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

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

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

Constraints

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

0 \leq A_i < 2^{60}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

3
1 2 3

Sample Output 1

6

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

Sample Input 2

10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

237

Sample Input 3

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

Sample Output 3

103715602

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



Sample input:
3
1 2 3


Sample output:
6

Submission status: Time Limit Exceeded

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

zero_each_dig = [0 for _ in range(60)]
one_each_dig = [0 for _ in range(60)]

for i in range(n):
     for j in range(60):
        if (A[i] >> j) & 1 == 1:
            one_each_dig[j] += 1
        else:
            zero_each_dig[j] += 1

Multi = []
for k in range(60):
    Multi.append(zero_each_dig[k] * one_each_dig[k] * (2**k) % (10**9 +7))

ans = sum(Multi) % (10**9 +7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input().split()
n=int(s[0])
s = input().split()
ans = 0
for i in range(len(bin(int(max(s))))-2):
    count_0=0
    count_1=0
    for j in s:
        if len(bin(int(j)))>i+2:
            if bin(int(j))[len(bin(int(j)))-1-i] == '0':
                count_0+=1
            else:
                count_1+=1
        else:
            count_0+=1
    ans+=(count_0*count_1)*2**i

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
suma = 0
maxa = max(A)
bin = format(maxa,'b')
for i in range(len(bin)):
    count1 = 0
    for j in range(N):
        if (A[j] >> i) & 1 == 1:
            count1 += 1
    suma = (suma+(N-count1)*count1*((2**i))%(10**9+7))%(10**9+7)
print(suma)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
suma = 0
maxa = max(A)
bin = format(maxa,'b')
for i in range(len(bin)):
    count1 = 0
    for j in range(N):
        if (A[j] >> i) & 1 == 1:
            count1 += 1
    suma = (suma+(N-count1)*count1*(2**i))%(10**9+7)
print(suma)

Submission status: Time Limit Exceeded

Solution code:
s = input().split()
n=int(s[0])
s = input().split()

ans = 0
for i in range(n-1):
    for j in range(int(i+1),n):
        ans += int(s[i]) ^ int(s[j])

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

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(62):
    cnt=0
    for j in range(n):
        cnt+=(A[j]>>i)&1
    ans+=cnt * (n-cnt) *(2**i)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
ml = len(bin(max(a)))-2
ans = 0
for i in range(ml):
  x = sum([1 for j in range(n) if ((a[j]>>i) & 1)])
  ans += x*(n-x)*(2**i)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
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:
N = int(input())
A= list(map(int,input().split()))
MOD = 10**9+7
digN = 60
binA = [bin(A[i])[2:].zfill(digN) for i in range(N)]
cnt_digs = [0 for _ in range(digN)]
for i in range(N-1):
  for j in range(i+1,N):
    k = 0
    for a1,a2 in zip(binA[i], binA[j]):
      if a1 != a2:
        cnt_digs[k] += 1
      k += 1
ans = 0
mods = []
for i in range(digN):
  if i == 0:
    mods.append(2**i)
  else:
    mods.append((mods[i-1]*2)%MOD)

for i, cnt_dig in enumerate(cnt_digs):
  ii = digN - i - 1
  if cnt_dig != 0:
    ans += (mods[ii]*cnt_dig)%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A= list(map(int,input().split()))
MOD = 10**9+7
digN = 60
binA = [bin(A[i])[2:].zfill(digN) for i in range(N)]
cnt_digs = [0 for _ in range(digN)]
for i in range(N-1):
  for j in range(i+1,N):
    k = 0
    for a1,a2 in zip(binA[i], binA[j]):
      if a1 != a2:
        cnt_digs[k] += 1
      k += 1
ans = 0
for i, cnt_dig in enumerate(cnt_digs):
  ii = digN - i - 1
  if cnt_dig != 0:
    ans += ((2**ii)*cnt_dig)%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
a=[int(i) for i in input().split()]
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  t=1<<k
  for i in range(n):
    if a[i]&t:
      x+=1
  c=x*(n-x)*2**k
  ans+=c
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
#python3
#python3
import numpy as np
n=int(input())
a=np.array([int(i) for i in input().split()])
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  t=1<<k
  for i in range(n):
    if a[i]&t:
      x+=1
  c=x*(n-x)*2**k
  ans+=c
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
#python3
#python3
import numpy as np
n=int(input())
a=np.array([int(i) for i in input().split()])
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  for i in range(n):
    if(a[i]>>k)&1:
      x+=1
  ans+=x*(n-x)*2**k
  ans%=MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
dig=1
ans=0
m=max(a)
k=0
mod=10**9+7
while m>>k >0:
    k+=1
k=max(0,k)
for j in range(k):
    cnt=0
    for i in range(n):
        if a[i]>>j & 1:
            cnt+=1
    cnt=cnt*(n-cnt)%mod
    ans=(ans+dig*cnt%mod)%mod
    dig=dig*2%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#python3
#python3
import numpy as np
n=int(input())
a=np.array([int(i) for i in input().split()])
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  for i in range(n):
    if(a[i]>>k)&1:
      x+=1
  c=x*(n-x)*2**k
  ans+=c
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
#python3
#python3
import numpy as np
n=int(input())
a=np.array([int(i) for i in input().split()])
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  for i in range(n):
    if(a[i]>>k)&1:
      x+=1
  ans+=x*(n-x)*2**k
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
#python3
n=int(input())
a=[int(i) for i in input().split()]
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  for i in range(n):
    if(a[i]>>k)&1:
      x+=1
  contribute = x*(n-x)*(1<<k)
  ans+=contribute
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
#python3
n=int(input())
a=[int(i) for i in input().split()]
MOD = int(1e9+7)
ans=0
for k in range(60):
  x=0
  for i in range(n):
    if(a[i]>>k)&1:
      x+=1
  contribute = x*(n-x)*2**k
  ans+=contribute
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
#!python3

def resolve():
    N = int(input())
    A = tuple(map(int, input().rstrip().split()))

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for k in range(61):
    o = 0
    for i in range(N):
        if A[i]>>k &1:o+=1
    ans+=(2**k)*o*(N-o)
print(ans%(10**9+7))

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(61):
    one = 0
    zero = 0
    for i in range(N):
        if A[i]%2==0:zero+=1
        else:one+=1
        A[i]//=2
    ans += (one*zero)*(2**k)
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)
        

n = int(input())
a = np.array(list(map(int,input().split())))
b = np.array([0] * 60)
for i in range(n):
  tmp = a[i]
  for j in range(60):
    x = tmp%2
    if x == 1:
      b[j] += 1
    tmp //= 2
tmp = ModInt(1)
ans = ModInt(0)
for i in range(60):
    s = ModInt((n-b[i])*b[i])
    ans += s*tmp
    tmp *= 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)
        

n = int(input())
a = list(map(int,input().split()))
b = [0] * 60
for i in range(len(a)):
  tmp = a[i]
  for j in range(60):
    x = tmp%2
    if x == 1:
      b[j] += 1
    tmp //= 2
tmp = ModInt(1)
ans = ModInt(0)
for i in range(60):
    s = ModInt((n-b[i])*b[i])
    ans += s*tmp
    tmp *= 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

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

A = np.array(A,np.int64)##Ai<2^60

ans = 0
mod = int(1e9+7)

for i in range(60+1):
    bottom_bit = (A>>i)&1 ##i回シフトしたときの最下位bit
    ones = sum(bottom_bit[bottom_bit>0])
    ##ans += (N-ones)*ones*(2**i) ##0の個数*1の個数*2^i個
    tmp = ones*(N-ones)
    for j in range(i):
        tmp = (tmp * 2) % mod
    ans += tmp

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

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

##A = np.array(A,np.int64)##Ai<2^60

ans = 0
mod = int(1e9+7)

for i in range(60+1):
    bottom_bit = (A>>i)&1 ##i回シフトしたときの最下位bit
    ones = sum(bottom_bit[bottom_bit==1])
    ##ans += (N-ones)*ones*(2**i) ##0の個数*1の個数*2^i個
    tmp = ones*(N-ones)
    for j in range(i):
        tmp = (tmp * 2) % mod
    ans += tmp

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

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

A = np.array(A,np.int64)##Ai<2^60

ans = 0
mod = int(1e9+7)

for i in range(60+1):
    bottom_bit = (A>>i)&1 ##i回シフトしたときの最下位bit
    ones = sum(bottom_bit[bottom_bit==1])
    ##ans += (N-ones)*ones*(2**i) ##0の個数*1の個数*2^i個
    tmp = ones*(N-ones)
    for j in range(i):
        tmp = (tmp * 2) % mod
    ans += tmp

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += A[i] ^ A[j]

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
mod=10**9+7
for k in range(60):
    count=0
    for a in A:
        count+=int(a&(1<<k)>0)
    ans+=count*(N-count)*(2**k)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
mod=10**9+7
for k in range(60):
    count=sum([int(bin(a)[2:].zfill(60)[k]) for a in A])
    ans+=count*(N-count)*(2**(60-k-1))
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=[bin(a)[2:].zfill(60) for a in A]
ans=0
mod=10**9+7
for k in range(60):
    count=sum([int(a[k]) for a in A])
    ans+=count*(N-count)*(2**(60-k-1))
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += A[i] ^ A[j]
ans = ans % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random
N = int(input())
As = [int(i) for i in input().split(" ")]
Nmax = len(format(max(As),"b"))

total = 0
for k in range(Nmax):
    
    o = 0
    z = 0
    
    for i in range(N):
        
        # k桁を取り出す
        ai_k = As[i] >> k & 1
        
        # 0と1の個数を数える
        if ai_k == 0:
            o += 1
        else:
            z += 1
        
    total += (2**k)*o*z
    
print(total%int(1e9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_n = list(map(int, input().split()))
result = 0

for i in range(N-1):
    for j in range(i+1, N):
        result += int(bin(A_n[i] ^ A_n[j]), 2)
print(result % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

Nmax = len(format(max(As),"b"))

total = 0
for k in range(Nmax):
    
    counter = [0,0]
    
    for i in range(N):
        
        # k桁を取り出す
        ai_k = As[i] >> k & 1
        
        # 0と1の個数を数える
        counter[ai_k] += 1
    
    total += (2**k)*counter[0]*counter[1]
    
print(total%int(1e9+7))

Submission status: Time Limit Exceeded

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

total = 0
for i in range(N):
    for j in range(i+1,N):
        
        total += As[i]^As[j]
        
print(total%(int(1e9+7)))

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [A[i][59-k] for i in range(N)]
  v = s.count('0')*s.count('1')
  S += (v<<k)
S %= mod
print(S)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [A[i][59-k] for i in range(N)]
  v = s.count('0')*s.count('1')
  S += (v<<k) % mod
  S %= mod
S %= mod
print(S)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
j = 1
for k in range(60):
  s = [A[i][59-k] for i in range(N)]
  v = s.count('0')*s.count('1')
  S += (v * j) % mod
  j *= 2
  j %= mod
  S %= mod
S %= mod
print(S)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
S = 0
j = 1
for c in range(61):
  m = 0
  n = 0
  for i in range(N):
    if A[i] % 2 == 1:
      m += 1
    else:
      n += 1
    A[i] //= 2
  S += ((m * n) * j) % mod
  j *= 2
  j %= mod
  S %= mod
S %= mod
print(S)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
S = 0
j = 1
Z = [0 for i in range(N)]
while A != Z:
  m = 0
  n = 0
  for i in range(N):
    if A[i] % 2 == 1:
      m += 1
    else:
      n += 1
    A[i] //= 2
  S += ((m * n) * j) % mod
  j *= 2
  j %= mod
  S %= mod
S %= mod
print(S)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
S = 0
j = 1
while A != [0 for i in range(N)]:
  m = 0
  n = 0
  for i in range(N):
    if A[i] % 2 == 1:
      m += 1
    else:
      n += 1
    A[i] //= 2
  S += (m * n) * j
  S %= mod
  j *= 2
S %= mod
print(S)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
mask = 1
ret = 0
for i in range(70):
    on = 0
    off = 0
    for a in A:
        if a & mask:
            on += 1
        else:
            off += 1
    ret += (on * off) * mask
    ret %= MOD
    mask *= 2

print(ret)

Submission status: Time Limit Exceeded

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

l.sort(reverse=True)
kmax = len(format(l[0], 'b'))

l0 = [0]*kmax
l1 = [0]*kmax

for i in range(n):
  a = format(l[i], 'b')
  a = ''.join(list(reversed(a)))
  for j in range(kmax):
    if j > len(a)-1:
      l0[j] += 1
    elif a[j] == '0':
      l0[j] += 1
    else:
      l1[j] += 1

ans = 0
for k in range(kmax):
  ans += l0[k]*l1[k]*(2**k)
  ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

MOD = 10**9 + 7
N = int(input())
A = [int(i) for i in input().split()]


def main():
    ans = sum([a ^ b for (a, b) in itertools.combinations(A, 2)]) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''input
3 5
1 2 1
2 3 0
'''
# connected components
from sys import stdin, setrecursionlimit
from bisect import bisect_left
import sys, threading
from collections import defaultdict


def power(a, x, mod):
    if x == 0:
        return 1
    temp = power(a, x//2, mod) % mod
    if x % 2:
        return ((temp * temp) % mod * a) % mod
    else:
        return ((temp * temp)% mod)


# main starts
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
ans = 0
mod = 10 ** 9 + 7
for i in range(60):
    num = 1 << i
    count = 0
    for k in range(n):
        if num & arr[k] == 0:
            count += 1
    # print(num, count, n - count)
    ans += (power(2, i, mod) *(count * (n - count)) % mod) % mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0] * 60
for i in range(len(a)):
  tmp = a[i]
  for j in range(60):
    x = tmp%2
    if x == 1:
      b[j] += 1
    tmp //= 2
tmp = 1
ans = 0
for i in range(60):
  s = (n-b[i])*b[i]
  ans += s*tmp
  ans %= 1000000007
  tmp *= 2
  tmp %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0] * 60
for i in range(len(a)):
  tmp = a[i]
  for j in range(60):
    x = tmp%2
    if x == 1:
      b[j] += 1
    tmp //= 2
tmp = 1
ans = 0
for i in range(60):
  s = (n-b[i])*b[i]
  ans += s*tmp
  ans %= 1000000007
  tmp *= 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
su=0
#a=[]
#for i in range(1,n):
#    c=int(input())
#    a.append(c) 
for i in range (n-1):
    for j in range(i+1,n):
        su+=a[i]^a[j]
print(su%(1000000000+7))

Submission status: Time Limit Exceeded

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

def get_bit_count(digit, A):
    bit_count = 0
    for a in A:
        bit = (a >> digit) & 1
        bit_count += bit
    return bit_count

def get_bit_counts(A, MAXBIT = 60):
    bitcount = [0 for i in range(MAXBIT)]  # x < 2**60
    for a in A:
        for i in range(MAXBIT):
            bitcount[i] = get_bit_count(i, A)
    return bitcount


def solve(N, A, MOD=1000000007):
    answer = 0
    for i in range(len(A)):
        left_counts = get_bit_counts(A[i:i+1])
        right_counts = get_bit_counts(A[i+1:])
        for d, (l, r) in enumerate(zip(left_counts, right_counts)):
            if l == 0:
                adder = r << d
            else:
                adder = (len(A[i+1:]) - r) << d
            answer = (answer + adder) % MOD
    return answer

if __name__ == '__main__':
    inputs = read()
    print('%d' % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
As=LI()

DIG_CUM = [[0]*60 for _ in range(N+1)]

for i in range(N):
    for s in range(60):
        DIG_CUM[i+1][s] = DIG_CUM[i][s] + ((As[i] >> s) & 1)

# for arr in DIG_CUM:
#     print(arr)

res = 0
for i in range(N-1):
    for s in range(60):
        coef = (N - i - 1 - (DIG_CUM[N][s] - DIG_CUM[i+1][s])) if (As[i] >> s) & 1 else DIG_CUM[N][s] - DIG_CUM[i+1][s]
        res += coef * (1 << s)
        res %= DVSR
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
As=LI()

DIG_CUM = [[0]*60 for _ in range(N+1)]

for i in range(N):
    for s in range(60):
        DIG_CUM[i+1][s] = DIG_CUM[i][s] + ((As[i] >> s) & 1)

# for arr in DIG_CUM:
#     print(arr)

res = 0
for i in range(N-1):
    for s in range(60):
        coef = (N - i - 1 - (DIG_CUM[N][s] - DIG_CUM[i+1][s])) if (As[i] >> s) & 1 else DIG_CUM[N][s] - DIG_CUM[i+1][s]
        res += coef * (1 << s)
    res %= DVSR
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
cnt = [0]*(66)
for num in a:
    for j in range(60):
        cnt[j] += (num >> j)%2
ans = 0
for b in range(60):
    ans += (cnt[b]*(n-cnt[b])) << b
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


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

    digits_ct = [(0, 0) for _ in range(65)]

    for A in AN:
        temp = A

        length = 0
        for _ in range(65):
            digit = temp & 0b1

            zero, one = digits_ct[length]
            if digit == 0:
                digits_ct[length] = (zero + 1, one)
            else:
                digits_ct[length] = (zero, one + 1)

            temp = temp >> 1
            length += 1

    ans = 0
    radix = 1
    for digit_ct in digits_ct:
        zero, one = digit_ct
        ans += (((zero * one) % MOD) * radix) % MOD
        ans = ans % MOD

        radix *= 2

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
bite = [0 for _ in range(60)]
for A in A_list:
    for i in range(60):
        if A & 1 << i:
            bite[i] += 1

ans = 0
on_right = N - 1
for num in range(len(A_list)):
    A = A_list[num]
    for i in range(60):
        if A & 1 << i:
            bite[i] -= 1
            ans += (on_right - bite[i]) * 1 << i
        else:
            ans += bite[i] * 1 << i
    on_right -= 1

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

Submission status: Time Limit Exceeded

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

D = defaultdict(int)
for a in A:
    for i in range(61):
        D[1 << i] += bool(a & (1 << i))

ans = 0
for key, value in D.items():
    ans += ((key * value) % MOD) * (N - value) % MOD
    ans %= MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

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

D = defaultdict(int)
for a in A:
    for i in range(61):
        D[1 << i] += bool(a & (1 << i))

ans = 0
for key, value in D.items():
    ans += key * value * (N - value)
    ans %= MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

# numpy and scipy are available for use
import numpy
import scipy
#https://atcoder.jp/contests/abc147/tasks/abc147_d
#Xor Sum 4
"""
iterate over bits
1. calculate how many bits we have on that position
2. for each 1, we need to add num 0s * num 1s * 2s
3. sum them up

This version has TLE
"""

# reads a single line
N = gi()
a = [0] * N

max_v = 0
for i in range(N):
    a[i] = gi()
    max_v = max(max_v, a[i])

ans = 0
for shift in range(60):
    base = 1 << shift
    if (base > max_v):
        break
    n1 = 0
    for ai in a:
        if (ai & base):
            n1 += 1

    part = n1 * (N - n1)
    part %= MOD
    part *= base
    part %= MOD
    ans += part
    ans %= MOD

print(ans)