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: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)
ans = 0
POW = 1
for j in range(60):
  tmp = A & 1
  one = np.count_nonzero(tmp)
  zero = N - one
  ans = (ans + (one * zero * POW)) % MOD
  A >>= 1
  POW = (POW<<1)%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
bit = [0] * 60
for i in range(N):
  n = bin(A[i])
  for j in range(len(n)-1, 1, -1):
    bit[len(n)-j-1] += int(n[j])
ans = 0
POW = 1
for j in range(60):
  ans = (ans +bit[j]*(N-bit[j])*POW)%MOD
  POW = (POW * 2)%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
'''ika tako
bit桁ごとに考える。「XORを取り、その後足し算」という計算過程では
他の桁が影響することはないので、桁毎に独立に考えて問題ない。
N = 5
A = {   1   2   3   4   5 }   ↓
    { 001 010 011 100 101 }
たとえば2桁目を取り出すと
       0   1   1   0   0
各ペアでXORを取ると、(0,1)は'1'となり、(0,0)(1,1)は'0'となる。 
0はいくら足しても0なので、(0,1)の数だけわかれば良い。
それは、(0の個数)×(1の個数)で計算できる。
    0が3個、1が2個
→  XORを取ったとき、2桁目について'1'が立っているペア
　　　　　　　　　　　=合計に足される回数は 3x2=6
→  2進数の2桁目は2を表すので、合計に足される値は6x2=12
これを各桁について足し合わせる。
'''
n = int(input())
aaa = list(map(int, input().split())) 
MOD = 10 ** 9 + 7
ans = 0
m = 1#取り出したい桁、これを１つずつ増やしていく
for i in range(60):#上限は2＾60なので、60が上限
    bit = sum(a & m for a in aaa)
    #＆演算子は論理積、両方のビットが1の場合に1が返る
    #L=[a for a in aaa]  与えられたN個の整数を全列挙
    #この整数の各ビットをチェックする
    #print(L)
    #bit //= m こっちが原文、下の行は、下のプログラムに合わせてみた
    bit >>= i
    #print(bit)
    non_bit = n - bit
    ans = (ans + bit * non_bit * m) % MOD
    #ｍは上記、2桁目を表す2と同様、取り出した桁がpだとすると2^(p-1)
    m <<= 1#ビットを１つずつ左シフト、取り出したい桁をずらして求める
print(ans)
'''
結局この計算は Ai のすべての組み合わせ(Ai 自身同士は含まない)の 
XOR の合計なので、Ai のあるビットの立っている数の合計を c とすると、
Ai のあるビットが0であった場合により計算結果に立つビットの数は 
c、Ai のあるビットが1であった場合により計算結果に立つビットの数は 
N - c になるので、あるビットに関する計算結果は c * (N -c) の
ビットシフトした値になる. 結果として以下の計算で解ける.
N = int(input())
A = list(map(int, input().split())) 
result = 0
for bit in range(60):
    m = 1 << bit　すべてのビットを調べる
    c = sum(a & m for a in A) >> bit　
    ビット分、戻して、その桁に立っているビット数を算出
    result += (c * (N - c)) << bit　
    ビット分（上記の2桁目の2）調整、イメージとしては2のべき乗倍
    result %= 1000000007
print(result)
'''

Submission status: Accepted

Solution code:
'''ika tako
bit桁ごとに考える。「XORを取り、その後足し算」という計算過程では
他の桁が影響することはないので、桁毎に独立に考えて問題ない。
N = 5
A = {   1   2   3   4   5 }   ↓
    { 001 010 011 100 101 }
たとえば2桁目を取り出すと
       0   1   1   0   0
各ペアでXORを取ると、(0,1)は'1'となり、(0,0)(1,1)は'0'となる。 
0はいくら足しても0なので、(0,1)の数だけわかれば良い。
それは、(0の個数)×(1の個数)で計算できる。
    0が3個、1が2個
→  XORを取ったとき、2桁目について'1'が立っているペア
　　　　　　　　　　　=合計に足される回数は 3x2=6
→  2進数の2桁目は2を表すので、合計に足される値は6x2=12
これを各桁について足し合わせる。
'''
n = int(input())
aaa = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
ans = 0
m = 1
for i in range(60):#上限は2＾60なので、60が上限
    bit = sum(a & m for a in aaa)
    #＆演算子は論理積、両方のビットが1の場合に1が返る
    #L=[a for a in aaa]  与えられたN個の整数を全列挙
    #print(L)
    #bit //= m こっちが原文、下の行は、下のプログラムに合わせてみた
    bit >>= i
    #print(bit)
    non_bit = n - bit
    ans = (ans + bit * non_bit * m) % MOD
    #ｍは上記、2桁目を表す2と同様
    m <<= 1#ビットを１つずつ左シフト
