Sum of XOR Functions (Codeforces 1879D)
Tags: Math, divide and conquer

You are given an array $$$a$$$ of length $$$n$$$ consisting of non-negative integers.You have to calculate the value of $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$$$, where $$$f(l, r)$$$ is $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_{r-1} \oplus a_r$$$ (the character $$$\oplus$$$ denotes bitwise XOR).Since the answer can be very large, print it modulo $$$998244353$$$.

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9)$$$.

Output: Print the one integer — the value of $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$$$, taken modulo $$$998244353$$$.

Note: In the first example, the answer is equal to $$$f(1, 1) + 2 \cdot f(1, 2) + 3 \cdot f(1, 3) + f(2, 2) + 2 \cdot f(2, 3) + f(3, 3) = $$$ $$$= 1 + 2 \cdot 2 + 3 \cdot 0 + 3 + 2 \cdot 1 + 2 = 12$$$.

Sample Inputs:
3
1 3 2

4
39 68 31 80

7
313539461 779847196 221612534 488613315 633203958 394620685 761188160

Sample Outputs:
12

1337

257421502

Solution (Python):
""""""
import sys

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

def ii():
    return int(si())

def mi(ss=' '):
    return map(int, si().split(ss))

def msi(ss=' '):
    return map(str, si().split(ss))

def li(ss=' '):
    return list(mi(ss))
sys.setrecursionlimit(10 ** 5)
(MOD, MOD2, INF) = (10 ** 9 + 7, 998244353, float('inf'))
MAX = 10 ** 5 + 1

def xor_sum(bit, n, arr):
    cnt_zero = cnt_one = sum_zero = sum_one = 0
    res = 0
    for i in range(n):
        if arr[i] & bit:
            (cnt_zero, cnt_one) = (cnt_one, cnt_zero)
            (sum_zero, sum_one) = (sum_one, sum_zero)
            cnt_one += 1
        else:
            cnt_zero += 1
        sum_zero += cnt_zero
        sum_one += cnt_one
        res += sum_one
    return bit * res % MOD2

def solve():
    n = ii()
    arr = li()
    ans = 0
    for i in range(32):
        bit = 1 << i
        ans += xor_sum(bit, n, arr)
        ans %= MOD2
    print(ans)
test = 1
for _ in range(test):
    solve()

Solution (Python):
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random
import heapq
MOD = int(1000000000.0) + 7
MOD3 = 998244353

def inp(force_list=False):
    re = list(map(int, input().split()))
    if len(re) == 1 and (not force_list):
        return re[0]
    return re

def inst():
    return input().strip()

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(x, y):
    return x * y / gcd(x, y)

def qmod(a, b, mod=MOD):
    res = 1
    while b:
        if b & 1:
            res = res * a % mod
            b >>= 1
            a = a * a % mod
    return res

def inv(a):
    return qmod(a, MOD - 2)
last = 0
rans = 1000000

def query(x, add):
    re = last
    if add > 0:
        print('+ %d' % x)
        re = (last + x - 1) % rans + 1
    else:
        print('- %d' % x)
        re = (last - x - 1) % rans + 1
    stdout.flush()
    return re
    return inp()
fac = [1]
for i in range(1, 100001):
    fac.append(fac[-1] * i % MOD)

def C(n, k):
    return fac[n] * inv(fac[k] * fac[n - k] % MOD) % MOD

def lstr(da):
    return ' '.join(map(str, da))

def my_main():
    global MOD
    MX = int(10000000000.0)
    kase = 1
    pans = []
    for ikk in range(kase):
        n = inp()
        da = inp(True)
        ans = 0
        for i in range(30):
            cnt = [0, 0]
            sm = [0, 0]
            x = 0
            cur = 0
            for j in range(n):
                sm[x] += j + 1
                cnt[x] += 1
                bit = da[j] >> i & 1
                x ^= bit
                cur += (j + 2) * cnt[x ^ 1] - sm[x ^ 1]
            ans += cur * (1 << i)
            ans %= MOD3
        pans.append(str(ans))
    print('\n'.join(pans))
my_main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

def ri():
    return int(input())

def rs():
    return input()

def rm():
    return map(int, input().split())
mod = 998244353

def main():
    n = ri()
    a = rl()
    res = 0
    for bit in range(30):
        cur_b = 1 << bit
        count = [1, 0]
        sm = [0, 0]
        cur = 0
        for i in range(n):
            if a[i] & cur_b:
                cur ^= 1
            count[cur] += 1
            sm[cur] += i + 1
            cs = count[cur ^ 1] * (i + 1) - sm[cur ^ 1]
            cs %= mod
            res += cs * cur_b
            res %= mod
    print(res)
main()