Problem:


Score : 400 points

Problem Statement

We have N integers. The i-th integer is A_i.

Find \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

2 \leq N \leq 3 \times 10^5

0 \leq A_i < 2^{60}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the value \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

Sample Input 1

3
1 2 3

Sample Output 1

6

We have (1\mbox{ XOR } 2)+(1\mbox{ XOR } 3)+(2\mbox{ XOR } 3)=3+2+1=6.

Sample Input 2

10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

237

Sample Input 3

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

Sample Output 3

103715602

Print the sum modulo (10^9+7).



Sample input:
3
1 2 3


Sample output:
6

Submission status: Runtime Error

Solution code:
import math

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

digit = math.floor(math.log2(max(A))) + 1
bin_A = [format(Ai, '0' + str(digit) + 'b') for Ai in A]

ans = 0

for i in range(digit):
    num0 = 0
    num1 = 0
    for j in range(N):
        if bin_A[j][i] == '1':
            num1 += 1
        else:
            num0 += 1
    ans += (num1 * num0) * (2**(digit-i-1))

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

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"runtime/pprof"
	"strconv"
)

func main() {
	f, err := os.Create("cpu.prof")
	if err != nil {
		log.Fatal("could not create CPU profile: ", err)
	}
	if err := pprof.StartCPUProfile(f); err != nil {
		log.Fatal("could not start CPU profile: ", err)
	}
	defer pprof.StopCPUProfile()

	N := readInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = readInt()
	}

	result := 0
	bs := make([]int, N)
	for b := 0; b < 60; b++ {
		t := 0
		bs[N-1] = (A[N-1] >> uint(b)) & 1
		for i := N - 2; i > -1; i-- {
			a := (A[i] >> uint(b)) & 1
			bs[i] = bs[i+1] + a
			if a == 0 {
				t += bs[i+1]
			} else {
				t += (N - (i + 1)) - bs[i+1]
			}
		}
		t %= 1000000007
		B := (1 << uint(b)) % 1000000007
		result += (t * B) % 1000000007
		result %= 1000000007
	}
	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	N := readInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = readInt()
	}

	result := 0
	for b := 0; b < 60; b++ {
		a := make([]int, N)
		for i := 0; i < N; i++ {
			a[i] = (A[i] >> uint(b)) & 1
		}

		bs := make([]int, N)
		bs[N-1] = a[N-1]
		for i := N - 2; i > -1; i-- {
			bs[i] = bs[i+1] + a[i]
		}

		t := 0
		for i := 0; i < N-1; i++ {
			if a[i] == 0 {
				t += bs[i+1]
			} else {
				t += (N - (i + 1)) - bs[i+1]
			}
			t %= 1000000007
		}
		B := (1 << uint(b)) % 1000000007
		result += (t * B) % 1000000007
		result %= 1000000007
	}
	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

MOD = 10 ** 9 + 7

n, *a = map(int, sys.stdin.read().split())
a = np.array(a, dtype=np.int64)

powmod = [None] * 100
powmod[0] = 1
for i in range(60):
    powmod[i+1] = powmod[i] * 2 % MOD

def main():
    b = a >> np.arange(60).reshape(-1, 1) & 1
    x = np.count_nonzero(b, axis=1)
    y = n - x
    x *= y
    x *= powmod[:60]
    x %= MOD
    ans = np.sum(x) % MOD
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

MOD = 10 ** 9 + 7

n, *a = map(int, sys.stdin.read().split())
a = np.array(a, dtype=np.int64)

powmod = [None] * 100
powmod[0] = 1
for i in range(60):
    powmod[i+1] = powmod[i] * 2 % MOD
    
def main():
    b = a >> np.arange(60).reshape(-1, 1) & 1
    x = np.count_nonzero(b, axis=1)
    x = x * (n - x)
    x *= powmod[:60]
    x %= MOD
    ans = np.sum(x) % MOD
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

MOD = 10 ** 9 + 7

n, *a = map(int, sys.stdin.read().split())
a = np.array(a, dtype=np.int64)

def main():
    b = a >> np.arange(61).reshape(-1, 1) & 1
    x = np.count_nonzero(b, axis=1)
    x = x * (n - x) % MOD
    # x *= 2 ** np.arange(60) % MOD
    for i in range(1, 61):
        x[i] *= pow(2, i, MOD)
    x %= MOD
    ans = np.sum(x) % MOD
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