print(ans)

'''
結局この計算は Ai のすべての組み合わせ(Ai 自身同士は含まない)の 
XOR の合計なので、Ai のあるビットの立っている数の合計を c とすると、
Ai のあるビットが0であった場合により計算結果に立つビットの数は 
c、Ai のあるビットが1であった場合により計算結果に立つビットの数は 
N - c になるので、あるビットに関する計算結果は c * (N -c) の
ビットシフトした値になる. 結果として以下の計算で解ける.

N = int(input())
A = list(map(int, input().split()))
 
result = 0
for bit in range(60):
    m = 1 << bit　すべてのビットを調べる
    c = sum(a & m for a in A) >> bit　
    ビット分、戻して、その桁に立っているビット数を算出
    result += (c * (N - c)) << bit　
    ビット分（上記の2桁目の2）調整、イメージとしては2のべき乗倍
    result %= 1000000007
print(result)
'''

Submission status: Accepted

Solution code:
'''ika tako
bit桁ごとに考える。「XORを取り、その後足し算」という計算過程では
他の桁が影響することはないので、桁毎に独立に考えて問題ない。
N = 5
A = {   1   2   3   4   5 }   ↓
    { 001 010 011 100 101 }
たとえば2桁目を取り出すと
       0   1   1   0   0
各ペアでXORを取ると、(0,1)は'1'となり、(0,0)(1,1)は'0'となる。 
0はいくら足しても0なので、(0,1)の数だけわかれば良い。
それは、(0の個数)×(1の個数)で計算できる。
    0が3個、1が2個
→  XORを取ったとき、2桁目について'1'が立っているペア
　　　　　　　　　　　=合計に足される回数は 3x2=6
→  2進数の2桁目は2を表すので、合計に足される値は6x2=12
これを各桁について足し合わせる。
'''
n = int(input())
aaa = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
ans = 0
m = 1
for i in range(60):#上限は2＾60なので、60が上限
    bit = sum(a & m for a in aaa)#ｍは何番目のビットが立っているか
    #bit //= m こっちが原文、下の行は、下のプルグラムに合わせたみた
    bit >>= i
    non_bit = n - bit
    ans = (ans + bit * non_bit * m) % MOD
    #ｍは上記、2桁目を表す2と同様
    m <<= 1#ビットを１つずつ左シフト
print(ans)

'''
結局この計算は Ai のすべての組み合わせ(Ai 自身同士は含まない)の 
XOR の合計なので、Ai のあるビットの立っている数の合計を c とすると、
Ai のあるビットが0であった場合により計算結果に立つビットの数は 
c、Ai のあるビットが1であった場合により計算結果に立つビットの数は 
N - c になるので、あるビットに関する計算結果は c * (N -c) の
ビットシフトした値になる. 結果として以下の計算で解ける.

N = int(input())
A = list(map(int, input().split()))
 
result = 0
for bit in range(60):
    m = 1 << bit　すべてのビットを調べる
    c = sum(a & m for a in A) >> bit　
    ビット分、戻して、その桁に立っているビット数を算出
    result += (c * (N - c)) << bit　
    ビット分（上記の2桁目の2）調整、イメージとしては2のべき乗倍
    result %= 1000000007
print(result)
'''

Submission status: Accepted

Solution code:
n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 1000000007
n, *a = map(int, open(0).read().split())

ans = 0
w = 1
for i in range(61):
    zero = one = 0
    for j in range(n):
        if a[j]&1: one += 1
        else: zero += 1
        a[j] >>= 1;
    ans += w * zero * one
    ans %= MOD
    w = w * 2 % MOD
print(ans)

Submission status: Accepted

Solution code:
m=10**9+7

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

