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:
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 0
N = read_a_int()
A = []
for a in read().split():
    A.append(int(a))
    n = max(n, len(bin(int(a))) - 2)


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += ((2**i) * n_1) % MOD
        else:
            ret += ((2**i) * (n_1_max - n_1)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 0
N = read_a_int()
A = []
for a in read().split():
    A.append(int(a))
    n = max(n, len(bin(int(a))) - 2)


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * n_1) % MOD
        else:
            ret += (((2**i) % MOD) * (n_1_max - n_1)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for j in range(N):
    a = A[j]
    for i in range(60):
      if (a >> i) & 1 == 0:
        res += ones[i] * ((2 ** i)%MOD)
      else:
        res += (N-ones[i]-j) * ((2 ** i)%MOD)
        ones[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

P = 10**9+7
bit = [0 for i in range(60)]

# 各bit独立に1が何個あるか数える
for a in A:
    for i in range(60):
        if a&(1<<i):
            bit[i] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
ans = 0
for i,a in enumerate(bit):
    ans += a*(N-a)*(2**i)
    ans %= P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for j in range(N):
    a = A[j]
    for i in range(60):
      if (a >> i) & 1 == 0:
        res += ones[i] * (2 ** i)%MOD
      else:
        res += (N-ones[i]-j) * (2 ** i)%MOD
        ones[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * n_1) % MOD
        else:
            ret += (((2**i) % MOD) * (n_1_max - n_1)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
P = 10**9+7
bit = [0 for i in range(60)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i,a in enumerate(bit):
    ans += a*(N-a)*(2**i)
    ans %= P

print(ans)

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()

import numpy as np


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return np.array(ret_r, dtype='int')


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * n_1) % MOD
        else:
            ret += (((2**i) % MOD) * (n_1_max - n_1)) % MOD
    return ret


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = np.zeros(n, dtype='int')
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = n_1_ls + a_pre_binary
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()

import numpy as np


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return np.array(ret_r, dtype='int')


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * (n_1 % MOD)) % MOD
        else:
            ret += (((2**i) % MOD) * ((n_1_max - n_1) % MOD)) % MOD
    return ret


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = np.zeros(n, dtype='int')
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = n_1_ls + a_pre_binary
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
P = 10**9+7
bit = [0]*60

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(60):
    if bit[i] != 0 and bit[i] != N:
        ans += bit[i]*(N-bit[i])*(2**i)
        ans %= P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
MOD = 10 ** 9 + 7
#2番目以降(N-1個の数)のbitの格桁の合計
l = [0] * 60
for i in range(N):
    s = list(str(bin(A[i]))[2:].rjust(60, '0'))
    #print(s)
    for j in range(60):
        if s[j] == '1':
            l[j] += 1
answer = 0
#print(l)
for i in range(N-1):
    s = list(str(bin(A[i]))[2:].rjust(60, '0'))
    for j in range(60):
        if s[j] == '1':
            l[j] -= 1
            answer += 2 ** (59-j) * (N - 1 - i - l[j])
        else:
            answer += 2 ** (59-j) * l[j]
    answer %= MOD
#print(l)
print(answer)

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * (n_1 % MOD)) % MOD
        else:
            ret += (((2**i) % MOD) * ((n_1_max - n_1) % MOD)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
MOD=10**9+7
m=max(a)
s=bin(m)
l=len(s[2:])
h=[0]*l
su=0
for i in range(n):
    s=bin(a[i])
    su+=a[i]%MOD
    for j in range(len(s)-2):
        if s[len(s)-j-1]=='1':
            h[j]+=1
count=0
for i in range(n):
    count+=su
    count%=MOD
    su-=a[i]%MOD
    s=bin(a[i])
    for j in range(len(s)-2):
        if s[len(s)-j-1]=='1':
            k=pow(2,j,MOD)
            x=(k*(n-h[j]*2-i))%MOD
            count+=x
            count%=MOD
            h[j]-=1
    #print(count,h)
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
MOD=10**9+7
m=max(a)
s=bin(m)
l=len(s[2:])
h=[0]*l
su=0
for i in range(n):
    s=bin(a[i])
    su+=a[i]%MOD
    for j in range(len(s)-2):
        if s[len(s)-j-1]=='1':
            h[j]+=1
count=0
for i in range(n):
    count+=su
    su-=a[i]%MOD
    s=bin(a[i])
    for j in range(len(s)-2):
        if s[len(s)-j-1]=='1':
            k=pow(2,j,MOD)
            x=(k*(n-h[j]*2-i))%MOD
            count+=x
            count%=MOD
            h[j]-=1
    #print(count,h)
print(count)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9 + 7
#print(bin(9))
N=int(input())
A=list(map(int,input().split()))
A.sort()
#print(A)
A=[bin(i)[2:] for i in A]
#print(A)
nowdata=[0 for i in range(60)]
data=[0 for i in range(60)]

#print(A)

for i in range(N-1):
    S=A[i]

    for a in range(len(S)):
        if S[-a-1]=="1":
            nowdata[a]+=1
    S=A[i+1]
    for a in range(len(S)):
        if S[-a-1]=="0":
            data[a]+=nowdata[a]
        else:
            data[a]+=i+1-nowdata[a]
    #print(nowdata)


num=0
#print(data)
for i in range(60):
    num+=data[i]* (2**i)
    num%=mod

print(num)

Submission status: Time Limit Exceeded

Solution code:
N=int(input()) 
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7
c = [0]*k
 
for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    if bit[j] == '1':
      c[-1-j] +=1
      
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
MOD=10**9+7
m=max(a)
s=bin(m)
l=len(s[2:])
h=[0]*l
for i in range(n):
    buf=a[i]
    for j in range(l):
        h[j]+=buf%2
        buf//=2
#print(h)
count=0
su=sum(a)
for i in range(n):
    count+=su
    su-=a[i]
    s=bin(a[i])
    for j in range(len(s)-2):
        if s[len(s)-j-1]=='1':
            k=pow(2,j,MOD)
            x=(k*(n-h[j]*2-i))%MOD
            count+=x
            count%=MOD
            h[j]-=1
    #print(count,h)
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split( )))
ans = 0
mod = 10**9+7
Bit = [0 for j in range(60)]# for i in range(n+1)