MOD = 10 ** 9 + 7

n, *a = map(int, sys.stdin.read().split())
a = np.array(a, dtype=np.int64)

def main():
    b = a >> np.arange(60).reshape(-1, 1) & 1
    x = np.count_nonzero(b, axis=1)
    x = x * (n - x) % MOD
    # x *= 2 ** np.arange(60) % MOD
    for i in range(60):
        x[i] *= pow(2, i, MOD)
    x %= MOD
    ans = np.sum(x) % MOD
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
ans = 0
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
for i in range(p):
    c1 = sum(l)
    ans += (2**(p - i - 1)) * c1 * (n - c1)
    ans %= (10**9 + 7)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

# s = [0]*61
# for a in A:
#     for i in range(61):
#         # print(cnt,a)
#         if(a>>i&1)==1:
#             s[i+1] += 1
ans = 0
for i in range(61):
    # print("a",2**(i-1)*s.get(i,0)*(n-s.get(i,0)))
    # print("b",s.get(i,0))
    # print("c",(n-s.get(i,0)))
    ans += 2**(i-1)*s[i]*(n-s[i])
ans = ans % (10**9+7)
print(int(ans))
# print(s)

Submission status: Runtime Error

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

s = [0]*60
for a in A:
    cnt = 0
    while a != 0:
        # print(cnt,a)
        if(a&1)==1:
            s[cnt+1] += 1
        cnt+=1
        a = a >> 1
ans = 0
for i in range(60):
    # print("a",2**(i-1)*s.get(i,0)*(n-s.get(i,0)))
    # print("b",s.get(i,0))
    # print("c",(n-s.get(i,0)))
    ans += (2**(i-1)*s[i]*(n-s[i])) % (10**9+7)
ans = ans % (10**9+7)
print(int(ans))
# print(s)

Submission status: Runtime Error

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

s = [0]*60
for a in A:
    cnt = 0
    while a != 0:
        # print(cnt,a)
        if(a&1)==1:
            s[cnt+1] += 1
        cnt+=1
        a = a >> 1
ans = 0
for i in range(60):
    # print("a",2**(i-1)*s.get(i,0)*(n-s.get(i,0)))
    # print("b",s.get(i,0))
    # print("c",(n-s.get(i,0)))
    ans += (2**(i-1)*s.get(i,0)*(n-s.get(i,0))) % (10**9+7)
ans = ans % (10**9+7)
print(int(ans))
# print(s)

Submission status: Runtime Error

Solution code:
//#pragma GCC optimize("O3")
//#pragma GCC target("avx")

#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// Types
using ll = long long int;
using str = string;
template <class T> using u_set = unordered_set<T>;
template <class K, class V> using u_map = unordered_map<K, V>;
template <class V> using graph = u_map<V, u_set<V>>;
template <class F,
          typename enable_if<is_function<F>::value, nullptr_t>::type = nullptr>
using fun = function<F>;

namespace io {
// Input
using IS = istream;
IS &in(IS &i);
IS &in(IS &i) { return i; }
template <class T, class... Ts> IS &in(IS &i, T &a, Ts &... as) {
  return in(i >> a, as...);
}
template <class V> IS &operator>>(IS &i, vector<V> &a) {
  for_each(a.begin(), a.end(), [&i](auto &e) { i >> e; });
  return i;
}
template <class F, class S> IS &operator>>(IS &i, pair<F, S> &p) {
  return in(i, p.first, p.second);
}
template <class... Ts, size_t... I>
IS &tuple_in(IS &i, tuple<Ts...> &t, index_sequence<I...>) {
  return in(i, get<I>(t)...);
}
template <class... Ts> IS &operator>>(IS &i, tuple<Ts...> &t) {
  return tuple_in(i, t, make_index_sequence<sizeof...(Ts)>());
}
// Output
using OS = ostream;
OS &out(OS &o) { return o << endl; }
template <class T> OS &out(OS &o, T const &a) { return o << a << endl; }
template <class T, class... Ts> OS &out(OS &o, T const &a, Ts const &... as) {
  return out(o << a << " ", as...);
}
template <class F, class S> OS &operator<<(OS &o, pair<F, S> const &p) {
  return o << p.first << ":" << p.second;
}
template <class... Ts> OS &args_out(OS &o, Ts const &... ts);
OS &args_out(OS &o) { return o; }
template <class T> OS &args_out(OS &o, T const &t) { return o << t; }
template <class T0, class T1, class... Ts>
OS &args_out(OS &o, T0 const &t0, T1 const &t1, Ts const &... ts) {
  return args_out(o << t0 << ",", t1, ts...);
}
template <class... Ts, size_t... I>
OS &tuple_out(OS &o, tuple<Ts...> const &t, index_sequence<I...>) {
  return args_out(o, get<I>(t)...);
}
template <class... Ts> OS &operator<<(OS &o, tuple<Ts...> const &t) {
  return tuple_out(o << "(", t, make_index_sequence<sizeof...(Ts)>()) << ")";
}
template <
    class C,
    class T = typename iterator_traits<typename C::iterator>::value_type,
    typename enable_if<!is_same<C, str>::value, nullptr_t>::type = nullptr>
OS &operator<<(OS &o, C const &a) {
  return a.empty() ? (o << "[]") : ([&o, &a]() -> OS & {
    o << "[" << *a.begin();
    for_each(next(a.begin()), a.end(), [&o](auto const &e) { o << "," << e; });
    return o << "]";
  }());
}
} // namespace io
auto input = [](auto &... a) { io::in(cin, a...); };
auto print = [](auto const &... a) { io::out(cout, a...); };
#ifdef JUMPAKU_DEBUG
auto dump = [](auto const &... a) { io::out(cout, a...); };
#else
auto dump = [](auto const &... a) {};
#endif