for i in range(60):
    x=0
    y=0
    for j in range(n):
        if (a[j]>>i)%2==1:
            x+=1
        else:
            y+=1
    ans+=(2**i) * (x*y)
print(ans%m)

Submission status: Accepted

Solution code:
m=10**9+7

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

b=max(a)
k=0

while b!=0:
    b=b//2
    k+=1

ans=0

for i in range(k):
    x=0
    y=0
    for j in range(n):
        if (a[j]>>i)%2==1:
            x+=1
        else:
            y+=1
    ans+=((2**i)%m) * ((x*y)%m)
print(ans%m)

Submission status: Accepted

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

ans = 0
twopow = 1
for n in range(60):
    tmp = A & 1
    one = np.count_nonzero(tmp)
    zero = N - one
    ans = (ans + (one * zero) * twopow) % MOD
    A >>= 1
    twopow = twopow << 1 % MOD

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
counts=[0]*60
for b in a:
    for i in range(60):
        counts[i]+=b%2
        b//=2
ans=0
mod = 10**9+7
for i in range(60):
    c=counts[i]
    comb=c*(n-c)
    ans=(ans+(1<<i)*comb)%mod
print(ans)

Submission status: Accepted

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

cnt = [0] * 60

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 %= MOD
print(ans)

Submission status: Accepted

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

blist=[0]*60
for a in alist:
  bblist=[]
  while a:
    bblist.append(a%2)
    a//=2
    
  #print(bblist)
  for i in range(len(bblist)):
    blist[i]+=bblist[i]
      
#print(blist)
answer=0
pow2=1
for i in range(60):
  answer+=blist[i]*(N-blist[i])*pow2
  answer%=MOD
  pow2=2*pow2%MOD
  
print(answer)

Submission status: Accepted

Solution code:
import sys
 
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())
 
def log(*args):
    print("DEBUG:", *args, file=sys.stderr)
 
def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]
 
def inv(x, MOD):
    return pow(x, MOD-2, MOD)
 
MOD = 10**9+7
 
n,*A = get_all_int()
 
pow2    = [1] * 61
pow2mod = [1] * 61
for i in range(1,61):
    pow2[i] = pow2[i-1] * 2
    pow2mod[i] = pow2[i] % MOD
 
# ビットごとの出現回数 2**i
bits = [0] * 60
 
for a in A:
    for i in range(60):
        if pow2[i] & a != 0:
            bits[i] += 1
 
ans = 0
 
for a in A:
    for i in range(60):
        ans += pow2mod[i] * abs(bits[i] - (1 if pow2[i] & a != 0 else 0) *n)
 
print(ans*inv(2,MOD) % MOD)

Submission status: Accepted

Solution code:
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

MOD = 10**9+7

n,*A = get_all_int()

pow2 = [1] * 61
for i in range(1,61):
    pow2[i] = pow2[i-1] * 2

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if pow2[i] & a != 0:
            bits[i] += 1

# その位のビットの1の個数*0の個数 が、そのビットがansに足される回数
ans = sum(( pow(2, i, MOD) * bits[i] * (n-bits[i]) for i in range(60))) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
import time

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

start = time.time()

MOD = 10**9+7

debug = False

if debug:
    n = 30 * 10000
    A = list(range(n))
else:
    n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)
# log("bits.", time.time() - start)

# ans = 0

ans = sum(( pow(2, i, MOD) * bits[i] * (n-bits[i]) for i in range(60))) % MOD

# for a in A:
#     # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

#     for i in range(60):
#         ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

#     # a_dash = list(map(lambda a: a*(n-1), a_bits))

#     # log("a_dash", a_dash)

#     # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
#     # log("bits_dash", bits_dash)
#     # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

#     # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

#     # for i in range(60):
#     #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
#     # log(a, ans)

# print(ans//2 % MOD)
print(ans)
# log("end.", time.time() - start)

Submission status: Accepted

