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: Runtime Error

Solution code:
#D
import numpy as np
N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N-1):
    B=np.full(len(A)-i-1,A[i])
    C=np.bitwise_xor(A[i+1:],B)
    ans+=np.sum(C)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
import itertools

input = sys.stdin.readline

n = int(input())
a_s = [0] * n
xss = []
yss = []
for i in range(n):
	a_s[i] = int(input())
	xss.append([])
	yss.append([])
	for _ in range(a_s[i]):
		x, y = map(int, input().split())
		xss[i].append(x)
		yss[i].append(y)

# print(xss)
# print(yss)

tmp_shojiki = [True] * n
for i in range(n):
	for shojiki in set(itertools.permutations(tmp_shojiki)):
		# print(i, shojiki)
		all_shojiki = True
		for j in range(n):
			if not shojiki[j]:
				continue
			for k in range(a_s[i]):
				x, y = xss[j][k] - 1, yss[j][k]
				if y == 1:
					if shojiki[x] == False:
						all_shojiki = False
				else:
					if shojiki[x] == True:
						all_shojiki = False
		if all_shojiki:
			print(n - i)
			sys.exit()

	tmp_shojiki[i] = False

print(0)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int, input().split()))
a = [bin(A[i]) for i in range(len(A))]
ans = []
anser = 0

for i in range(len(a)):
    for j in a[i]:
        a[i] = a[i].lstrip('0b')

for i in range(len(a)):
     a[i] = int(a[i])


for i in range(len(a)-1):
    for j in range(i+1, len(a)):
        ans.append(a[i]^a[j])

ans = [str(ans[i]) for i in range(len(ans))]
ans = [int(ans[i], 2) for i in range(len(ans))]

ans = sum(ans)

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

Submission status: Runtime Error

Solution code:
def xor(x,y):
  if x==y:
    return 0
  elif (x=1 and y=0) or (x=0 and y=1):
    return 1
  else:
    return 0
def XOR(x,y):
  X=str(bin(x))
  Y=str(bin(y))
  MA=max(len(X),len(Y))
  MI=min(len(X),len(Y))
  ans=[0 for i in range(MA)]
  if len(X)>len(Y):
    B=X
  else:
    B=Y
  i=1
  while i<=MA:
    if i<=MI:
      ans[MA-i]=xor(X[MA-i],Y[MA-i])
    else:
      ans[MA-i]=B[MA-i]
  ANS=str(1)
  for i in range(1,MA):
    ANS+=ans[i]
  ANS=int('ANS',2)
  return ANS
N=int(input())
A=list(map(int,input().split()))
c=0
for i in range(N-1):
  for p in range(i+1,N+1):
    c=(c+XOR(A[i],A[p]))%(10**9+7)
print(c)

Submission status: Runtime Error

Solution code:
def main():
    num = input()
    num_list = list(map(int, input().split(" ")))
    # result = sum([sum([num_list[i]^num_list[j] for j in range(i)]) for i in range(int(num))])
    result = 0
    for i in range(int(num)):
        for j in range(i):
            result += sum(num_list[i]^num_list[j])
    print(result%(10**9+7))    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
keta=[0 for i in range(n)]
ans=0
for i in range(n):
  b=a[i]
  cnt=0
  while(b>=1):
    if b%2==1:
      keta[cnt]+=1
    b=b//2
    cnt+=1
#print(keta)
for i in range(len(keta)):
  #print(keta[i])
  ans+=keta[i]*(n-keta[i])*(2**i)
print(ans)

Submission status: Runtime Error

Solution code:
%%time
from functools import reduce
from operator import xor

A_arr = list(map(int, input().split()))

res = 0
for i,Ai in enumerate(A_arr[:-1]):
    res += sum(map(lambda yj: Ai ^ yj, A_arr[i+1:]))
print(res%(10**9 + 7))

Submission status: Runtime Error

Solution code:
import math
from math import factorial

p = 10 ** 9 + 7
def cmb(n):
  a = n % p
  b = (n - 1) % p
  return(int((a * b / 2)) % p)

n = input()
a = input().split(" ")

a = [int(i) for i in a]

