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()))
MOD = 1000000007

for i, a in enumerate(A):
    if i == 0:
        bits = [[0] * 60]
    else:
        bits.append(bits[i - 1].copy())

    cnt = 0
    while a != 0:
        if a & 1:
            bits[i][cnt] += 1

        cnt += 1
        a >>= 1


all_sum = 0
two_exp = [pow(2, i, MOD) for i in range(60)]

for i, a in enumerate(A):
    temp_sum = 0
    cnt = 0
    while cnt < 60:
        ones = bits[-1][cnt] - bits[i][cnt]
        zeros = N - (i + 1) - ones

        if a & 1:
            temp_sum += (two_exp[cnt] * zeros) % MOD
        else:
            temp_sum += (two_exp[cnt] * ones) % MOD

        temp_sum %= MOD

        a >>= 1
        cnt += 1

    all_sum += temp_sum
    all_sum %= MOD


print(all_sum)

Submission status: Time Limit Exceeded

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

for i, a in enumerate(A):
    if i == 0:
        bits = [[0] * 60]
    else:
        bits.append(bits[i - 1].copy())

    cnt = 0
    while a != 0:
        if a & 1:
            bits[i][cnt] += 1

        cnt += 1
        a >>= 1


all_sum = 0
for i, a in enumerate(A):
    temp_sum = 0
    cnt = 0
    while cnt < 60:
        ones = bits[-1][cnt] - bits[i][cnt]
        zeros = N - (i + 1) - ones

        if a & 1:
            temp_sum += (pow(2, cnt, MOD) * zeros) % MOD
        else:
            temp_sum += (pow(2, cnt, MOD) * ones) % MOD

        temp_sum %= MOD

        a >>= 1
        cnt += 1

    all_sum += temp_sum
    all_sum %= MOD


print(all_sum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations 

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = int(input())
A = LI()
mod = 10**9 + 7
ans = 0

for a in combinations(A, 2):
    ans += a[0] ^ a[1]
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
p = 10**9 + 7
total = 0
for i in range(60):
    cnt_1, cnt_0 = 0, 0
    for j in range(N):
        if (A[j]>>i)&1:
            cnt_1 += 1
        else:
            cnt_0 += 1
    total += pow(2, i, p) * cnt_0 * cnt_1 %p
print(total%p)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
p = 10**9 + 7
total = 0
for i in range(60):
    cnt_1, cnt_0 = 0, 0
    for j in range(N):
        if (A[j]>>i)&1:
            cnt_1 += 1
        else:
            cnt_0 += 1
    total += 2**i * cnt_0 * cnt_1
print(total%p)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
num_list = [0] * 100
P = 10 ** 9 + 7
for i in A:
    tmp = i
    for j in range(len(bin(i)) - 2):
        num_list[j] += (tmp & 1)
        tmp = tmp >> 1
ans = 0


def func(N, n):
    return (N - n) * n


for i in range(100):
    ans = (ans + func(N, num_list[i]) * 2 ** i) % P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
num_list = [0] * 100
P = 10 ** 9 + 7
for i in A:
    for j in range(len(bin(i)) - 2):
        num_list[j] += (i >> j) & 1
ans = 0


def func(N, n):
    return (N - n) * n


for i in range(100):
    ans = (ans + func(N, num_list[i]) * 2 ** i) % P
print(ans)

Submission status: Time Limit Exceeded

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

M = 61
D1 = [0] * M

for a in A:
    k = 0
    while a > 0:
        if a & 1:
            D1[k] += 1
        a >>= 1
        k += 1

MOD = 10 ** 9 + 7
ans = 0
for k in range(M):
    d = D1[k]
    ans += d * (N - d) * pow(2, k, MOD)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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


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

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

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


            if check[next_vertex]==True:
                continue

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

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

    return color

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

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

Submission status: Time Limit Exceeded

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


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

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

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


            if check[next_vertex]==True:
                continue

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

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

    return color

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys


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


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    d_0 = [N for _ in range(61)]
    d_1 = [0 for _ in range(61)]
    max_d = 0
    for a in A:
        d = 0
        while a > 0:
            keta = a % 2
            a //= 2
            if keta == 1:
                d_0[d] -= 1
                d_1[d] += 1
            d += 1
        if d > max_d:
            max_d = d
    # print(d_0)
    # print(d_1)
    answer = 0
    for i in range(max_d):
        answer += d_0[i] * d_1[i] * 2 ** i
        answer %= MOD
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
ans=0
for i in range(60):
    ichi=0
    for j in range(n):
        if (a[j]>>i)&1:
            ichi+=1
    zero=n-ichi
    s=ichi*zero*pow(2,i,mod)%mod# xorをしたあとi桁目が1になる組み合わせの個数 x 2**i
    ans+=s
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
ans=0
for i in range(60):
    ichi=0
    for j in range(n):
        if (a[j]>>i)&1:
            ichi+=1
    zero=n-ichi
    s=ichi*zero*2**i%mod# xorをしたあとi桁目が1になる組み合わせの個数 x 2**i
    ans+=s
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = 10**9+7
n = int(input())
a = np.array(input().split(), np.int64)

ans = 0

po = 1
for i in range(61):
    bit = (a>>i) & 1
    s=sum(bit)
    ans+=s*(n-s)*po
    ans%=N
    po*=2
    po%=N
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 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:
import math
N = 10**9+7
n = int(input())
a = list(map(int,input().split()))

ans = 0

po = 1
for i in range(61):
    sum=0
    for j in range(n):
        sum+=(a[j]>>i) & 1
    ans+=sum*(n-sum)*po
    ans%=N
    po*=2
    po%=N
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(61):
    sum=0
    for j in range(n):
        sum+=(a[j]>>i) & 1
    ans+=sum*(n-sum)*pow(2,i,N)
    ans%=10**9+7
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

a1 = max(a)
if a1 == 0:
    a1=2
ma = int(math.log2(a1))
if ma<0:
    ma=0
for i in range(ma+2):
    sum=0
    for j in range(n):
        sum+=(a[j]>>i) & 1
    ans+=sum*(n-sum)*pow(2,i,N)
    ans%=10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))