Solution code:
'''ika tako
bit桁ごとに考える。「XORを取り、その後足し算」という計算過程では
他の桁が影響することはないので、桁毎に独立に考えて問題ない。
N = 5
A = {   1   2   3   4   5 }   ↓
    { 001 010 011 100 101 }
たとえば2桁目を取り出すと
       0   1   1   0   0
各ペアでXORを取ると、(0,1)は'1'となり、(0,0)(1,1)は'0'となる。 
0はいくら足しても0なので、(0,1)の数だけわかれば良い。
それは、(0の個数)×(1の個数)で計算できる。
    0が3個、1が2個
→  XORを取ったとき、2桁目について'1'が立っているペア
　　　　　　　　　　　=合計に足される回数は 3x2=6
→  2進数の2桁目は2を表すので、合計に足される値は6x2=12
これを各桁について足し合わせる。
'''
n = int(input())
aaa = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
ans = 0
m = 1
for _ in range(60):#上限は2＾60なので、60が上限
    bit = sum(a & m for a in aaa)#ｍは何番目のビットが立っているか
    bit //= m
    #bit >>= m これはダメだった。なぜ、だろう？
    non_bit = n - bit
    ans = (ans + bit * non_bit * m) % MOD
    #ｍは上記、2桁目を表す2と同様
    m <<= 1#ビットを１つずつ左シフト
print(ans)

'''
結局この計算は Ai のすべての組み合わせ(Ai 自身同士は含まない)の 
XOR の合計なので、Ai のあるビットの立っている数の合計を c とすると、
Ai のあるビットが0であった場合により計算結果に立つビットの数は 
c、Ai のあるビットが1であった場合により計算結果に立つビットの数は 
N - c になるので、あるビットに関する計算結果は c * (N -c) の
ビットシフトした値になる. 結果として以下の計算で解ける.

N = int(input())
A = list(map(int, input().split()))
 
result = 0
for bit in range(60):
    m = 1 << bit　すべてのビットを調べる
    c = sum(a & m for a in A) >> bit　
    ビット分、戻して、その桁に立っているビット数を算出
    result += (c * (N - c)) << bit　
    ビット分（上記の2桁目の2）調整、イメージとしては2のべき乗倍
    result %= 1000000007
print(result)
'''

Submission status: Accepted

Solution code:
'''ika tako
bit桁ごとに考える。「XORを取り、その後足し算」という計算過程では
他の桁が影響することはないので、桁毎に独立に考えて問題ない。
N = 5
A = {   1   2   3   4   5 }
               ↓
    { 001 010 011 100 101 }
たとえば2桁目を取り出すと
       0   1   1   0   0
各ペアでXORを取ると、(0,1)は'1'となり、(0,0)(1,1)は'0'となる。 
0はいくら足しても0なので、(0,1)の数だけわかれば良い。
それは、(0の個数)×(1の個数)で計算できる。
    0が3個、1が2個
→  XORを取ったとき、2桁目について'1'が立っているペア
　　　　　　　　　　　=合計に足される回数は 3x2=6
→  2進数の2桁目は2を表すので、合計に足される値は6x2=12
これを各桁について足し合わせる。
'''
n = int(input())
aaa = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
ans = 0
m = 1
for _ in range(60):
    bit = sum(a & m for a in aaa)
    bit //= m
    #bit >>= m これはダメだった。なぜ、だろう？
    non_bit = n - bit
    ans = (ans + bit * non_bit * m) % MOD
    m <<= 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
a = np.array(a)
ans = 0
# for bin_a in map(bin, a):
d = 1
num_of_one_per_keta = []
while d < (1 << 61):
    cnt = np.count_nonzero(a & d)
    num_of_one_per_keta.append(cnt)
    d <<= 1
ans = 0
for i, num_of_one in enumerate(num_of_one_per_keta):
    ans += (n-num_of_one)*num_of_one*pow(2, i, mod) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc147/tasks/abc147_d
n = int(input())
nums = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

ans = 0
one = [0] * 61
zero = [0] * 61

for i in range(61):
    for num in nums:
        if (num >> i) & 1:
            one[i] += 1
        else:
            zero[i] += 1
ans = 0
for k in range(61):
    ans = (ans + (one[k] * zero[k] * (1 << k))) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  import numpy as np
  n=int(input()) 
  a=np.array(list(map(int,input().split())))
  mod=pow(10,9)+7
  ans=0
  
  for i in range(60):
    x=np.count_nonzero(a & 1)
    ans+=pow(2,i,mod)*x*(n-x)
    ans=ans%mod
    a=a>>1
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
K = 1000000007
N = int(input())
A = [int(a) for a in input().split()]
li = [0] * 60
for n in range(N):
    li = [li[i] + (A[n] >> i & 1) for i in range(60)]