bmax = math.ceil(math.log2(max(a)))

r = 0

for j in range(bmax):
  b = [k & (2 ** j) for k in a] # 各ビットを取り出す
  b = [int(k != 0) for k in b]
  n_tot = len(b)
  n_one = sum(b)
  n_zero = n_tot - n_one
  r_tmp = cmb(n_tot) - (cmb(n_zero) + cmb(n_one))
  b_tmp = (2 ** j) % p
  r = r + ((r_tmp * b_tmp) % p)
  
print(r % p)

Submission status: Runtime Error

Solution code:
import numpy as np

n=int(input())

a=[]

for i in range(n):
    k=int(input())
    a.append(k)

ans=0
for i in range(n-1):
    for k in range(i,n):
        tmp=a[i]^a[k]
        #print(tmp)
        ans=(ans+tmp)%1000000007

print(ans)

Submission status: Runtime Error

Solution code:
def sumXOR( arr,  n): 
      
    sum = 0
    for i in range(0, 32): 
  
        #  Count of zeros and ones 
        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] = int(arr[j] / 2) 
          
           
        # calculating individual bit sum  
        idsum = oc * zc * (1 << i) 
   
        # final sum     
        sum = sum + idsum;  
      
    return sum
  
  
  
# driver function  
sum = 0
arr = []
a=0
n=int(input())
for i in range(n):
  a=int(input())
  ar.append(a)
sum = sumXOR(arr, n); 
print (sum)

Submission status: Runtime Error

Solution code:
import math
from math import factorial

p = 10 ** 9 + 7
def comb(n,k):
  """power_funcを用いて(nCk) mod p を求める"""
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2)*power_func(c,p-2))%p
def power_func(a,b):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1))%p

n = input()
a = input().split(" ")

a = [int(i) for i in a]

bmax = math.ceil(math.log2(max(a)))

r = 0

for j in range(bmax):
  b = [k & (2 ** j) for k in a] # 各ビットを取り出す
  b = [int(k != 0) for k in b]
  n_tot = len(b)
  n_one = sum(b)
  n_zero = n_tot - n_one
  r_tmp = comb(n_tot, 2) - (comb(n_zero, 2) + comb(n_one, 2))
  b_tmp = (2 ** j) % p
  r = r + ((r_tmp * b_tmp) % p)
  
print(r % p)

Submission status: Runtime Error

Solution code:
# An efficient Python3 program to compute 
# sum of bitwise OR of all pair 

# Returns sum of bitwise OR 
# of all pairs 
mod=1000000007
def sumXOR( arr, n): 
	
	sum = 0
	for i in range(0, 60): 

		# Count of zeros and ones 
		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] = int(arr[j] / 2) 
		
		
		# calculating individual bit sum 
		curr=(oc*zc)%mod
		idsum = (curr * ((1 << i)%mod))%mod
		# final sum	 
		sum = (sum + idsum) )%mod
	
	return sum%mod



# driver function 
sum = 0
n=int(input())
arr = list(map(int,input().split())) 
for i in range(n):
    arr[i]=arr[i]
sum = sumXOR(arr, n); 
print (sum) 

# This code is contributed by saloni1297

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A=list(map(int,input().split()))
l=[0]*59
for i in A:
    s=str(bin(i))[2:]
    for j in range(len(s)):
        if s[-j-1]=="1":
            l[j]+=1
a=0
for i in range(59):
    a=(a+2**i*l[i]*(N-l[i]))%(10**9+7)
print(a)

Submission status: Runtime Error

Solution code:
import itertools
import numpy

S = int(input())
a = [int(i) for i in input().split()]

xor = 0
patern = list(itertools.combinations(a, 2))
for p in patern:
    xor += p[0] ^ p[1]
if xor >= 10 ** 9:
    print(np.mod(xor, (10 ** 9 + 7)))
else:
    print(xor)

Submission status: Runtime Error

Solution code:
n = input()
ans = 0
arr=[]
    for i in range(0,n):
        for j in range(i+1,n):
            ans = ans + (arr[i] ^ arr[j])
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
import numpy as np
A = np.array(A)
B = A[:, np.newaxis]
x = np.sum(A^B)//2
print(x % (10**9 + 7))