for i in range(1,n):##1から
    for j in range(60):
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j]<<j
            ans %=mod
        else:
            ans += (i-Bit[j])<<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
m=max(a)
s=bin(m)
l=len(s[2:])
h=[0]*l
for i in range(n):
    buf=a[i]
    for j in range(l):
        h[j]+=buf%2
        buf//=2
#print(h)
count=0
su=sum(a)
for i in range(n):
    count+=su
    su-=a[i]
    s=bin(a[i])
    #print(s)
    for j in range(len(s)-2):
        if s[len(s)-j-1]=='1':
            k=pow(2,j,MOD)
            count+=k*(n-h[j]*2-i)
            count%=MOD
            h[j]-=1
    #print(count,h)
print(count)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9 + 7
#print(bin(9))
N=int(input())
A=list(map(int,input().split()))
A.sort()
#print(A)
A=[bin(i)[2:] for i in A]
#print(A)
nowdata=[0 for i in range(60)]
data=[0 for i in range(60)]

#print(A)

for i in range(N-1):
    S=A[i]

    for a in range(len(S)):
        nowdata[a]+=int(S[-a-1])
    S=A[i+1]
    for a in range(len(S)):
        if S[-a-1]=="0":
            data[a]+=nowdata[a]
        else:
            data[a]+=i+1-nowdata[a]
    #print(nowdata)


num=0
#print(data)
for i in range(60):
    num+=data[i]* (2**i)
    num%=mod

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split( )))
ans = 0
mod = 10**9+7
Bit = [0 for j in range(60)]# for i in range(n+1)

for i in range(1,n):##1から
    for j in range(60):
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j]<<j
            ans %=mod
        else:
            ans += (i-Bit[j])<<j
            ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n  = int(input())
m  = 10 ** 9 + 7
xs = [int(x) for x in input().split()]
bs = [0] * 60
b  = 1

for x in xs:
	e = 0
	
	while 0 < x:
		if x % 2 == 1:
			bs[e] += 1
			
		e  += 1
		x //= 2

b = 1
r = 0

for i in range(0, 60):
	r  += ((n - bs[i]) * bs[i]) * b
	b <<= 1
	
print(r % m)

Submission status: Time Limit Exceeded

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