// Hash
namespace hashcode {
template <class... Ts> size_t hash_args(size_t h, Ts const &... ts);
size_t hash_args(size_t h) { return h; }
template <class T, class... Ts>
size_t hash_args(size_t h, T const &t, Ts const &... ts) {
  return hash_args(((h << 10) - h + hash<T>{}(t)), ts...);
}
template <class... Ts, size_t... I>
size_t hash_tuple(tuple<Ts...> const &t, index_sequence<I...>) {
  return hash_args(1089283, get<I>(t)...);
}
} // namespace hashcode
namespace std {
template <class... Ts> struct hash<tuple<Ts...>> {
  size_t operator()(tuple<Ts...> const &t) const {
    return hashcode::hash_tuple(t, index_sequence_for<Ts...>());
  }
};
} // namespace std

// Range
vector<ll> range(ll const &begin, ll const &end) {
  vector<ll> ret(max(0LL, end - begin));
  iota(ret.begin(), ret.end(), begin);
  return ret;
}
vector<ll> range(ll const &end) { return range(0, end); }
template <class T = ll> vector<T> vec(size_t n, T &&init = T()) {
  return vector<T>(n, init);
}
template <class Itr, class T = typename iterator_traits<Itr>::value_type>
vector<T> vec(Itr begin, Itr end) {
  return vector<T>(begin, end);
}

ll bisect(ll ng, ll ok, fun<bool(ll)> const &is_ok) {
  while (ok - ng > 1) {
    dump(ng, ok);
    ll m = ng + (ok - ng) / 2;
    (is_ok(m) ? ok : ng) = m;
  }
  return ok;
}
ll gcd(ll p, ll q) { return (q == 0) ? p : gcd(q, p % q); }
ll lcm(ll p, ll q) { return p * q / gcd(q, p); }

// MOD
ll pow(ll a, ll n, ll m) {
  if (n == 0)
    return 1;
  if (n & 1)
    return ((a % m) * pow(a, n - 1, m)) % m;
  auto b = pow(a, n / 2, m);
  return (b * b) % m;
}
ll inv(ll a, ll p) { return pow(a, p - 2, p); }
constexpr ll MOD = 1e9 + 7;

int main() {
  ll N;
  input(N);
  auto A = vec(N);
  input(A);
  dump(A);
  auto const bitOf = [](ll a, int k) { return 0 != (a & (1LL << k)); };
  ll ans = 0LL;
  for (auto &&k : range(60)) {
    auto Ak = vec(N);
    transform(A.begin(), A.end(), Ak.begin(),
              [&](auto ai) { return bitOf(ai, k); });
    auto Sk = Ak;
    partial_sum(Sk.rbegin(), Sk.rend(), Sk.rbegin());
    auto Bk = vec(N);
    transform(A.begin(), A.end(), Bk.begin(),
              [&](auto ai) { return !bitOf(ai, k); });
    auto Tk = Bk;
    partial_sum(Tk.rbegin(), Tk.rend(), Tk.rbegin());
    dump(k, Ak, Sk, Bk, Tk);
    ll ansK = 0LL;
    for (auto &&i : range(N - 1)) {
      dump(A[i], bitOf(A[i], k));
      ansK += (bitOf(A[i], k) ? Tk : Sk)[i + 1];
      ansK %= MOD;
    }
    for (auto &&i : range(k)) {
      ansK *= 2;
      ansK %= MOD;
    }
    ans += ansK;
    ans %= MOD;
  }
  print(ans);
}