if __name__=='__main__':
    mod = 10**9 + 7
    n = I()
    a = LI()
    ans = 0
    for i in range(60):
        c1 = 0
        for rep in a:
            if (rep>>i)&1:
                c1 += 1
        ans += ((n-c1)*c1*(2**i)%mod)%mod
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# 813~
# 解法 826
# 各数字について，２進数に直したときの各桁の値を計算する．(桁数＊(0,1))の形を持ったリストに対して,各桁数ごとの値で
# 足し合わせていく．各桁ごとに(0,1)の要素数をかけ合わせて，最後に足し合わせれば答えになる
# 計算量は　O(N*60)くらい
# 実装， 思ったよりもかんたんだったけど，やっぱり単純なケースで間違っていることがわかってやり直さないといけなかった
# 結果はあってるだろうけどTLEが出て困る

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

Large = 10**9 + 7
BA = [[0,0] for _ in range(60)] # <2^60なので
pow260 = pow(2,60)
for a in A:
    a = a + pow260
    a_bin = bin(a)
    for i,ab in enumerate(a_bin[::-1][:-3]): # 最初の'0x'みたいなのを取り除く，あと最初につけた'1'を除く
        ab = int(ab)
        BA[i][ab] += 1
ans = 0
for i,ba in enumerate(BA):
    ans += ba[0] * ba[1] * pow(2,i,Large)
    ans %= Large

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 813~
# 解法 826
# 各数字について，２進数に直したときの各桁の値を計算する．(桁数＊(0,1))の形を持ったリストに対して,各桁数ごとの値で
# 足し合わせていく．各桁ごとに(0,1)の要素数をかけ合わせて，最後に足し合わせれば答えになる
# 計算量は　O(N*60)くらい

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

Large = 10**9 + 7
BA = [[0,0] for _ in range(60)] # <2^60なので
for a in A:
    a = a + pow(2,60)
    a_bin = bin(a)
    for i,ab in enumerate(a_bin[::-1][:-3]): # 最初の'0x'みたいなのを取り除く，あと最初につけた'1'を除く
        ab = int(ab)
        BA[i][ab] += 1
ans = 0
for i,ba in enumerate(BA):
    ans += ba[0] * ba[1] * pow(2,i,Large)
    ans %= Large

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    res = 0
    for i in range(60):
        cnt = 0
        for a in A:
            cnt += (a >> i) & 1
        res += (cnt * (n - cnt) % mod) * (1 << i) % mod
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

# 10進数表記でnのk進数を求めてlength分0埋め
def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums


def main():
    num = int(input())
    data = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    max_length = len(bin(max(data))) - 2
    bit_count = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = ternary(data[i], 2, max_length)
        data[i] = now_bin
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] += 1

    flg_data = [0 for i in range(max_length)]

    # for i in range(num):
    #     now_bin = data[i]
    #     for j in range(max_length):
    #         if now_bin[j] == "1":
    #             bit_count[j] -= 1
    #             flg_data[j] += (num - i - 1 - bit_count[j])
    #         else:
    #             flg_data[j] += bit_count[j]

    for i in range(max_length):
        flg_data[i] += bit_count[i] * (num - bit_count[i])

    # print(flg_data)
    # print(bit_count)

    ans = 0
    for j in range(max_length):
        pow_num = max_length - 1 - j
        bbb = pow(2, pow_num, mod)

        ans += bbb * flg_data[j]
        ans %= mod

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

