Apollo versus Pan (Codeforces 1466E)
Tags: Math, bitmasks

Only a few know that Pan and Apollo weren't only battling for the title of the GOAT musician. A few millenniums later, they also challenged each other in math (or rather in fast calculations). The task they got to solve is the following:Let $$$x_1, x_2, \ldots, x_n$$$ be the sequence of $$$n$$$ non-negative integers. Find this value: $$$$$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k)$$$$$$Here $$$\&$$$ denotes the bitwise and, and $$$|$$$ denotes the bitwise or.Pan and Apollo could solve this in a few seconds. Can you do it too? For convenience, find the answer modulo $$$10^9 + 7$$$.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1\,000$$$) denoting the number of test cases, then $$$t$$$ test cases follow.The first line of each test case consists of a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$), the length of the sequence. The second one contains $$$n$$$ non-negative integers $$$x_1, x_2, \ldots, x_n$$$ ($$$0 \leq x_i < 2^{60}$$$), elements of the sequence.The sum of $$$n$$$ over all test cases will not exceed $$$5 \cdot 10^5$$$.

Output: Print $$$t$$$ lines. The $$$i$$$-th line should contain the answer to the $$$i$$$-th text case.


Sample Inputs:
8
2
1 7
3
1 2 4
4
5 5 5 5
5
6 2 2 1 0
1
0
1
1
6
1 12 123 1234 12345 123456
5
536870912 536870911 1152921504606846975 1152921504606846974 1152921504606846973

Sample Outputs:
128
91
1600
505
0
1
502811676
264880351

Solution (Python):
import io
import os
import __pypy__
int_add = __pypy__.intop.int_add
int_sub = __pypy__.intop.int_sub
int_mul = __pypy__.intop.int_mul

def make_mod_mul(mod=10 ** 9 + 7):
    fmod_inv = 1.0 / mod

    def mod_mul(a, b, c=0):
        res = int_sub(int_add(int_mul(a, b), c), int_mul(mod, int(fmod_inv * a * b + fmod_inv * c)))
        if res >= mod:
            return res - mod
        elif res < 0:
            return res + mod
        else:
            return res
    return mod_mul
mod_mul = make_mod_mul()
MOD = 10 ** 9 + 7
NUM_BITS = 60
HALF_NUM_BITS = NUM_BITS // 2
HALF_MASK = (1 << HALF_NUM_BITS) - 1
dp1 = [0] * NUM_BITS
dp2 = [0] * NUM_BITS

def solve(N, front, back):
    modMask = 1
    mask = 1
    for pos in range(HALF_NUM_BITS):
        count = 0
        for x in back:
            if x & mask:
                count += 1
        dp1[pos] = mod_mul(count, modMask)
        dp2[pos] = mod_mul(N, modMask)
        modMask = mod_mul(modMask, 2)
        mask *= 2
    mask = 1
    for pos in range(HALF_NUM_BITS, NUM_BITS):
        count = 0
        for x in front:
            if x & mask:
                count += 1
        dp1[pos] = mod_mul(count, modMask)
        dp2[pos] = mod_mul(N, modMask)
        modMask = mod_mul(modMask, 2)
        mask *= 2
    ans = 0
    for (f, b) in zip(front, back):
        total1 = 0
        total2 = 0
        mask = 1
        for pos in range(HALF_NUM_BITS):
            if b & mask:
                total1 = (total1 + dp1[pos]) % MOD
                total2 = (total2 + dp2[pos]) % MOD
            else:
                total2 = (total2 + dp1[pos]) % MOD
            mask *= 2
        mask = 1
        for pos in range(HALF_NUM_BITS, NUM_BITS):
            if f & mask:
                total1 = (total1 + dp1[pos]) % MOD
                total2 = (total2 + dp2[pos]) % MOD
            else:
                total2 = (total2 + dp1[pos]) % MOD
            mask *= 2
        ans = mod_mul(total1, total2, ans)
    return ans
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    TC = int(input())
    for tc in range(1, TC + 1):
        N = int(input())
        front = []
        back = []
        for x in input().split():
            x = int(x)
            f = int(float(x >> HALF_NUM_BITS))
            b = int(float(x & HALF_MASK))
            front.append(f)
            back.append(b)
        ans = solve(N, front, back)
        print(ans)

Solution (Python):
import io, os, __pypy__
int_add = __pypy__.intop.int_add
int_sub = __pypy__.intop.int_sub
int_mul = __pypy__.intop.int_mul

def make_mod_mul(mod=10 ** 9 + 7):
    fmod_inv = 1.0 / mod

    def mod_mul(a, b, c=0):
        res = int_sub(int_add(int_mul(a, b), c), int_mul(mod, int(fmod_inv * a * b + fmod_inv * c)))
        if res >= mod:
            return res - mod
        elif res < 0:
            return res + mod
        else:
            return res
    return mod_mul