Submission status: Runtime Error

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

import numba
@numba.jit
def calc(N, A):
    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            ans += A[i] ^ A[j]

    ans = ans % (INF + 7)
    return ans

print(calc(N, A))

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
import numpy as np
A = np.array(A)
B = A[:, np.newaxis]
x = np.sum(A^B)//2
if x >= 10**9 + 7:
  print(x % (10**9 + 7))
else:
  print(x)

Submission status: Runtime Error

Solution code:
input itertools
count = int(input())
waru = 10**9 + 7
intlist = list(map(int,input().split()))
sum = 0
kumi = list(itertools.combinations(intlist,2))
for i in range(len(kumi)):
    sum+=kumi[i][0]^kumi[i][1]
print(sum%waru)

Submission status: Runtime Error

Solution code:
def solve():
    import numpy as np
    ans=0
    for i in range(n-1):
        for j in range(i+1,n):
            ans+=a[i]^a[j]
    
    print(ans%(10**9+7))
    
n=int(input())
a=np.array(list(map(int,input().split())) )
solve()

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = np.array([int(i) for i in input().split()])
B = A[:, np.newaxis]
x = np.sum(A^B)//2
if x >= 10**9 + 7:
  print(x % (10**9 + 7))
else:
  print(x)

Submission status: Runtime Error

Solution code:
input itertools
count = int(input())
waru = 10**9 + 7
intlist = list(map(int,input().split()))
sum = 0
kumi = list(itertools.combinations(intlist,2))
for i in range(count):
    sum+=kumi[i][0]^kumi[i][1]
print(sum%waru)

Submission status: Runtime Error

Solution code:
a=int(input())
b=list(map(int,input().split()))
s=0
for i in range(len(b)):
  for j in range(i+1,len(b)):
    s=(s+b[i]^x[j])%(1e19+7)
print(s)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

const long long int MODN = (long long int)(1e9+7);
long long int sumXOR(long long int arr[], int n) 
{ 
    long long int sum = 0; 
    for (int i = 0; i < 64; i++)  
    { 
        long long int zc = 0, oc = 0;  
          
        long long int idsum = 0;  
        for (int j = 0; j < n; j++) 
        { 
            if (arr[j] % 2 == 0) 
                zc++; 
            else
                oc++; 
            arr[j] /= 2; 
        } 
          
        idsum = ((((oc%MODN) * (zc%MODN))%MODN) * ((1L << i)%MODN))%MODN;  
  
        sum += idsum;  
        sum %= MODN;
    } 
    return sum; 
} 

int main() {
  long long int N;
  scanf("%lld",&N);
  long long int arr[N];
  for (int i=0;i<N;i++) {
    scanf("%lld",&arr[i]);
  }
  printf("%lld\n",sumXOR(arr,N));
}

Submission status: Runtime Error

Solution code:
import math

N = int(input())
A = [int(i) for i in input().split()]
digs = int(math.log(max(A), 2)+1)
count = [0] * digs

for i in range(N):
    A_bit = format(A[i], 'b')
    for j in range(len(A_bit)):
        if A_bit[len(A_bit)-1-j] == '1':
            count[j] += 1
total = 0
for i in range(digs):
    total += 2**i * count[i] * (N - count[i])
    
print(total % 1000000007)

Submission status: Runtime Error

Solution code:
import math

n=int(input())
alist = [int(i) for i in input().split()]
alist=sorted(alist)

keta=math.floor(math.log2(alist[-1]))+1
#print(math.log2(alist[-1]), keta)
zeros=[0]*keta
ones=[0]*keta

for al in alist:
    kaz2=bin(al)[2:]
    kaz2=(keta-len(kaz2))*'0'+kaz2
    #print(kaz2)
    for i in range(keta):
        if kaz2[i]=='1':
            ones[i]+=1
        else:
            zeros[i]+=1

#print(ones)
#print(zeros)
answer=0
for i in range(keta):
    tas=ones[-i-1]*zeros[-i-1]
    tas*=((2**i)%(10**9+7))
    answer+=tas%(10**9+7)

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