ans = 0
for i in range(60):
    ans += (1 << i) * li[i] * (N - li[i])
    ans %= K
print(ans)

Submission status: Accepted

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

from collections import Counter
s = []

for i in range(n):
    b = bin(a[i])[2:]
    c = len(b)
    s.append("0"*(60-c) + b)
    
ans = 0
for i in range(60):
    zero = 0
    one = 0
    for j in range(n):
        if s[j][i] == "0":
            zero += 1
        else:
            one += 1
            
    temp = zero * one * (2 ** (59-i)) % MOD
    
    ans = (ans + temp) % MOD
    
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A_list = []
	for vol in A:
		target = bin(vol)
		target = target[2:]
		target = target[::-1]
		A_list.append(target)

	ans = 0
	for k in range(60):
		conts_0 = 0
		conts_1 = 0
		for i,val in enumerate(A_list):
			if len(val) >= k+1:
				if "1" == val[k]:
					conts_1 += 1
				else:
					conts_0 += 1
			else:
				conts_0 += 1

		ans = (ans + (conts_1 * conts_0 * (2**k)) % mod ) % mod

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
A = np.array(input().split(), np.int)
#print(A)

cnt = 0
for i in range(61):
    B = (A>>i)&1
    z = np.count_nonzero(B)
    cnt += z*(N-z)*(2**(i))
    cnt %= MOD

print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

b = [0] * 60

def count(a, b):
	i = len(b)-1
	while a:
		b[i] += a % 2
		a //= 2
		i -= 1
	return i+1

def sum_xor(a, b, l, left):
	i = len(b)-1
	e = 1
	s = 0
	while a or left <= i:
		if a % 2 == 0:
			s = (s + b[i] * e) % mod
		else:
			s = (s + (l-(b[i])) * e) % mod
		a //= 2
		e = e * 2 % mod
		i -= 1
	return s

ans = 0
min_left = 60
for i in range(N):
	if i > 0:
		ans = (ans + sum_xor(A[i], b, i, min_left)) % mod
	left = count(A[i], b)
	min_left = min(min_left, left)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
import numpy as np
from collections import defaultdict
MOD = pow(10,9)+7
N = int(input())
d = [[N,0] for _ in range(60)]
A = list(map(int,input().split()))
A = np.array(A)
ans = 0
for m in range(60):
    B = (A >> m) & 1
    x = np.count_nonzero(B)
    x *= (N-x)
    x *= pow(2,m,MOD)
    ans += x
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
from collections import defaultdict
MOD = pow(10,9)+7
N = int(input())
d = [[N,0] for _ in range(60)]
A = list(map(int,input().split()))
for k in A:
    c = 0
    while k > 0:
        if k % 2 == 1:
            d[c][0] -= 1
            d[c][1] += 1
        k = k // 2
        c += 1
s = 0
for i in range(60):
    li = d[i]
    s += (li[0]*li[1]*pow(2,i,MOD))%MOD
print(s%MOD)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    D = [[0, 0] for _ in range(70)]
    for a in A:
        for i in range(70):
            if (a >> i) & 1:
                D[i][1] += 1
            else:
                D[i][0] += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
ans=0
for i in range(60):
    a,b=0,0
    for j in range(N):
        if A[j]%2==0:
            a=a+1
        else:
            b=b+1
        A[j]=A[j]//2
    ans=(ans+(a*b)*2**i)%MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 1e+9 + 7
shift = 70
a = [int(i) for i in input().split()]

b = [0 for _ in range(shift)]

for i in a:
  for j in range(shift):
    b[j] += (i >> j) & 1

ans = 0
for i, j in enumerate(b):
  ans += ((j * (N - j)) * 2**i) % MOD
  
print(int(ans%MOD))

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
mod = 10**9+7
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
A = np.array(A)
ans = 0
d = 1

while d < (1 << 60):
    cnt = np.count_nonzero(A & d)
    ans += (N - cnt) * cnt * d
    ans %= mod
    d <<= 1
print(ans)

Submission status: Accepted

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

n = 62
D = [0]*n

for i in range(N):
    s = list(bin(A[i])[2:])[::-1]
    s = [i for i in range(len(s)) if s[i]=='1']
    for j in s:
        D[j] += 1