# 10進数表記でnのk進数を求めてlength分0埋め
def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums


def main():
    num = int(input())
    data = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    max_length = len(bin(max(data))) - 2
    bit_count = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = ternary(data[i], 2, max_length)
        data[i] = now_bin
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] += 1

    flg_data = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = data[i]
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] -= 1
                flg_data[j] += (num - i - 1 - bit_count[j])
            else:
                flg_data[j] += bit_count[j]

    ans = 0
    for j in range(max_length):
        pow_num = max_length - 1 - j
        bbb = pow(2, pow_num, mod)

        ans += bbb * flg_data[j]
        ans %= mod

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

# 10進数表記でnのk進数を求めてlength分0埋め
def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums


def main():
    num = int(input())
    data = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    max_length = len(bin(max(data))) - 2
    bit_count = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = ternary(data[i], 2, max_length)
        data[i] = now_bin
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] += 1

    pow_data = defaultdict(int)

    ans = 0
    for i in range(num):
        now_bin = data[i]
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] -= 1
                aaa = (num - i - 1 - bit_count[j])
            else:
                aaa = bit_count[j]

            pow_num = max_length - 1 - j
            if pow_num in pow_data:
                bbb = pow_data[pow_num]
            else:
                bbb = pow(2, pow_num, mod)
                pow_data[pow_num] = bbb

            ans += bbb * aaa
            ans %= mod

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

# 10進数表記でnのk進数を求めてlength分0埋め
def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums


def main():
    num = int(input())
    data = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    max_length = 61
    bit_count = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = ternary(data[i], 2, max_length)
        # print(now_bin)
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] += 1


    ans = 0
    for i in range(num):
        now_bin = ternary(data[i], 2, max_length)
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] -= 1
                ans += pow(2, max_length - 1 - j, mod) * (num - i - 1 - bit_count[j])
            else:
                ans += pow(2, max_length - 1 - j, mod) * bit_count[j]
            ans %= mod

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int, input().split()))
mod = 10**9 + 7
m = len(bin(max(s))) - 2
p = [0] * m
q = [0] * m

for i in s:
    for j in range(m):
        if (i >> j) & 1 == 1:
            p[j] += 1
        else:
            q[j] += 1

res = 0
r = 1
for k in range(m):
    res += p[k] * q[k] % mod * r
    res %= mod
    r = r * 2 % mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10 ** 9 + 7