Submission status: Runtime Error

Solution code:
//#pragma GCC optimize("O3")
//#pragma GCC target("avx")

#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// Types
using ll = long long int;
using lll = __int128_t;
using str = string;
template <class T> using u_set = unordered_set<T>;
template <class K, class V> using u_map = unordered_map<K, V>;
template <class V> using graph = u_map<V, u_set<V>>;
template <class F,
          typename enable_if<is_function<F>::value, nullptr_t>::type = nullptr>
using fun = function<F>;

namespace io {
// Input
using IS = istream;
IS &in(IS &i);
IS &in(IS &i) { return i; }
template <class T, class... Ts> IS &in(IS &i, T &a, Ts &... as) {
  return in(i >> a, as...);
}
template <class V> IS &operator>>(IS &i, vector<V> &a) {
  for_each(a.begin(), a.end(), [&i](auto &e) { i >> e; });
  return i;
}
template <class F, class S> IS &operator>>(IS &i, pair<F, S> &p) {
  return in(i, p.first, p.second);
}
template <class... Ts, size_t... I>
IS &tuple_in(IS &i, tuple<Ts...> &t, index_sequence<I...>) {
  return in(i, get<I>(t)...);
}
template <class... Ts> IS &operator>>(IS &i, tuple<Ts...> &t) {
  return tuple_in(i, t, make_index_sequence<sizeof...(Ts)>());
}
// Output
using OS = ostream;
OS &out(OS &o) { return o << endl; }
template <class T> OS &out(OS &o, T const &a) { return o << a << endl; }
template <class T, class... Ts> OS &out(OS &o, T const &a, Ts const &... as) {
  return out(o << a << " ", as...);
}
template <class F, class S> OS &operator<<(OS &o, pair<F, S> const &p) {
  return o << p.first << ":" << p.second;
}
template <class... Ts> OS &args_out(OS &o, Ts const &... ts);
OS &args_out(OS &o) { return o; }
template <class T> OS &args_out(OS &o, T const &t) { return o << t; }
template <class T0, class T1, class... Ts>
OS &args_out(OS &o, T0 const &t0, T1 const &t1, Ts const &... ts) {
  return args_out(o << t0 << ",", t1, ts...);
}
template <class... Ts, size_t... I>
OS &tuple_out(OS &o, tuple<Ts...> const &t, index_sequence<I...>) {
  return args_out(o, get<I>(t)...);
}
template <class... Ts> OS &operator<<(OS &o, tuple<Ts...> const &t) {
  return tuple_out(o << "(", t, make_index_sequence<sizeof...(Ts)>()) << ")";
}
template <
    class C,
    class T = typename iterator_traits<typename C::iterator>::value_type,
    typename enable_if<!is_same<C, str>::value, nullptr_t>::type = nullptr>
OS &operator<<(OS &o, C const &a) {
  return a.empty() ? (o << "[]") : ([&o, &a]() -> OS & {
    o << "[" << *a.begin();
    for_each(next(a.begin()), a.end(), [&o](auto const &e) { o << "," << e; });
    return o << "]";
  }());
}
} // namespace io
auto input = [](auto &... a) { io::in(cin, a...); };
auto print = [](auto const &... a) { io::out(cout, a...); };
#ifdef JUMPAKU_DEBUG
auto dump = [](auto const &... a) { io::out(cout, a...); };
#else
auto dump = [](auto const &... a) {};
#endif

// Hash
namespace hashcode {
template <class... Ts> size_t hash_args(size_t h, Ts const &... ts);
size_t hash_args(size_t h) { return h; }
template <class T, class... Ts>
size_t hash_args(size_t h, T const &t, Ts const &... ts) {
  return hash_args(((h << 10) - h + hash<T>{}(t)), ts...);
}
template <class... Ts, size_t... I>
size_t hash_tuple(tuple<Ts...> const &t, index_sequence<I...>) {
  return hash_args(1089283, get<I>(t)...);
}
} // namespace hashcode
namespace std {
template <class... Ts> struct hash<tuple<Ts...>> {
  size_t operator()(tuple<Ts...> const &t) const {
    return hashcode::hash_tuple(t, index_sequence_for<Ts...>());
  }
};
} // namespace std