ans = 0
for i in range(n):
    ans += D[i]*(N-D[i])*2**i
    ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np


input = sys.stdin.readline

def main():
    N = int(input().rstrip())
    A = np.array(input().rstrip().split(), dtype=np.int64)
    M = 60
    p = 10 ** 9 + 7
    ans = 0

    for m in range(M):
        B = (A >> m) & 1
        x = np.count_nonzero(B)
        x *= N-x
        
        x *= 2 ** m
        x %= p
        ans += x

    print(ans % p)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import collections
import itertools
import heapq
import string
import sys
import copy
import numpy as np
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')

N = iin()
A = np.array(sys.stdin.readline().split(), np.int64)

two_factor = 1
ans = 0
for i in range(60):
    B = A >> i & 1
    ones = np.count_nonzero(B)
    zeros = N - ones
    zeroone_cmb = ones*zeros%MOD
    ans = (ans + (zeroone_cmb*two_factor%MOD))%MOD
    two_factor = (two_factor*2)%MOD

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
import math
A=list(map(int,input().split()))
b=math.ceil(math.log(max(max(A),1),2)) 
B=[0 for i in range(b)] #0のリスト
C=[0 for i in range(b)] #1のリスト
for i in A:
  for j in range(b):
    if ((i>>j) & 1):
      C[j]+=1
    else:
      B[j]+=1
 # print(B,C,i)
mod =10**9+7
ans=[(B[i]*C[i])*2**i % mod for i in range(b)]
print(sum(ans)%mod)

Submission status: Accepted

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

bucket = [0] * 61
for num in A:
    for j in range(60):
        if (num >> j) & 1:
            bucket[j] += 1
# print(bucket)

ans = 0
res = 1
for i, one in enumerate(bucket):
    temp = (bucket[i] * (N - bucket[i]) * res) % MOD
    # print(temp)
    ans = (ans + temp) % MOD
    res = (res * 2) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    ans = 0

    for k in range(60):
        # 各要素のk桁目をXOR演算
        x0 = 0
        x1 = 0
        for i in range(N):
            x = A[i] >> k & 1  # k桁目
            if x == 0:
                x0 += 1
            else:
                x1 += 1
        ans += (x0 * x1) * (2 ** k)
    print(ans % mod)


resolve()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans=0
cnt=0
fin=False
while not fin:
    fin=True
    z_cnt=0
    o_cnt=0
    for i in range(len(a)):
        q,mod = divmod(a[i],2)
        a[i]=q
        if q!=0:
            fin=False
        if mod==0:
            z_cnt+=1
        else:
            o_cnt+=1

    ans+=(z_cnt*o_cnt) * pow(2,cnt)
    ans%=10**9+7
    cnt+=1
print(ans)

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    A = [format(a, "b")[::-1] for a in A]
    a_sum = [int()]*60

    for a in A:
        for i, r_a in enumerate(a):
            if r_a == "1":
                a_sum[i] += 1

    a_sum = [a_s_*(2**i)%MOD for i, a_s_ in zip(range(60), a_sum)]
    a_acc_sum = [_ for _ in a_sum]

    for x in range(1,60):
        a_acc_sum[x] = a_acc_sum[x-1] + a_acc_sum[x] 
    
    ans = 0
    for a in A:
        for i, r_a in enumerate(a):
            if r_a == "0":
                ans += a_sum[i]
        
        ans += a_acc_sum[59] - a_acc_sum[i]
        ans %= MOD

    print(ans%MOD)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    A = [format(a, "b")[::-1] for a in A]
    a_sum = [int()]*60

    for a in A:
        for i, r_a in enumerate(a):
            if r_a == "1":
                a_sum[i] += 1

    a_sum = [a_s_*(2**i)%MOD for i, a_s_ in zip(range(60), a_sum)]
    a_acc_sum = [_ for _ in a_sum]
    
    for x in range(1,60):
        a_acc_sum[x] = a_acc_sum[x-1] + a_acc_sum[x] 
    
    ans = 0
    for a in A:
        for i, r_a in enumerate(a):
            if r_a == "0":
                ans += a_sum[i]
        
        ans += a_acc_sum[59] - a_acc_sum[i]

        # for ic in range(i+1,60):
            # ans+=a_sum[ic]
            # ans%=MOD

    print(ans%MOD)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()