ans = 0
P = 10**9+7
bit = [0 for i in range(60)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(60):
    if bit[i] != 0 and bit[i] != N:
        ans += (2**i)*bit[i]*(N-bit[i])
        ans %= P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n  = int(input())
m  = 10 ** 9 + 7
xs = [int(x) for x in input().split()]
bs = [0] * 61
b  = 1

for x in xs:
	e = 0
	
	while 0 < x:
		if x % 2 == 1:
			bs[e] += 1
			
		e  += 1
		x //= 2

b = 1
r = 0

for i in range(0, 61):
	if 0 < bs[i] and bs[i] < n:
		r += ((n - bs[i]) * bs[i]) * b
		
	b <<= 1
	
print(r % m)

Submission status: Time Limit Exceeded

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

from collections import defaultdict

cnt = defaultdict(int)

for i in range(N):
    for j in range(61):
        if a_list[i] & (1 << j):
            cnt[j] += 1


ans = 0
mod = 10 ** 9 + 7

for i in range(61):
    ans += cnt[i] * (N - cnt[i]) * (1 << i)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
P = 10**9+7
bit = [0 for i in range(60)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        bit[j-1] += int(S[-1*j])

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(60):
    if bit[i] != 0 and bit[i] != N:
        ans += (2**i)*bit[i]*(N-bit[i])
        ans %= P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
for i in range(60):
    t = 2**i
    B = [A[j]&t for j in range(N)]
    c = B.count(0)
    ans += c*(N-c)*(t%MOD)%MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
X = [0]*60
sumA = 0
for i in A:
    for j in range(60):
        if i >> j & 1 == 1:
            X[j] += 1
    sumA += i
ans = 0
for i in range(N):
    sumA -= A[i]
    ans += sumA
    for j in range(60):
        if A[i] >> j & 1 == 1:
            X[j] -= 1
            ans += ((2**j) * (N-i-1-X[j]*2))%MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    if bit[i] != 0 and bit[i] != N:
        ans += (2**i)*bit[i]*(N-bit[i])
        ans %= P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
MOD=10**9+7
m=max(a)
s=bin(m)
l=len(s[2:])
h=[0]*l
for i in range(n):
    buf=a[i]
    for j in range(l):
        h[j]+=buf%2
        buf//=2
#print(h)
count=0
su=sum(a)
for i in range(n):
    buf=a[i]
    count+=su
    su-=a[i]
    for j in range(l):
        if buf%2==1:
            k=pow(2,j,MOD)
            count+=k*(n-h[j]*2-i)
            count%=MOD
            h[j]-=buf%2
        buf//=2
    
    #print(count,h)
print(count)

Submission status: Time Limit Exceeded

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

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    ans += (2**i)*bit[i]*(N-bit[i])
    ans %= P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
d_max=max(l)
dp=[[-1 for i in range(d_max+1)] for j in range(d_max+1)]
ans=0

for i in range(n):
    for j in range(i,n):
        a=0
        if i == j:
            continue
        if dp[l[i]][l[j]] == -1:
            a=l[i]^l[j]
            dp[l[i]][l[j]]=a
        else:
            a=dp[l[i]][l[j]]
        ans+=a

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
s = 0
x = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        s += lst[i]^lst[j]
mod = 10 ** 9 + 7
print(s % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
for i in range(60):
    B = [(A[j]>>i)&1 for j in range(N)]
    c = B.count(0)
    ans += c*(N-c)*(2**i%MOD)%MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
for i in range(60):
    B = [(A[j]>>i)&1 for j in range(N)]
    c = B.count(0)
    ans += c*(N-c)*2**i%MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = [0]*60
C = [0]*60

ans = 0
for i in range(60):
    D = [(A[j]>>i)&1 for j in range(N)]
    ans += D.count(0)*D.count(1)*2**i%MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
n  = int(input())
m  = 10 ** 9 + 7
xs = [int(x) for x in input().split()]
bs = [0] * 61
b  = 1

for i in range(0, 61):
	c = 0
	
	for x in xs:
		if (x & b) != 0:
			c += 1
	
	bs[i] = c
	b   <<= 1

b = 1
r = 0

for i in range(0, 61):
	if 0 < bs[i] and bs[i] < n:
		r += ((n - bs[i]) * bs[i]) * b
		
	b <<= 1
	
print(r % m)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 60
data = [[0 for i in range(leng+1)] for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        temp = data[i - 1][j]
        if j - 1 >= ll:
            data[i][j] = temp
            continue
        if k[j - 1] == "1":
            data[i][j] = temp + 1
        else:
            data[i][j] = temp
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = format(a[i], 'b')
    k = list(k)
    k.reverse()
    for s in range(leng - len(k)):
        k.append(0)
    for j in range(leng):
        if k[j] == "1":
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
a_ls = [bin(int(i))[2:].zfill(60)[::-1] for i in sys.stdin.readline().split()]
MOD = 10**9 + 7
#memo_ls[i][j] : 後ろからi番目まででj桁に1がある個数
memo_ls = [[0 for j in range(60)] for i in range(n+1)]
for i, a in enumerate(a_ls[::-1], 1):
    for j, k in enumerate(a):
        memo_ls[i][j] = memo_ls[i-1][j] + int(k)

res = 0
for i in range(60):
    res += memo_ls[-1][i] * (n - memo_ls[-1][i]) * 2 ** i
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
MOD=10**9+7
m=max(a)
s=bin(m)
l=len(s[2:])
h=[0]*l
for i in range(n):
    buf=a[i]
    for j in range(l):
        h[j]+=buf%2
        buf//=2
#print(h)
count=0
for i in range(n):
    buf=a[i]
    for j in range(l):
        k=pow(2,j,MOD)
        if buf%2==1:
            count+=k*(n-h[j]-i)
        else:
            count+=k*h[j]
        count%=MOD
        h[j]-=buf%2
        buf//=2
    #print(count)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
a_ls = [bin(int(i))[2:].zfill(60) for i in sys.stdin.readline().split()]
MOD = 10**9 + 7
#memo_ls[i][j] : 後ろからi番目まででj桁に1がある個数
memo_ls = [[0 for j in range(60)] for i in range(n+1)]
for i, a in enumerate(a_ls[::-1], 1):
    for j, k in enumerate(a[::-1]):
        memo_ls[i][j] = memo_ls[i-1][j] + int(k)

res = 0
for i in range(60):
    res += memo_ls[-1][i] * (n - memo_ls[-1][i]) * 2 ** i
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [0] * 60
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        ones[i] += 1
  # print(ones)
  res = 0
  for j in range(N):
    a = A[j]
    for i in range(60):
      if (a >> i) & 1 == 0:
        res += ones[i] * 2 ** i
      else:
        res += (N-ones[i]-j) * 2 ** i
        ones[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = 61
data = [[0 for i in range(leng+1)] for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        if j - 1 >= ll:
            data[i][j] = data[i - 1][j]
            continue
        if k[j - 1] == "1":
            data[i][j] = data[i - 1][j] + 1
        else:
            data[i][j] = data[i-1][j]
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = format(a[i], 'b')
    k = list(k)
    k.reverse()
    for s in range(leng - len(k)):
        k.append(0)
    for j in range(leng):
        if k[j] == "1":
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = [0]*60
C = [0]*60

for i in range(60):
    for j in range(N):
        if (A[j]>>i)&1 == 0:
            C[i] += 1
        else:
            B[i] += 1

ans = 0
for i in range(60):
    ans += B[i]*C[i]*2**i%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
mxbit = 0
for i in range(N):
  mxbit = max(mxbit, a[i].bit_length())
cs = [[0] * mxbit for _ in range(N + 1)]
for i in range(N):
  for j in range(mxbit):
    t = 1 << j
    #print(a[i], t, a[i] & t)
    x = (a[i] & t) > 0
    cs[i + 1][j] = (cs[i][j] + x) % mod
res = 0
#print(cs[-1])
#print(cs[2])
for i in range(N):
  t = 0
  for j in range(mxbit):
    x = 1 << j
    if a[i] & x != 0:
      x %= mod
      #if i == 1: print((1 << j) * (N - i - 1), (cs[-1][j] - cs[i + 1][j]))
      t += x * ((N - i - 1) - (cs[-1][j] - cs[i + 1][j]))
    else:
      x %= mod
      #if i == 1: print(a[i] & (1 << j), (cs[-1][j] - cs[i + 1][j]))
      t += x * (cs[-1][j] - cs[i + 1][j])
    #print(t)
    t %= mod
  res += t
  res %= mod
print(res % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
cs = [[0] * 60 for _ in range(N + 1)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(60):
    t = 1 << j
    #print(a[i], t, a[i] & t)
    x = (a[i] & t) > 0
    cs[i + 1][j] = (cs[i][j] + x) % mod
res = 0
#print(cs[-1])
#print(cs[2])
for i in range(N):
  t = 0
  for j in range(60):
    x = 1 << j
    if a[i] & x != 0:
      x %= mod
      #if i == 1: print((1 << j) * (N - i - 1), (cs[-1][j] - cs[i + 1][j]))
      t += x * ((N - i - 1) - (cs[-1][j] - cs[i + 1][j]))
    else:
      x %= mod
      #if i == 1: print(a[i] & (1 << j), (cs[-1][j] - cs[i + 1][j]))
      t += x * (cs[-1][j] - cs[i + 1][j])
    #print(t)
    t %= mod
  res += t
  res %= mod
print(res % mod)