// Range
vector<ll> range(ll const &begin, ll const &end) {
  vector<ll> ret(max(0LL, end - begin));
  iota(ret.begin(), ret.end(), begin);
  return ret;
}
vector<ll> range(ll const &end) { return range(0, end); }
template <class T = ll> vector<T> vec(size_t n, T &&init = T()) {
  return vector<T>(n, init);
}
template <class Itr, class T = typename iterator_traits<Itr>::value_type>
vector<T> vec(Itr begin, Itr end) {
  return vector<T>(begin, end);
}

ll bisect(ll ng, ll ok, fun<bool(ll)> const &is_ok) {
  while (ok - ng > 1) {
    dump(ng, ok);
    ll m = ng + (ok - ng) / 2;
    (is_ok(m) ? ok : ng) = m;
  }
  return ok;
}
ll gcd(ll p, ll q) { return (q == 0) ? p : gcd(q, p % q); }
ll lcm(ll p, ll q) { return p * q / gcd(q, p); }

// MOD
ll pow(ll a, ll n, ll m) {
  if (n == 0)
    return 1;
  if (n & 1)
    return ((a % m) * pow(a, n - 1, m)) % m;
  auto b = pow(a, n / 2, m);
  return (b * b) % m;
}
ll inv(ll a, ll p) { return pow(a, p - 2, p); }
constexpr ll MOD = 1e9 + 7;