mod_mul = make_mod_mul()
MOD = 10 ** 9 + 7
NUM_BITS = 60
HALF_NUM_BITS = NUM_BITS // 2
HALF_MASK = (1 << HALF_NUM_BITS) - 1
dp1 = [0] * NUM_BITS
dp2 = [0] * NUM_BITS

def solve(N, front, back):
    modMask = 1
    mask = 1
    for pos in range(HALF_NUM_BITS):
        count = sum((1 for x in back if x & mask))
        dp1[pos] = mod_mul(count, modMask)
        dp2[pos] = mod_mul(N, modMask)
        modMask = mod_mul(modMask, 2)
        mask *= 2
    mask = 1
    ans = 0
    for pos in range(HALF_NUM_BITS, NUM_BITS):
        count = sum((1 for x in front if x & mask))
        dp1[pos] = mod_mul(count, modMask)
        dp2[pos] = mod_mul(N, modMask)
        modMask = mod_mul(modMask, 2)
        mask *= 2
    for (f, b) in zip(front, back):
        total1 = 0
        total2 = 0
        mask = 1
        for pos in range(HALF_NUM_BITS):
            if b & mask:
                total1 = (total1 + dp1[pos]) % MOD
                total2 = (total2 + dp2[pos]) % MOD
            else:
                total2 = (total2 + dp1[pos]) % MOD
            mask *= 2
        mask = 1
        for pos in range(HALF_NUM_BITS, NUM_BITS):
            if f & mask:
                total1 = (total1 + dp1[pos]) % MOD
                total2 = (total2 + dp2[pos]) % MOD
            else:
                total2 = (total2 + dp1[pos]) % MOD
            mask *= 2
        ans = mod_mul(total1, total2, ans)
    return ans
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    for tc in range(int(input())):
        N = int(input())
        front = []
        back = []
        for x in input().split():
            x = int(x)
            f = int(float(x >> HALF_NUM_BITS))
            b = int(float(x & HALF_MASK))
            front.append(f)
            back.append(b)
        print(solve(N, front, back))

Solution (Python):
import io, os, __pypy__
int_add = __pypy__.intop.int_add
int_sub = __pypy__.intop.int_sub
int_mul = __pypy__.intop.int_mul

def make_mod_mul(mod=10 ** 9 + 7):
    fmod_inv = 1.0 / mod

    def mod_mul(a, b, c=0):
        res = int_sub(int_add(int_mul(a, b), c), int_mul(mod, int(fmod_inv * a * b + fmod_inv * c)))
        if res >= mod:
            return res - mod
        elif res < 0:
            return res + mod
        else:
            return res
    return mod_mul
mod_mul = make_mod_mul()
MOD = 10 ** 9 + 7
NUM_BITS = 60
HALF_NUM_BITS = NUM_BITS // 2
HALF_MASK = (1 << HALF_NUM_BITS) - 1
dp1 = [0] * NUM_BITS
dp2 = [0] * NUM_BITS

def solve(N, front, back):
    modMask = 1
    mask = 1
    for pos in range(HALF_NUM_BITS):
        count = sum((1 for x in back if x & mask))
        dp1[pos] = mod_mul(count, modMask)
        dp2[pos] = mod_mul(N, modMask)
        modMask = mod_mul(modMask, 2)
        mask *= 2
    mask = 1
    for pos in range(HALF_NUM_BITS, NUM_BITS):
        count = sum((1 for x in front if x & mask))
        dp1[pos] = mod_mul(count, modMask)
        dp2[pos] = mod_mul(N, modMask)
        modMask = mod_mul(modMask, 2)
        mask *= 2
    ans = 0
    for (f, b) in zip(front, back):
        total1 = 0
        total2 = 0
        mask = 1
        for pos in range(HALF_NUM_BITS):
            if b & mask:
                total1 = (total1 + dp1[pos]) % MOD
                total2 = (total2 + dp2[pos]) % MOD
            else:
                total2 = (total2 + dp1[pos]) % MOD
            mask *= 2
        mask = 1
        for pos in range(HALF_NUM_BITS, NUM_BITS):
            if f & mask:
                total1 = (total1 + dp1[pos]) % MOD
                total2 = (total2 + dp2[pos]) % MOD
            else:
                total2 = (total2 + dp1[pos]) % MOD
            mask *= 2
        ans = mod_mul(total1, total2, ans)
    return ans
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    for tc in range(int(input())):
        N = int(input())
        front = []
        back = []
        for x in input().split():
            x = int(x)
            f = int(float(x >> HALF_NUM_BITS))
            b = int(float(x & HALF_MASK))
            front.append(f)
            back.append(b)
        print(solve(N, front, back))