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
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

n=int(input())
a=list(map(int, input().split()))
l0=[0]*60
l1=[0]*60
for i in range(n):
    b=bin(a[i])[::-1]
    #print(b)
    for j in range(60):
        if j<len(b)-2:
            if b[j]=="0":
                l0[j]+=1
            else:
                l1[j]+=1
        else:
            l0[j]+=1
#print(l0,l1)
ans=0
for i in range(60):
    ans+=l0[i]*l1[i]*(2**i)
    if ans>=10**9+7:
        ans%=(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

l=[0]*60
for i in A:
  for j in range(60):
    if i&(1<<j):l[j]+=1
ans=0
for i in range(60):
  ans+=l[i]*(N-l[i])*(1<<i)
  ans%=10**9+7
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

b = [0] * 65

for i in range(N):
    bb = format(A[i], "060b")
    for j in range(60):
        if bb[j] == "1":
            b[j] += 1

ans = 0

for j in range(60):
    ans = (ans + b[j] * (N - b[j]) * pow(2, 59 - j, mod)) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=10**9+7
a=list(map(int,input().split()))
bit=[0]*61
for i in range(n):
    b=bin(a[i])[2:].zfill(61)
    for j in range(61):
        if b[j]=="1":
            bit[j]+=1
ans=0
for i in range(61):
    x=bit.pop()
    ans+=x*(n-x)*(2**i)%p
print(ans%p)

Submission status: Time Limit Exceeded

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


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [[0]*60 for i in range(N)]
    for i in range(1, N):
        target = targets[N-i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[N-i-1][keta] = ttl_bins[N -
                                             i][keta] + int(target_str[keta])

    ttl_final = [0]*60
    for i in range(N-1):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            keta_int = int(target_str[keta])
            if keta_int == 0:
                ttl_others_1 = ttl_bins[i][keta]
                ttl_final[59 - keta] += ttl_others_1
            if keta_int == 1:
                ttl_others_0 = (N - i - 1) - ttl_bins[i][keta]
                ttl_final[59 - keta] += ttl_others_0

    ans = 0
    for i in range(60):
        ans += (ttl_final[i] * pow(2, i, MOD)) % MOD
        ans %= MOD

    print(ans)


main()

Submission status: Time Limit Exceeded

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


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [[0]*60 for i in range(N)]
    for i in range(1, N):
        target = targets[N-i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[N-i-1][keta] = ttl_bins[N -
                                             i][keta] + int(target_str[keta])

    ttl_final = [0]*60
    for i in range(N-1):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            keta_int = int(target_str[keta])
            if keta_int == 0:
                ttl_others_1 = ttl_bins[i][keta]
                ttl_final[59 - keta] += ttl_others_1
            if keta_int == 1:
                ttl_others_0 = (N - i - 1) - ttl_bins[i][keta]
                ttl_final[59 - keta] += ttl_others_0

    ans = 0
    for i in range(60):
        ans += ttl_final[i] * pow(2, i, MOD)
        ans %= MOD

    print(ans)


main()

Submission status: Time Limit Exceeded

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


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [[0]*60 for i in range(N)]
    for i in range(1, N):
        target = targets[N-i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[N-i-1][keta] = ttl_bins[N -
                                             i][keta] + int(target_str[keta])

    ans = 0

    for i in range(N-1):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            keta_int = int(target_str[keta])
            if keta_int == 0:
                ttl_others_1 = ttl_bins[i][keta]
                base = pow(2, 59-keta, MOD)
                ans += (ttl_others_1) * base
            if keta_int == 1:
                ttl_others_0 = (N - i - 1) - ttl_bins[i][keta]
                base = pow(2, 59-keta, MOD)
                ans += (ttl_others_0) * base
            ans = ans % MOD

    print(ans)


main()

Submission status: Time Limit Exceeded

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


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [[0]*60 for i in range(N)]
    for i in range(1, N):
        target = targets[N-i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[N-i-1][keta] = ttl_bins[N -
                                             i][keta] + int(target_str[keta])

    ans = 0

    for i in range(N-1):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            keta_int = int(target_str[keta])
            if keta_int == 0:
                ttl_others_1 = ttl_bins[i][keta]
                ans += (ttl_others_1) * (2 ** (59-keta)
                                         % MOD)
            if keta_int == 1:
                ttl_others_0 = (N - i - 1) - ttl_bins[i][keta]
                ans += (ttl_others_0) * (2 ** (59-keta)
                                         % MOD)
            ans = ans % MOD

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def nishin(n):
  return str(bin(n)[2:])[::-1]
N=int(input())
L=list(map(int,input().split()))
mod=1000000007
ans=sum(L)*(N-1)
c=[0]*61
for i in L:
  i=nishin(i)
  for j in range(len(i)):
    if i[j]=="1":
      c[j]+=1
for i in range(61):
  ans-=(pow(2,i,mod)*c[i]*(c[i]-1))%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
P = 10**9 + 7

N = int(input())
A = [int(x) for x in input().split()]

X = [[0,0] for _ in range(60)]
for k in range(60):
    for i in range(N):
        b = (A[i] >> k) & 1
        X[k][b] += 1

S = 0
pow2 = 1
for k in range(60):
    S = (S + pow2 * X[k][0] * X[k][1]) % P
    pow2 = 2 * pow2 % P

print(S)

Submission status: Time Limit Exceeded

Solution code:
P = 10**9 + 7

N = int(input())
A = [int(x) for x in input().split()]

X = [[0,0] for _ in range(60)]
for k in range(60):
    for i in range(N):
        b = (A[i] >> k) & 1
        X[k][b] += 1

S = 0
for k in range(60):
    S = (S + 2**k * X[k][0] * X[k][1]) % P

print(S)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
ans = 0
M = 60
bitlist = [1]
anslist = [0 for _ in range(M)]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while a:
        b = a & 1
        if b == 0:
            anslist[c] += counter[-c-1]
        else:
            anslist[c] += k - counter[-c-1]
            counter[-c-1] += 1
        c += 1
        a >>= 1
    while c < M:
        anslist[c] += counter[-c-1]
        c += 1
for k in range(M):
    ans += anslist[k]*bitlist[k]%mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
anslist = [0 for _ in range(M)]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while a:
        b = a & 1
        if b == 0:
            anslist[c] += counter[-c-1]
        else:
            anslist[c] += k - counter[-c-1]
            counter[-c-1] += 1
        c += 1
        a >>= 1
    while c < M:
        anslist[c] += counter[-c-1]
        c += 1
for k in range(M):
    ans += anslist[k]*bitlist[k]%mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
anslist = [0 for _ in range(M)]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while c < M:
        b = a & 1
        if b == 0:
            anslist[c] += counter[-c-1]
        else:
            anslist[c] += k - counter[-c-1]
            counter[-c-1] += 1
        c += 1
        a >>= 1
for k in range(M):
    ans += anslist[k]*bitlist[k]%mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = deque(map(int, input().split()))
mod = 10**9 + 7
M = len(bin(max(A))) - 2
ans = 0
bitlist = [1]
for k in range(M):
    bitlist.append(bitlist[-1]*2%mod)
counter = [0 for _ in range(M)]

for k in range(N):
    a = A.pop()
    c = 0
    while c < M:
        b = a & 1
        if b == 0:
            ans += counter[-c-1]*bitlist[c]%mod
            ans %= mod
        else:
            ans += (k-counter[-c-1])*bitlist[c]%mod
            ans %= mod
            counter[-c-1] += 1
        c += 1
        a >>= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7

ans=0
cnt=[0 for i in range(61)]

for i in range(n):
    now=A[i]
    bek=1
    for q in range(61):
        if now&1==0:
            ans+=cnt[q]*bek
        else:
            ans+=(i-cnt[q])*bek
        bek<<=1
        cnt[q]+=now&1
        now>>=1
    ans=ans%mod
    #print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

p=10**9+7

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

binA=[]
for i in range(n):
  binA.append(format(A[i],"060b"))

exp=[1]
for i in range(60):
  exp.append((exp[i]*2)%p)


ans=0
for i in range(60):
  num0=0
  num1=0
  for j in range(n):
    if binA[j][i]=="0":
      num0+=1
    else:
      num1+=1
  ans=(ans+num0*num1*exp[59-i])%p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

p=10**9+7

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

binA=[]
for i in range(n):
  binA.append(format(A[i],"060b"))


lis=[0 for i in range(60)]

for binAi in binA:
  for j in range(60):
    lis[j]+=int(binAi[j])

binary=[0 for i in range(60)]

for i in range(n):
  for j in range(60):
    if binA[i][j]=="0":
      binary[j]+=lis[j]
    else:
      binary[j]+=n-lis[j]


binary[58]+=binary[59]//2
binary[59]=0


explis=[1]

for i in range(60):
  explis.append((explis[i]*2)%p)

ans=0
for i in range(59):
  ans=(ans+binary[i]*explis[58-i])%p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
k=1
for i in range(61):
    count0=0
    count1=0
    for j in a:
        if not (j>>i & 1):
            count0+=1
        if j>>i & 1:
            count1+=1
    ans+=((count0*count1)*(k))%mod
    k=(2*k)%mod
    
    
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(61):
    count0=0
    count1=0
    for j in a:
        if not (j>>i & 1):
            count0+=1
        if j>>i & 1:
            count1+=1
    ans+=((count0*count1)*(2**i))%mod
    
print(ans%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

pows = [pow(2, i, mod) for i in range(60)]
count = [0]*60
num = [0]*60
ans = 0

for i in range(n):
    bit = a[i]
    for g in range(60):
        if bit % 2 == 1:
            count[g] += 1
            num[g] += i+1 - count[g]
        else:
            num[g] += count[g]
        bit //= 2

for i in range(60):
    ans += num[i]*pows[i]

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
num=[0]*63
for i in range(n):
    num1=a[i]
    for j in range(63):
        if num1==0:
            break
        if num1%2==1:
            num[j]+=1
        num1//=2
ans=0
for i in range(63):
    if num[i]!=0 and num[i]!=n:
        ans+=((2**i)*num[i]*(n-num[i]))%(10**9+7)
ans%=10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
n = int(input())
a_ls = list(map(int, input().split()))
c_bin = [[0]*60 for _ in range(n)]
a_bin_ls = [[0]*60 for _ in range(n)]
now_bin = [0] * 60
for i in range(n-1,-1,-1):
    a = a_ls[i]
    j = 0
    while True:
        if a == 1:
            now_bin[j] += 1
            a_bin_ls[i][j] = 1
            break
        elif a == 0:
            break
        a,r = divmod(a,2)
        now_bin[j] += r 
        a_bin_ls[i][j] = r
        j += 1
    c_bin[i] = copy(now_bin)
ans_bin = [0]*60
for i in range(n-1):
    a_bin = a_bin_ls[i]
    for j in range(60):
        if a_bin[j] == 0:
            times = c_bin[i+1][j]
        else:
            times = n - (i+1) - c_bin[i+1][j]
        ans_bin[j] += times
ans = 0
mod = 10**9+7
for i in range(60):
    ans += 2**i * (ans_bin[i]%mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
ans = 0

for k in range(60):
    x, y = 0, 0
    for a in A:
        x += 1 & a>>k
    tmp = x*(n-x)%mod
    tmp *= pow(2, k, mod)
    ans += tmp
    ans %= mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
ans = 0

for k in range(60):
    x, y = 0, 0
    for a in A:
        x += 1 & a>>k
    tmp = x*(n-x)%mod
    tmp *= pow(2, k, mod)
    ans += tmp%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
ans = 0

for k in range(60):
    x, y = 0, 0
    for a in A:
        x += 1 & a>>k
    ans += x*(n-x)*pow(2, k, mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
ans = 0

for k in range(60):
    x, y = 0, 0
    for a in A:
        if a & 1<<k:
            x += 1
    ans += x*(n-x)*pow(2, k, mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
ans = 0

for k in range(60):
    x = 0
    y = 0
    for a in A:
        if a & 1<<k:
            x += 1
        else:
            y += 1
    ans += x*y*pow(2, k, mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
ans = 0
for C in itertools.combinations(a, 2):
    ans += (C[0]^C[1])%mod
    ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
a = list(map(int, input().split()))
num = 0
for i in itertools.combinations(a,2):
    num += (i[0]^i[1])
print(num%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
B = [bin(a) for a in A]

maxA = max(A)
mask = 1

count = 0
i = 0
while maxA >> i:
    zeros = sum([1 for a in A if (mask * 2**i) & a == 0]) % MOD
    ones = (len(A) - zeros) % MOD
    count += zeros * ones * ((2**i) % MOD)
    count %= MOD
    i += 1

print(count)

Submission status: Time Limit Exceeded

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
B = [bin(a) for a in A]

maxA = max(A)
mask = 1

count = 0
i = 0
while maxA >> i:  # ここが違う
    zeros = sum([1 for a in A if (mask * 2**i) & a == 0])
    ones = len(A) - zeros
    count += zeros * ones * 2**i
    count %= MOD
    i += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

def main():
    mod = 10**9+7
    n = ii()
    a = li()
    bi = [0]*60
    for x in a:
        for i in range(60):
            if (x>>i)&1:
                bi[i]+= 1
    ans = 0
    for i in range(60):
        tmp = bi[i]*(n-bi[i])*(1<<i)
        tmp %= mod
        ans += tmp
        ans %= mod

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

n = int(input())
alst = list(map(int, input().split()))
bin_s = [2 ** i for i in range(60)]
cnt = [0 for _ in range(60)]

for a in alst:
    for j in range(60):
        if bin_s[j] & a:
            cnt[j] += 1

ans = 0
for i in range(60):
    ans += bin_s[i] * cnt[i] * (n - cnt[i])
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans=0
for i in range(60):
  g = [0,0]
  for j in a:
    g[(j>>i)%2]+=1
  ans+=2**i*g[0]*g[1]
  ans%=10**9+7
print(ans)

Submission status: Time Limit Exceeded

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

#n=10
#a=[3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a=[3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

mod=10**9+7
asum=0
for i in range(60):
    zcnt=0
    for ii in range(n):
        asht=a[ii]>>i
        if asht&1==0:
            zcnt+=1
    tmp=(zcnt*(n-zcnt))%mod*((2**i)%mod)
    asum+=(tmp)%mod
               
asum=asum%mod
print(asum)

Submission status: Time Limit Exceeded

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

mod=10**9+7
asum=0
for i in range(n-1):
    for j in range(i+1,n):
        asum+=(a[i]^a[j])%mod

asum=asum%mod
print(asum)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    m = 10 ** 9 + 7
    ans = 0

    for i in range(N - 1):
        for j in range(i + 1, N):
            tmp = a[i] ^ a[j]
            ans += tmp % m
            ans %= m

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
A = [int(x) for x in input().split()]
ans = 0
mod = 10 ** 9 + 7
# 制約がai <= 2^60なので
for d in range(61):
    # d桁目ごとに考える
    x = 0
    for a in A:
        if (a >> d) & 1:
            x += 1
    ans += x * (n-x) * 2**d
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
ans = 0
mod = 10 ** 9 + 7
for d in range(60):
    # d桁目ごとに考える
    x = 0
    for a in A:
        if (a >> d) & 1:
            x += 1
    ans += x * (n-x) * 2**d
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    
    ans+= ((pow(2,59-i,mod)* (q*(n-q)))%mod)%mod
    ans%=mod


print(ans)

Submission status: Time Limit Exceeded

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    ans+= ((pow(2,59-i,mod)* (q*(q-1)))%mod *pow(2,mod-2,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)

Submission status: Time Limit Exceeded

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=now.count(1)
    ans+= ((pow(2,59-i,mod)* (q*(q-1)))%mod *pow(2,mod-2,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)

Submission status: Time Limit Exceeded

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=np.count_nonzero(now)
    ans+= ((pow(2,59-i,mod)* (q*(q-1))%mod)%mod *pow(2,-1,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)

Submission status: Time Limit Exceeded

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    for j in range(n):
        TB[i][j] = B[j][i]
        
import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=np.count_nonzero(now)
    ans+= ((pow(2,59-i,mod)* (q*(q-1))%mod)%mod *pow(2,-1,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)

Submission status: Time Limit Exceeded

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    for j in range(n):
        TB[i][j] = B[j][i]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=now.count(1)
    ans+= ((pow(2,59-i,mod)* (q*(q-1))%mod)%mod *pow(2,-1,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)

Submission status: Time Limit Exceeded

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

c = [n]*61
for i in range(n):
    b = str(bin(a[i]))[2:]
    b = b[::-1]
    for j, x in enumerate(b):
        if x == "1":
            c[j] -= 1

ans = 0
for i in range(60):
    ans += c[i]*(n-c[i])*pow(2,i,mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9 + 7)
n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(62):
    cnt = 0
    for a in A:
        if a & 1<<i:
            cnt += 1
    ans += (1<<i % MOD) * cnt % MOD * (n - cnt) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9 + 7)
n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(62):
    cnt = 0
    for a in A:
        if a & 1<<i:
            cnt += 1
    ans += (1<<i % MOD) * cnt * (n - cnt) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

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

ans = 0
x = 1
for d in range(60):
    odd = 0
    even = 0
    for a in A:
        if a & (1 << d):
            odd += 1
        else:
            even += 1
    ans += odd * even * x
    ans %= MOD
    x <<= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
bits = [0]*60
for x in a:
    i = 0
    while x > 0:
        if x % 2 == 1:
            bits[i] += 1
        x //= 2
        i += 1
ans = 0
for i in range(60):
    ans += (bits[i] * (n-bits[i])) * pow(2, i, mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
C = [0] * 60
for a in A:
    for i in range(60):
        if a>>i&1:
            C[i] += 1
ans = 0
for i, c in enumerate(C):
    ans += (1<<i) * c * (N-c) % mod
print(ans % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n=INT()
    a=np.array(LIST())
    ans=0
    mod=10**9+7
    for i in range(70):
        digit=sum((a>>i)&1)
        ans+=pow(2,i,mod)*(((n-digit)*digit)%mod)
        ans=ans%mod
    
    print(ans)



if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n=INT()
    a=np.array(LIST())
    ans=0
    mod=10**9+7
    for i in range(70):
        digit=sum((a>>i)&1)
        ans+=((2**i)%mod)*(((n-digit)*digit)%mod)
        ans=ans%mod
    
    print(ans)



if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
x = max(l)
s = bin(x)
u = len(s)-2
o = [0]*u
for i in l:
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u - len(a)
    a = (["0"] * d) + a
    j = 0
    while(j < len(o)):
        if a[j] == "1":
            o[j] = o[j]+1

        j = j+1

cnt = 0
z = len(o)*[0]
for i in range(len(o)):
    z[i] = len(l)-o[i]


for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    j = u-1
    y = 0
    while(j > -1):
        if a[y] == "1":
            #print(o[])
            o[y] = o[y] - 1

        if a[y] == "0":
            z[y] = z[y]-1

        y = y+1
        j = j-1

    j = u-1
    y = 0
    while(j > -1):
        if a[y] == "0":
            cnt = (cnt+((2**j)*o[y])%M)%M

        if a[y] == "1":
            cnt = (cnt + ((2 ** j) * z[y]) % M) % M

        y = y+1
        j = j-1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
o = [0]*61
z = [0]*61
for i in l:
    a = bin(i)[2:]
    j = 0
    while(j < len(a)):
        if a[j] == "1":
            o[len(a)-j-1] = o[len(a)-j-1]+1

        j = j+1

cnt = 0
b = 1
for j in range(len(o)):
    cnt = (cnt+(o[j]*(n-o[j])*b)%M)%M
    b = b*2

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
o = [0]*61
z = [0]*61
for i in l:
    a = bin(i)
    a = a[2:]
    j = 0
    while(j < len(a)):
        if a[j] == "1":
            o[len(a)-j-1] = o[len(a)-j-1]+1

        j = j+1

cnt = 0
b = 1
for j in range(len(o)):
    cnt = (cnt+(o[j]*(n-o[j])*b)%M)%M
    b = b*2

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
x = max(l)
s = bin(x)
u = len(s)-2
o = [0]*u
z = [0]*u
for i in l:
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u - len(a)
    a = (["0"] * d) + a
    j = 0
    while(j < len(o)):
        if a[j] == "1":
            o[j] = o[j]+1

        else:
            z[j] = z[j]+1

        j = j+1


o = o[::-1]
z = z[::-1]
cnt = 0
for j in range(len(o)):
    cnt = (cnt+((o[j]*z[j]*(2**j))%M))%M


print(cnt)