int main() {
  ll N;
  input(N);
  auto A = vec(N);
  input(A);
  dump(A);
  auto const bitOf = [](ll a, int k) { return 0 != (a & (1LL << k)); };
  ll ans = 0;
  for (auto &&k : range(60)) {
    auto Ak = vec(N);
    transform(A.begin(), A.end(), Ak.begin(),
              [&](auto ai) { return bitOf(ai, k); });
    auto Sk = Ak;
    partial_sum(Sk.rbegin(), Sk.rend(), Sk.rbegin());
    auto Bk = vec(N);
    transform(A.begin(), A.end(), Bk.begin(),
              [&](auto ai) { return !bitOf(ai, k); });
    auto Tk = Bk;
    partial_sum(Tk.rbegin(), Tk.rend(), Tk.rbegin());
    dump(k, Ak, Sk, Bk, Tk);
    lll ansK = 0;
    for (auto &&i : range(N - 1)) {
      dump(A[i], bitOf(A[i], k));
      ansK += (bitOf(A[i], k) ? Tk : Sk)[i + 1];
      ansK %= MOD;
    }
    ansK <<= k;
    ansK %= MOD;
    ans += ansK;
    ans %= MOD;
  }
  print(ans);
}

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
com=[(x^y)%mod for x in a for y in a]
print(sum(comb)//2%mod)

Submission status: Runtime Error

Solution code:
def fold(x,m):
    y = 0
    for _ in range(m):
        if x & 1:
            y |= 1
        y <<= 1
        x >>= 1
    return x|y



h,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
b = [list(map(int, input().split())) for _ in range(h)]
g = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    g[i][j] = abs(a[i][j] - b[i][j])
a = b = 0
m = max(max(x) for x in g)
mask = (1<<(m*(h+w+2)//2)) - 1

dp = [[0]*(w+1) for _ in range(h+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1,h+1):
  for j in range(1,w+1):
    par = dp[i-1][j] | dp[i][j-1]
    dp[i][j] = mask&(par<<g[i-1][j-1])|fold(par,g[i-1][j-1])
for i in range(m*(h+w+2)//2):
  if dp[h][w]&(1<<i):
    print(i)
    break

Submission status: Runtime Error

Solution code:
n = input()
a = map(int, input().split(" "))
s = 0
l = len(a)
for i in range(l):
  for j in range(i+1, l):
    s += i ^ j

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

Submission status: Runtime Error

Solution code:
import numpy as np
 
N = int(input())
A = list(input().split())
d_to_num1 = {}
max_len = 0
for i in range(N):
    a = list(bin(int(A[i]))[2:])
    if max_len <= len(a):
        max_len = len(a)
    for j,b in enumerate(reversed(a)):
        if b=='1':
            if not(j in d_to_num1.keys()):
                d_to_num1[j]=1
            else:
                d_to_num1[j]+=1 
        
if __name__ == "__main__":
 
    res = 0
    mod = 10**9+7
 
    for i in range(max_len):
        if not(i in d_to_num1.keys()):
            num_1 = 0
        else:
            num_1 = d_to_num1[i]
        num_0 = (N-num_1)%mod
        tmp = 1
        tmp *= num_1
        tmp %= mod
        tmp *= num_0
        tmp %= mod
        for _ in range(i):
            tmp = (tmp*2)%mod
        res += tmp%mod
        res %= mod
    print(res)

Submission status: Runtime Error

Solution code:
def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    # 繰り上がり処理ありバージョン
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  def get_ret_from_xs2(xs: List[int]) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * x
      ret %= 10**9 + 7
    return ret

  # zeros = [1, 1] + [0] * 58  # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  # ones = [2, 2] + [0] * 58 # 各要素 0 ~ n. 要素iは、下 i +1 桁目が0である A_? の個数
  zeros = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      # a_bin = format(a, '060b')
      # a_i_digit_from_right = a_bin[60 - i - 1]
      # if a_i_digit_from_right == '0':
      #   zeros[i] += 1
      # else:
      #   ones[i] += 1

      a_i_digit_from_right = ((a & (2**i)) >> i) & 0b1
      if a_i_digit_from_right == 0:
        zeros[i] += 1

  # 繰り上がり処理しないでも、各桁で収めてもいいんだ！
  xs = [zeros[i] * (len(a_s) - zeros[i]) for i in range(60)]
  return get_ret_from_xs2(xs)


  # # 繰り上がりのせいで、xsの要素数は60を超えることがあるので注意
  # xs = []
  # i = 0
  # while True:
  #   x_i = 0
  #   if i <= 59:
  #     x_i = (zeros[i] * ones[i])
  #   if i >= 1:
  #     x_i += xs[i - 1] // 2
  #   xs.append(x_i)
  #
  #   if i >= 60 and x_i // 2 == 0:
  #     break
  #
  #   i += 1

  #xs = [2, 3, 1]
  #return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

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

print(solve(a_s))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input()))
DIV=10**9+7
ans=0
if n%2==0:
  ans=a[0]
  for i in range(1,len(a)):
    ans+=ans^a[i]
    ans%=DIV
else:
  ans=a[0]^a[0]
  for i in range(1,len(a)):
    ans+=ans^(a[i]^a[i])
    ans%=DIV
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math

N = int(input())
A = [int(i) for i in input().split()]
s = 0
c = 1
for i in range(int(math.log2(max(A))+1)):
    #print(max(A))
    s0 = 0
    s1 = 0
    for i,j in enumerate(A):
        A[i],mod = divmod(j,2)
        if mod==1:
            s1 +=1
        else:
            s0 +=1
    s = (s+(s0*s1*c)%(10**9+7))%(10**9+7)
    c *= 2
print(s)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
 
n = int(input())
lst = [int(i) for i in sys.stdin.readline().split()]
arr = np.array(lst, np.int64)

mod = 10 ** 9 + 7
x_sum = 0

for i in range(60):
    c1 = sum(lst & 1)
    x_sum += (c1 * (n - c1) * 2 ** i)
    x_sum %= mod
    lst >>= 1
print(x_sum)

Submission status: Runtime Error

Solution code:
N = int(input())

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

ones = [0] * 60
m = 10 ** 9 + 7

for Ai in A:
    for digit in range(len(bin(Ai) - 2)):
        ones[digit] += ((Ai >> digit) & 1)

res = 0
for i, num in enumerate(ones):
    res = (res + (1 << i) * num * (N - num)) % m

print(res)

Submission status: Runtime Error

Solution code:
N = int(input())

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

ones = [0] * 60
m = 10 ** 9 + 7

for Ai in A:
    for digit in len(bin(Ai) - 2):
        ones[digit] += ((Ai >> digit) & 1)

res = 0
for i, num in enumerate(ones):
    res = (res + (1 << i) * num * (N - num)) % m

print(res)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
 
n = int(input())
lst = [int(i) for i in sys.stdin.readline().split()]
mod = 10 ** 9 + 7
c = []

for i in range(60):
    c1 = sum(lst & 1)
    c.append(c1 * (n - c1))
    lst >>= 1
print(sum([v * 2 ** i for i, v in enumerate(c)]) % mod)

Submission status: Runtime Error

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

import numpy as np

MOD = 10 ** 9 + 7

N = int(readline())
A = np.array(read().split())

answer = 0
for n in range(63):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    for _ in range(n):
        x *= 2
        x %= MOD
    answer += x
answer %= MOD
print(answer)

Submission status: Runtime Error

Solution code:
As = list(map(int, input().split()))
r = 0
#for i in range(N):
#  for j in range(i+1, N):
#    r = (r+(As[i]^As[j]))%1000000007
for i in range(64):
  n = 0
  for A in As:
    if A&(1<<i) != 0:
      n += 1
  #print(i, n)
  d = n*(N-n)%1000000007
  d2 = (d<<i)%1000000007
  r = (r+d2)%1000000007
print(r)

Submission status: Runtime Error

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

Solution code:
#include <bits/stdc++.h>

#define int long long int
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define rep(i,l,r) for(int i=l;i<r;i++)
#define bep(i,l,r) for(int i=l;i>=r;i--)
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define el '\n'
#define sz(s) s.size()
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define ll long long
using namespace std;

int inf = 1e18;
const int N = 4e5+5;
int mod = 1e9+7;
/*void dfs(int u,int par,int maxx)
{


    for(int v:adj[u])
    {
        if(v==par)
            continue;
        dfs(v,u,maxx);
    }
}


int ncr(int n , int r ){
	r = min(r,n-r);
	int res = 1 ;
	for(int i = 1 ; i <= r ; i++ ){
		( res *= n-i+1 )%= mod;
		res /= i ;
	}
	return res ;
}
*/
ll powmod(ll a,ll b) {ll res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}
int arr[N];
 int sumXOR(int n)
{
     int sum = 0;
    for (int i = 0; i < 62; i++)
    {

        int k = 1ll<<i;
        int ct = 0;
        for(int i=0;i<n;++i)
        {
            if(arr[i]&k)
                ct++;
        }
        sum = (sum+ (k%mod)*(ct%mod)*((n-ct)%mod))%mod;
    }
    return sum%mod;
}
int32_t main()
{
    io
    int tt=1;
    //cin>>tt;
    while(tt--)
    {
        int n;
        cin>>n;

        rep(i,0,n)
        cin>>arr[i];
        int ans = sumXOR(n);
        cout<<ans%mod<<el;

    }



    return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
L = [0 for i in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0

for i in range(N):
    tmp = format(As[i], 'b').zfill(60)

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[-(i + 1)]
    a = L[i] % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n = input()
l = np.array(list(map(int,input().split())) ,dtype='uint64')

s = 0

for i in range(61):
    z=0
    o=0
    for n in l:
        if (n >> i)%2 == 0:
            z += 1
        else:
            o += 1
    s += (z*o)*(2**i)

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

Submission status: Runtime Error

Solution code:
k=int(input())
l=[int(x) for x in input().rstrip().split()]
a=[]
 
for i in l:
    for j in l:
        if i<j:
            a.append([i,j])
 
A_1=0
A_2=0
SUM=0
ans=""
ANS=[]
for i in xrange(len(a)):
    A_1=format(a[i][0],'b')
    A_2=format(a[i][1],'b')
    if len(A_1)<len(A_2):
        A_1='0'*(len(A_2)-len(A_1))+A_1
    elif len(A_2)<len(A_1):
        A_2='0'*(len(A_1)-len(A_2))+A_2
 
 
    for j in xrange(len(A_1)):
        if A_1[j]==A_2[j]:
            ans=ans+'0'
        else:
            ans=ans+'1'
    ANS.append(ans)
    SUM+=int(ans,2)
    ans=''
SUM=SUM%(10**9+7)
print(SUM)

Submission status: Runtime Error

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

res = 0
for dig in range(61):
    one = 0
    for i in a:
        if i & (1<<dig) != 0:
            one += 1
    res = (res + one*(n-one)*(1<<dig))%MOD
print(res)

Submission status: Runtime Error

Solution code:

mod = 10**9 + 7


def main():
    n = int(input())
    A = [int(a) for a in input().split()]
    ans = 0
    for k in range(60):
        a = 0
        for i in range(n):
            a += A[i] & 1
            A[i] << = 1
        da = (1 << k) % mod
        da *= (n - a)*a
        da %= mod
        ans += da
        ans %= mod
    print(ans)


main()