Even Subarrays (Codeforces 1731C)
Tags: Math, hashing

You are given an integer array $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).Find the number of subarrays of $$$a$$$ whose $$$\operatorname{XOR}$$$ has an even number of divisors. In other words, find all pairs of indices $$$(i, j)$$$ ($$$i \le j$$$) such that $$$a_i \oplus a_{i + 1} \oplus \dots \oplus a_j$$$ has an even number of divisors.For example, numbers $$$2$$$, $$$3$$$, $$$5$$$ or $$$6$$$ have an even number of divisors, while $$$1$$$ and $$$4$$$ — odd. Consider that $$$0$$$ has an odd number of divisors in this task.Here $$$\operatorname{XOR}$$$ (or $$$\oplus$$$) denotes the bitwise XOR operation.Print the number of subarrays but multiplied by 2022... Okay, let's stop. Just print the actual answer.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. 

Output: For each test case, print the number of subarrays, whose $$$\operatorname{XOR}$$$ has an even number of divisors.

Note: In the first test case, there are $$$4$$$ subarrays whose $$$\operatorname{XOR}$$$ has an even number of divisors: $$$[3]$$$, $$$[3,1]$$$, $$$[1,2]$$$, $$$[2]$$$.In the second test case, there are $$$11$$$ subarrays whose $$$\operatorname{XOR}$$$ has an even number of divisors: $$$[4,2]$$$, $$$[4,2,1]$$$, $$$[4,2,1,5]$$$, $$$[2]$$$, $$$[2,1]$$$, $$$[2,1,5]$$$, $$$[2,1,5,3]$$$, $$$[1,5,3]$$$, $$$[5]$$$, $$$[5,3]$$$, $$$[3]$$$.In the third test case, there is no subarray whose $$$\operatorname{XOR}$$$ has an even number of divisors since $$$\operatorname{XOR}$$$ of any subarray is either $$$4$$$ or $$$0$$$.

Sample Inputs:
4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3

Sample Outputs:
4
11
0
20

Solution (Python):
from collections import defaultdict
import io, os, sys
from math import log, floor
outputs = []
for case in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    p = 0
    big = floor(log(n, 2))
    upper = 2 ** (big + 1)
    B = [p * p for p in range(0, floor(upper ** 0.5) + 1)]
    Bset = set(B)
    h = [0 for i in range(upper * 2)]
    total = 0
    count = 0
    xor = 0
    for ai in a:
        if count > 2 * 10 ** 9:
            total += count
            count = 0
        xor ^= ai
        if xor in Bset:
            count += 1
        for bi in B:
            count += h[xor ^ bi]
        h[xor] += 1
    total += count
    total = n * (n + 1) // 2 - total
    outputs.append(str(total))
sys.stdout.write('\n'.join(outputs))

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    (cnt, cur) = (0, 0)
    m = [0] * 2 * n
    m[cur] += 1
    for j in range(n):
        cur ^= a[j]
        i = 0
        while i * i < 2 * n:
            if cur ^ i * i < 2 * n:
                cnt += m[cur ^ i * i]
            i += 1
        m[cur] += 1
    ans = n * (n + 1) // 2
    ans = ans - cnt
    print(ans)

Solution (Python):
from collections import Counter
odc = [0]
x = 1
while x * x < 1 << 18:
    odc.append(x * x)
    x += 1

def main():
    t = int(input())
    allans = []
    cnts = [0] * (1 << 18)
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        cnts[0] = 1
        allpxors = [0]
        ans = 0
        X = 0
        for x in a:
            X ^= x
            allpxors.append(X)
            for sq in odc:
                ans += cnts[X ^ sq]
            cnts[X] += 1
        ans = (n + 1) * n // 2 - ans
        allans.append(ans)
        for X in allpxors:
            cnts[X] = 0
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()