x = 1
ans = 0
for i in range(60):
    ones = 0
    zeros = 0
    for a in A:
        if a & (1 << i) > 0:
            ones += 1
        else:
            zeros += 1
    ans += (ones * zeros * x) % MOD
    x *= 2

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def mod_pow(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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

mod = 10 ** 9 + 7

cnt = [0] * 60
for v in a:
    for i in range(60):
        if (v >> i) & 1:
            cnt[i] += 1

res = 0
for v in a:
    for i in range(60):
        if (v >> i) & 1:
            res = (res + (n - cnt[i]) * mod_pow(2, i) % mod) % mod
        else:
            res = (res + cnt[i] * mod_pow(2, i) % mod) % mod

print(res * mod_pow(2, mod - 2) % mod)

Submission status: Time Limit Exceeded

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

bins_zero=[0]*61
bins_one=[0]*61
for a_i in a:
    a_i_bin=list(str(bin(a_i))[2:].zfill(61))
    for i in range(len(a_i_bin)):
        if a_i_bin[i]=='0':
            bins_zero[i]+=1
        else:
            bins_one[i]+=1

ans=0
for i in range(61):
    ans+=(bins_one[i]*bins_zero[i]*(2**(60-i)))
print(ans%mod)

Submission status: Time Limit Exceeded

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

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

# 各桁の1と0の数を数えて、((1の数) * (0の数)) * (2 ** i桁目(1桁目を0とする))を数える

K = max(A)
for i in range(len(A)):
  A[i] = bin(A[i])[2:][::-1]
  
j = 0
ans = 0
while K:
  one = 0
  for i in range(len(A)):
    if len(A[i]) > j:
      if A[i][j] == "1":
        one += 1
  ans += (one % DIV) * ((N - one) % DIV) * pow(2,j,DIV)
  ans %= DIV
  j += 1
  K >>= 1
  
print(ans)

Submission status: Time Limit Exceeded

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

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

# 各桁の1と0の数を数えて、((1の数) * (0の数)) * (2 ** i桁目(1桁目を0とする))を数える

K = max(A) # 最も大きい数が0になるまでループ
ans = 0
j = 0
while K:
  one = 0
  for i in range(len(A)):
    if (A[i] >> j) & 1:
      one += 1
  ans += (one % DIV) * ((N - one) % DIV) * pow(2,j,DIV)
  ans %= DIV
  j += 1
  K >>= 1
  
print(ans)

Submission status: Time Limit Exceeded

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

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

# 各桁の1と0の数を数えて、((1の数) * (0の数)) * (2 ** i桁目(1桁目を0とする))を数える

K = max(A) # 最も大きい数が0になるまでループ
rate = 1
ans = 0
j = 0
while K:
  one = 0
  zero = 0
  for i in range(len(A)):
    if (A[i] >> j) & 1:
      one += 1
    else:
      zero += 1
  ans += (one % DIV) * (zero % DIV) * rate
  ans %= DIV
  rate *= 2
  rate %= DIV
  j += 1
  K >>= 1
  
print(ans)

Submission status: Time Limit Exceeded

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

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

# 各桁の1と0の数を数えて、((1の数) * (0の数)) * (2 ** i桁目(1桁目を0とする))を数える

K = max(A) # 最も大きい数が0になるまでループ
rate = 1
ans = 0
j = 0
while K:
  one = 0
  zero = 0
  for i in range(len(A)):
    if (A[i] >> j) & 1:
      one += 1
    else:
      zero += 1
  ans += one * zero * rate
  ans %= DIV
  rate *= 2
  j += 1
  K >>= 1
  
print(ans)

Submission status: Time Limit Exceeded

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

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

# 各桁の1と0の数を数えて、((1の数) * (0の数)) * (2 ** i桁目(1桁目を0とする))を数える

K = max(A) # 最も大きい数が0になるまでループ
rate = 1
ans = 0
while K:
  one = 0
  zero = 0
  for i in range(len(A)):
    if A[i] & 1:
      one += 1
    else:
      zero += 1
    A[i] >>= 1
  ans += one * zero * rate
  ans %= DIV
  rate *= 2
  K >>= 1
  
print(ans)

Submission status: Time Limit Exceeded

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

    base_2_cnt = [0]*60 
    for a in al:
        for i in range(60):
            if ((a >> i) & 1): base_2_cnt[i] += 1

    ans = 0
    curr_2 = 1
    for i in range(60):
        base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
        ans += base_01_comb * curr_2
        ans %= MOD
        curr_2*=2
        curr_2%=MOD

    print(ans%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    al = list(map(int, input().split()))

    base_2_cnt = [0]*60 
    for a in al:
        for i in range(60):
            if ((a >> i) & 1): base_2_cnt[i] += 1

    ans = 0
    curr_2 = 1
    for i in range(60):
        base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
        ans += base_01_comb * curr_2
        ans %= 10**9+7
        curr_2*=2

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    al = list(map(int, input().split()))

    base_2_cnt = [0]*60 
    for a in al:
        for i in range(60):
            if ((a >> i) & 1): base_2_cnt[i] += 1

    ans = 0
    for i in range(60):
        base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
        ans += base_01_comb * (2**i)
        ans %= 10**9+7

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

base_2_cnt = [0]*60 
for a in al:
    for i in range(60):
        if ((a >> i) & 1): base_2_cnt[i] += 1

ans = 0
for i in range(60):
    base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
    ans += base_01_comb * (2**i)
    ans %= 10**9+7

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

Submission status: Time Limit Exceeded

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

base_2_cnt = [0]*60 
for a in al:
    for i in range(60):
        if ((a >> i) & 1): base_2_cnt[i] += 1

ans = 0
for i in range(60):
    base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
    ans += base_01_comb * (2**i)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Xor Sum 4
https://atcoder.jp/contests/abc147/tasks/abc147_d

"""
import sys


def solve(N, A):
    MOD = 10**9 + 7
    bit_len = max(map(int.bit_length, A))
    ans = 0
    for i in range(bit_len):
        zeros, ones = 0, 0
        for a in A:
            if (a & 1<<i):
                ones += 1
            else:
                zeros += 1
        ans = (ans + (ones * zeros * 2**i)) % MOD
    return ans % MOD


def main(args):
    N = int(input())
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Xor Sum 4
https://atcoder.jp/contests/abc147/tasks/abc147_d

"""
import sys


def solve(N, A):
    MOD = 10**9 + 7
    bit_len = max(map(int.bit_length, A))
    ans = 0
    for i in range(bit_len):
        zeros, ones = 0, 0
        for a in A:
            if (a & 1<<i):
                ones += 1
            else:
                zeros += 1
        ans += (ones * zeros * 2**i)
    return ans % MOD


def main(args):
    N = int(input())
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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


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

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

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


            if check[next_vertex]==True:
                continue

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

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

    return color

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



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

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

ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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


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

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

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


            if check[next_vertex]==True:
                continue

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

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

    return color

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



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

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

ans%=mod
print(ans)