Problem:


Score : 800 points

Problem Statement

The beauty of a sequence a of length n is defined as a_1 \oplus \cdots \oplus a_n, where \oplus denotes the bitwise exclusive or (XOR).

You are given a sequence A of length N.
Snuke will insert zero or more partitions in A to divide it into some number of non-empty contiguous subsequences.

There are 2^{N-1} possible ways to insert partitions.
How many of them divide A into sequences whose beauties are all equal? Find this count modulo 10^{9}+7.

Constraints

All values in input are integers.

1 \leq N \leq 5 \times 10^5

0 \leq A_i < 2^{20}

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_{N}

Output

Print the answer.

Sample Input 1

3
1 2 3

Sample Output 1

3

Four ways of dividing A shown below satisfy the condition. The condition is not satisfied only if A is divided into (1),(2),(3).

(1,2,3)

(1),(2,3)

(1,2),(3)

Sample Input 2

3
1 2 2

Sample Output 2

1

Sample Input 3

32
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 3

147483634

Find the count modulo 10^{9}+7.

Sample Input 4

24
1 2 5 3 3 6 1 1 8 8 0 3 3 4 6 6 4 0 7 2 5 4 6 2

Sample Output 4

292



Sample input:
3
1 2 3


Sample output:
3

Submission status: Wrong Answer

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

bins = [0] * 20

zeros = 0
v_dict = dict()
v_dict[0] = dict()
v_all_dict = dict()

for i in range(N):
    a = a_list[i]
    b = 0
    for k in range(20):
        r = (a // (2**k)) % 2
        bins[k] = (bins[k] + r) % 2
        b += bins[k]*(2**k)
    if b in v_dict[zeros].keys():
        v_dict[zeros][b] += 1
    else:
        v_dict[zeros][b] = 1

    if b == 0:
        for v in v_dict[zeros].keys():
            if v not in v_all_dict.keys():
                v_all_dict[v] = [zeros, v_dict[zeros][v] % LARGE, 1]
            else:
                z, c1, c2 = v_all_dict[v]
                v_all_dict[v][1] = (v_all_dict[v][1] + v_all_dict[v][1] * (zeros - z) * v_dict[zeros][v] + v_all_dict[v][2] * v_dict[zeros][v]) % LARGE
        zeros += 1
        v_dict[zeros] = dict()


# print(zeros)
# print(v_all_dict)

if b == 0:
    res = 0
    for v in v_all_dict.keys():
        if v != 0:
            res = (res + v_all_dict[v][1]) % LARGE
        else:
            res = (res + 2 ** (zeros - 1) - 1) % LARGE
    res += 1
else:
    if b in v_all_dict.keys():
        z, c1, c2 = v_all_dict[b]
        res = (v_all_dict[b][1] + v_all_dict[b][1] * (zeros - z) + v_all_dict[v][2]) % LARGE
    else:
        res = 1
print(res)

Submission status: Wrong Answer

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

bins = [0] * 20

zeros = 0
v_dict = dict()
v_dict[0] = dict()
v_all_dict = dict()

for i in range(N):
    a = a_list[i]
    b = 0
    for k in range(20):
        r = (a // (2**k)) % 2
        bins[k] = (bins[k] + r) % 2
        b += bins[k]*(2**k)
    if b in v_dict[zeros].keys():
        v_dict[zeros][b] += 1
    else:
        v_dict[zeros][b] = 1

    if b == 0:
        for v in v_dict[zeros].keys():
            if v not in v_all_dict.keys():
                v_all_dict[v] = [zeros, v_dict[zeros][v] % LARGE, 1]
            else:
                z, c1, c2 = v_all_dict[v]
                v_all_dict[v][1] = (v_all_dict[v][1] + v_all_dict[v][1] * (zeros - z) * v_dict[zeros][v] + v_all_dict[v][2] * v_dict[zeros][v]) % LARGE
        zeros += 1
        v_dict[zeros] = dict()


# print(zeros)
# print(v_all_dict)

if b == 0:
    res = 0
    for v in v_all_dict.keys():
        if v != 0:
            res = (res + v_all_dict[v][1]) % LARGE
        else:
            res = (res + 2 ** (zeros - 1) - 1) % LARGE
    res += 1
else:
    if b in v_all_dict.keys():
        z, c1, c2 = v_all_dict[b]
        res = (v_all_dict[b][2] + v_all_dict[b][1] * (zeros - z)) % LARGE
    else:
        res = 1
print(res)

Submission status: Wrong Answer

Solution code:
import sys

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

C_sum = [0]
s = {0}

for a in A:
    C_sum.append(C_sum[-1]^a)
    s.add(C_sum[-1])

print(C_sum,file=sys.stderr)
print(s,file=sys.stderr)

if C_sum[-1] != 0:
    print(1)
else:
    dic_state = {}
    dic = {}
    for x in s:
        dic_state[x] = 0
        dic[x] = [0]
    for c in C_sum:
        if c==0:
            for d in dic:
                if dic_state[d] == 0:
                    dic[d][-1] += 1
                else:
                    dic[d].append(1)
                    dic_state[d] = 0
        else:
            if dic_state[c] == c:
                dic[c][-1] += 1
            else:
                dic[c].append(1)
                dic_state[c] = c

    print(dic,file=sys.stderr)

    ans = pow(2,dic[0][0]-2,10**9+7)

    for d in dic:
        tmp_0 = 1
        tmp_x = 0

        for i in range(1,len(dic[d])):
            if i%2==1:
                tmp_x += tmp_0 * dic[d][i]
                tmp_x %= 10**9+7
            else:
                tmp_0 += tmp_x * dic[d][i]
                tmp_0 %= 10**9+7

        print(d,file=sys.stderr)
        print(dic[d],file=sys.stderr)
        print(tmp_x,file=sys.stderr)

        ans += tmp_x
        ans %= 10**9+7

    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import accumulate
from operator import xor


def solve_0(acc):
    MOD = 10 ** 9 + 7
    cnt_0 = 0
    counts = defaultdict(list)
    for a in acc:
        if a == 0:
            for i, cnt in counts.items():
                if len(cnt) % 2 == 0:
                    cnt[-1] += 1
                else:
                    cnt.append(1)
            cnt_0 += 1
        else:
            cnt = counts[a]
            if len(cnt) % 2 == 0:
                cnt.append(1)
            else:
                cnt[-1] += 1
    ans = pow(2, cnt_0 - 1, MOD)
    for i, cnt in counts.items():
        c1 = cnt[0]
        ans += c1
        loc = {c1: 0}
        if len(cnt) > 2:
            for c0, c1 in zip(cnt[1::2], cnt[2:-1:2]):
                tmp = c1
                for i1, i0 in loc.items():
                    tmp += i1 * (i0 + c0) * c1
                    loc[i1] += c0
                loc[tmp] = 0
                ans = (ans + tmp) % MOD
                # print(ans, c0, c1, loc, tmp)
        ans %= MOD
    return ans


def solve_1(acc):
    MOD = 10 ** 9 + 7
    common = acc[-1]
    step = 1
    cnt = 0
    ans = 0
    for a in acc:
        if a == common:
            cnt = (cnt + step) % MOD
        elif a == 0:
            step = (step + cnt) % MOD
            ans = cnt
    return ans + 1


n = int(input())
aaa = list(map(int, input().split()))
acc = [0] * n
t = 0
for i in range(n):
    t = acc[i] = t ^ aaa[i]
# acc = list(accumulate(aaa, func=xor))
# print(acc)
if acc[-1] == 0:
    print(solve_0(acc))
else:
    print(solve_1(acc))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import accumulate
from operator import xor


def solve_0(acc):
    MOD = 10 ** 9 + 7
    cnt_0 = 0
    counts = defaultdict(list)
    for a in acc:
        if a == 0:
            for i, cnt in counts.items():
                if len(cnt) % 2 == 0:
                    cnt[-1] += 1
                else:
                    cnt.append(1)
            cnt_0 += 1
        else:
            cnt = counts[a]
            if len(cnt) % 2 == 0:
                cnt.append(1)
            else:
                cnt[-1] += 1
    ans = pow(2, cnt_0 - 1, MOD)
    for i, cnt in counts.items():
        c1 = cnt[0]
        ans += c1
        loc = {c1: 0}
        if len(cnt) > 2:
            for c0, c1 in zip(cnt[1::2], cnt[2:-1:2]):
                tmp = c1
                for i1, i0 in loc.items():
                    tmp += i1 * (i0 + c0) * c1
                    loc[i1] += c0
                loc[tmp] = 0
                ans = (ans + tmp) % MOD
                # print(ans, c0, c1, loc, tmp)
        ans %= MOD
    return ans


def solve_1(acc):
    MOD = 10 ** 9 + 7
    common = acc[-1]
    step = 1
    cnt = 0
    ans = 0
    for a in acc:
        if a == common:
            cnt = (cnt + step) % MOD
        elif a == 0:
            step = (step + cnt) % MOD
            ans = cnt
    return ans + 1


n = int(input())
aaa = list(map(int, input().split()))
acc = list(accumulate(aaa, func=xor))
# print(acc)
if acc[-1] == 0:
    print(solve_0(acc))
else:
    print(solve_1(acc))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

cx = [0]
for a in A:
    cx.append(cx[-1]^a)

if cx[-1]:
    print(1)
    exit()

ctr = Counter(cx)
ans = pow(2,ctr[0]-2,MOD)

for k,v in ctr.items():
    if k==0: continue
    ans += v*4-3
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

N = int(input())
a = list(map(int, input().split()))
ma = max(a)

cum_xor = [0] * (N + 1)
for i, aa in enumerate(a):
    cum_xor[i + 1] = cum_xor[i] ^ aa
# print(cum_xor)

d = [[] for _ in range(ma + 1)]

for i in range(0, ma + 1):
    tar = i
    cnt = 0
    for j in range(1, N + 1):
        if cum_xor[j] == tar:
            if cnt > 0:
                d[i].append(cnt)
                cnt = 0
            d[i].append(0)
            tar ^= i
        elif cum_xor[j] == (tar ^ i):
            cnt += 1
if cnt > 0:
    d[i].append(cnt)
    cnt = 0


def rec(cur):
    if cur < 0: return 0
    if cur == 0:
        return 1
    mul = 1
    # print(kkk, cur)
    if d[kkk][cur] > 0:
        mul = (d[kkk][cur] + 1)
        
    if mm[cur]:
        return mm[cur]
    res = 0
    for i in range(cur - 1, -1, -2):
        res += mul * rec(i)
        mul = 1
    return res


ans = 0
if d[0].count(0) == 0:
    pass
elif d[0].count(0) == 1:
    ans += 1
else:
    ans += 1 << (d[0].count(0) - 1)
for kkk in range(1, ma + 1):
    lg_di = len(d[kkk])
    mm = [None] * (N + 1)
    ans += rec(lg_di - 1)
    ans %= MOD
    # print(d[i])
print(ans)

Submission status: Wrong Answer

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

allxor = 0
tmpxor = 0
idx = [ ]
value = { }
for i in range(N):
    allxor ^= a[i]
    tmpxor ^= a[i]
    if not tmpxor in value:
        value[tmpxor] = 1
    else:
        value[tmpxor] += 2

    if tmpxor == 0:
        idx.append(i)

if allxor != 0:
    cnt = 0
    tmpxor = 0
    for i in range(N):
        tmpxor ^= a[i]
        if tmpxor == allxor:
            cnt += 1
            tmpxor = 0
    
    print(pow(2,cnt,mod))
    exit(0)

l = len(idx)
ans = pow(2, l-1, mod)

for key,value in value.items():
    if key == 0:
        continue
    if value == 1:
        ans += 1
    else:
        ans += (value%3) * ( pow(2, value//3) - 1) + 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
max_A = format(max(A),'b')
len_A = len(max_A)
for i in range(N):
	A[i] = format(A[i],'b')
	A[i] = list((len_A - len(A[i])) * "0" + A[i])

def X_or(a,b):
	c = []
	for i in range(len(a)):
		if a[i] == b[i]:
			c.append("0")
		else:
			c.append("1")
	return c

sum = 0
for i in range(N):
	temp_ans = A[0]
	if i == 0:
		pass
	else:
		for j in range(i):
			temp_ans = X_or(A[j+1],temp_ans)
	k = i + 1
	count = 0
	judge_row = ["0"] * len_A
	while k < N:
		judge_row = X_or(judge_row,A[k])
		if judge_row == temp_ans:
			count += 1
			judge_row = temp_ans
		k += 1
	if count > 0:
		if judge_row == ["0"] * len_A:
			sum += 2 ** (count - 1)
	
print((sum+1) % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]

M = 10**9+7

xa = []
x = 0
for a in A:
    x ^= a
    xa.append(x)

xa.append(x)

#print(A)
#print(xa)

from collections import defaultdict

cs = defaultdict(int)

result = 0

for i in range(1, N):
    cs[xa[i - 1]] += 1
    k = xa[N - 1] ^ xa[i - 1]
    # print(i, cs, k)
    if k in cs:
        x = 2 ** (cs[k] - 1)
        result += x

print(result % M + 1)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

N = int(input())
a = list(map(int, input().split()))
ma = max(a)

cum_xor = [0] * (N + 1)
for i, aa in enumerate(a):
    cum_xor[i + 1] = cum_xor[i] ^ aa
# print(cum_xor)

d = [[] for _ in range(ma + 1)]

for i in range(0, ma + 1):
    tar = i
    cnt = 0
    for j in range(1, N + 1):
        if cum_xor[j] == tar:
            if cnt > 0:
                d[i].append(cnt)
                cnt = 0
            d[i].append(0)
            tar ^= i
        elif cum_xor[j] == (tar ^ i):
            cnt += 1
if cnt > 0:
    d[i].append(cnt)
    cnt = 0


def rec(cur):
    if cur < 0: return 0
    if cur == 0:
        return 1
    mul = 1
    # print(kkk, cur)
    if d[kkk][cur] > 0:
        mul = (d[kkk][cur] + 1)
        mul = 1
    if mm[cur]:
        return mm[cur]
    res = 0
    for i in range(cur - 1, -1, -2):
        res += mul * rec(i)
    return res


ans = 0
if d[0].count(0) == 0:
    pass
elif d[0].count(0) == 1:
    ans += 1
else:
    ans += 1 << (d[0].count(0) - 1)
for kkk in range(1, ma + 1):
    lg_di = len(d[kkk])
    mm = [None] * (N + 1)
    ans += rec(lg_di - 1)
    ans %= MOD
    # print(d[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
max_A = format(max(A),'b')
len_A = len(max_A)
for i in range(N):
	A[i] = format(A[i],'b')
	A[i] = list((len_A - len(A[i])) * "0" + A[i])

def X_or(a,b):
	c = []
	for i in range(len(a)):
		if a[i] == b[i]:
			c.append("0")
		else:
			c.append("1")
	return c

sum = 0
for i in range(N):
	temp_ans = A[0]
	if i == 0:
		pass
	else:
		for j in range(i):
			temp_ans = X_or(A[j+1],temp_ans)
	k = i + 1
	count = 0
	judge_row = ["0"] * len_A
	while k < N:
		judge_row = X_or(judge_row,A[k])
		if judge_row == temp_ans:
			count += 1
			judge_row = ["0"] * len_A
		k += 1
	if count > 0:
		if judge_row == ["0"] * len_A:
			sum += 2 ** (count - 1)
	
print((sum+1) % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from math import sqrt
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N = int(input())
A = inpl()
S = []
x = 0
for i in range(N):
    x ^= A[i]
    S.append(x)
if S[-1] != 0:
    sr = S[-1]
    a, b = 0, 0
    for s in S:
        if s == sr:
            b =  (b + a + 1)%MOD
        elif s == 0:
            a = (a + b)%MOD
    print(b)
else:
    pass

Submission status: Wrong Answer

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

from collections import defaultdict

x = 0
dict = defaultdict(int)
cnt = defaultdict(int)

for a in A:
    x ^= a
    if x == 0:
        dict[x] += 1
    else:
        dict[x] += 1
        if cnt[x] == 0:
            cnt[x] = 1
        else:
            cnt[x] *= max(1, dict[0] - cnt[x])

ans = 2 ** (dict[0] - 1) + sum(dict.values()) + sum(cnt.values()) - n

mod = 10 ** 9 + 7

print(ans % mod)

Submission status: Wrong Answer

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

from collections import defaultdict

x = 0
dict = defaultdict(int)
cnt = defaultdict(int)

for a in A:
    x ^= a
    if x == 0:
        dict[x] += 1
    else:
        dict[x] += 1
        if cnt[x] == 0:
            cnt[x] = 1
        else:
            cnt[x] *= max(1, dict[0] - cnt[x])

print(2 ** (dict[0] - 1) + sum(dict.values()) + sum(cnt.values()) - n)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
s = a[0]
xor = [s]
MOD = 10**9+7
id0 = []
for i in range(1,N):
    s = s^a[i]
    xor.append(s)
    if s == 0:
        id0.append(i)

if s != 0:
    print(1)
else:
    ans = 2**(len(id0)-1)
    ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import Counter

def main():
    N = II()
    A = LI()
    acc = []
    tmp = 0
    for a in A:
        tmp = tmp ^ a
        acc.append(tmp)
    cnts = []
    cnt0 = Counter()
    for x in acc:
        cnt0[x] += 1
        if x == 0:
            cnts.append(cnt0)
            cnt0 = Counter()
    se = set([x]) if x != 0 else set(acc)
    ans = 0
    for k in se:
        if k == 0:
            ans = (ans + (2 ** (len(cnts) - 1))) % MOD
            continue
        tmp = 1
        for cnt in cnts:
            tmp = (tmp * (cnt[k] + 1)) % MOD
        ans = (ans + tmp) % MOD
    ans = (ans - len(se) + 1) % MOD
    return ans

print(main())

Submission status: Wrong Answer

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

allxor=0
for i in range(0,N):
    allxor=allxor ^ i
answer=0
ruiseki=0
for i in range(0,N):
    ruiseki=ruiseki ^ i
    if ruiseki==0:
        ruiseki2=0
        if i==N-1:
            answer+=N-1
        else:
            for j in range(0,i+1):
                ruiseki2=ruiseki2 ^ j
                if ruiseki2==ruiseki ^ allxor:
                    answer+=1

print(int(answer/(10**9+7)))

Submission status: Wrong Answer

Solution code:
print("むずっ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import accumulate
from operator import xor


def solve_0(acc):
    MOD = 10 ** 9 + 7
    cnt_0 = 0
    tmp_dp = defaultdict(lambda: 0)
    fix_dp = defaultdict(lambda: 0)
    last_0 = defaultdict(lambda: 0)
    steps = defaultdict(lambda: 1)
    for a in acc:
        if a == 0:
            for i, c in tmp_dp.items():
                if i in last_0:
                    fix_dp[i] = (fix_dp[i] + (c - 1) * (cnt_0 - last_0[i]) + 1) % MOD
                else:
                    fix_dp[i] = (fix_dp[i] + c) % MOD
                steps[i] = (steps[i] + fix_dp[i]) % MOD
                last_0[i] = cnt_0
            tmp_dp.clear()
            cnt_0 += 1
        else:
            tmp_dp[a] = (tmp_dp[a] + steps[a]) % MOD
        # print(f'a:{a}  tmp:{dict(tmp_dp)}  fix:{dict(fix_dp)}  step:{dict(steps)}')
    # print(f'tmp:{dict(tmp_dp)}  fix:{dict(fix_dp)}  step:{dict(steps)}')
    ans = sum(fix_dp.values()) % MOD
    ans = (ans + pow(2, cnt_0 - 1, MOD)) % MOD
    return ans


def solve_1(acc):
    MOD = 10 ** 9 + 7
    common = acc[-1]
    step = 1
    cnt = 0
    ans = 0
    for a in acc:
        if a == common:
            cnt = (cnt + step) % MOD
        elif a == 0:
            step = (step + cnt) % MOD
            ans = cnt
    return ans + 1


n = int(input())
aaa = list(map(int, input().split()))
acc = list(accumulate(aaa, func=xor))
# print(acc)
if acc[-1] == 0:
    print(solve_0(acc))
else:
    print(solve_1(acc))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
range = xrange
input = raw_input

MOD = 10**9 + 7

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

zeros = []
val = 0
arr = []
for a in A:
    val ^= a
    arr.append(val)
    if val == 0:
        arr.pop()
        zeros.append(arr)
        arr = []

big = 2**21

end = arr
if end:
    goal = end[-1]
    val = 0
    count = 0
    for a in A:
        val ^= a
        if val == goal:
            count += 1
            val = 0
    fib = [1]*big
    for i in range(2,big):
        fib[i] = (3*fib[i-1] - fib[i-2])%MOD
    print fib[(count-1)//2 + 1]
    sys.exit()


ways = [1]*big
ways[0] = (MOD+1)//2
for arr in zeros:
    for a,count in Counter(arr).items():
        ways[a] = ways[a]*(count + 1)%MOD
    ways[0] = ways[0]*2%MOD

for a in range(1,big):
    ways[a] -= 1

print sum(ways)%MOD

Submission status: Wrong Answer

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

n = int(input())
a = tuple(map(int,input().split()))
mod = 10**9+7

res = 0

base = 0
for i in range(n):
    base ^= a[i]

judge = False
for i in range(21):
    if base&(1<<i):
        judge = True
if judge:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

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

#数列Aを偶数もしくは奇数で分割する場合の数
def XOR_partition(A, mod):
    l = len(A)
    count = 0

    if l == 1 and A[0] % 2 == mod:
        return 1
    elif l == 1 and A[0] % 2 != mod:
        return 0
    else:
        for i in range(l-1):
            if sum(A[0:i+1]) % 2 == mod:
                count += XOR_partition(A[i+1:], mod)
        if sum(A) % 2 == mod:
            count += 1
        return count

even = XOR_partition(A, 0) % num
odd = XOR_partition(A, 1) % num
print((even + odd) % num)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
range = xrange
input = raw_input

MOD = 10**9 + 7

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

zeros = []
val = 0
arr = []
for a in A:
    val ^= a
    arr.append(val)
    if val == 0:
        arr.pop()
        zeros.append(arr)
        arr = []

if arr:
    print 1
    sys.exit()

big = 2**21
ways = [1]*big
ways[0] = (MOD+1)//2
for arr in zeros:
    for a,count in Counter(arr).items():
        ways[a] = ways[a]*(count + 1)%MOD
    ways[0] = ways[0]*2%MOD

for a in range(1,big):
    ways[a] -= 1

print sum(ways)%MOD

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
ais = map(int, raw_input().split())
cumul = 0
p = []
for ai in ais:

	cumul ^= ai
	p.append(cumul)

sp= set(p)
ans = 0
mod = (10 ** 9) +7

def f(ais, p , v):
	dp = {-1: 1}
	for i in range(len(ais)):
		dp[i] = 0
	for j in range(len(ais)):
		for i in range(j+1):
			if p[j] ^ (p[i-1] if i-1>=0 else 0) == v:
				#if reduce(lambda x,y:x^y,ais[i:j+1]) == v:
				dp[j] += dp[i-1]
	return dp[len(ais)-1]


for v in sp:
	ans += f(ais, p, v) % mod

print ans

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=10**9+7
    n=II()
    aa=LI()
    cs=[0]
    for a in aa:cs.append(cs[-1]^a)
    #print(cs)
    cnt=np.zeros((2,max(cs)+1),dtype="i8")
    cnt[0]=1
    for s in cs[1:]:
        if s==0:
            cnt[0]+=cnt[1]
        else:
            cnt[1][s]+=cnt[0][s]
    #print(cnt)
    if cs[-1]==0:print(np.sum(cnt[1])+pow(2,cs.count(0)-2,md))
    else:print(cnt[0][cs[-1]])

main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B=[A[0]]
mod=10**9+7
for i in range(1,N):
  B.append(B[-1]^A[i])
#print(B)
if B[-1]:
  table=[]
  for i in range(N):
    if B[i]==B[-1]:
      if table:
        if table[-1][0]==1:
          table[-1]=(1,table[-1][1]+1)
        else:
          table.append((1,1))
      else:
        table.append((1,1))
    elif B[i]==0:
      if table:
        if table[-1][0]==0:
          table[-1]=(0,table[-1][1]+1)
        else:
          table.append((0,1))
      else:
        table.append((0,1))
  l=len(table)
  dp=[[0]*2 for i in range(l+1)]
  dp[0][0]=1
  for i in range(l):
    if table[i][0]==1:
      dp[i+1][0]=dp[i][0]
      dp[i+1][1]=(dp[i][1]+dp[i][0]*table[i][1])%mod
    else:
      dp[i+1][1]=dp[i][1]
      dp[i+1][0]=(dp[i][0]+dp[i][1]*table[i][1])%mod
  #print(dp)
  #print(table)
  print(dp[l-1][0]) 
else:
  table=[[] for i in range(2**20)]
  List=[]
  used=[False]*(2**20)
  ans=5*(10**8)+4
  for i in range(N):
    if B[i]!=0:
      if not used[B[i]]:
        List.append(B[i])
        used[B[i]]=True
      if table[B[i]]:
        if table[B[i]][-1][0]==1:
          table[B[i]][-1]=(1,table[B[i]][-1][1]+1)
        else:
          table[B[i]].append((1,1))
      else:
        table[B[i]].append((1,1))
    elif B[i]==0:
      ans=(ans*2)%mod
      for k in List:
        if table[k]:
          if table[k][-1][0]==0:
            table[k][-1]=(0,table[k][-1][1]+1)
          else:
            table[k].append((0,1))
        else:
          table[k].append((0,1))
  for k in List:
    l=len(table[k])
    dp=[[0]*2 for i in range(l+1)]
    dp[0][0]=1
    for i in range(l):
      if table[k][i][0]==1:
        dp[i+1][0]=dp[i][0]
        dp[i+1][1]=(dp[i][1]+dp[i][0]*table[k][i][1])%mod
      else:
        dp[i+1][1]=dp[i][1]
        dp[i+1][0]=(dp[i][0]+dp[i][1]*table[k][i][1])%mod
    ans=(ans+dp[l-1][1])%mod
  #print(table)
  print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B=[A[0]]
mod=10**9+7
for i in range(1,N):
  B.append(B[-1]^A[i])
#print(B)
if B[-1]:
  table=[]
  for i in range(N):
    if B[i]==B[-1]:
      if table:
        if table[-1][0]==1:
          table[-1]=(1,table[-1][1]+1)
        else:
          table.append((1,1))
      else:
        table.append((1,1))
    elif B[i]==0:
      if table:
        if table[-1][0]==0:
          table[-1]=(0,table[-1][1]+1)
        else:
          table.append((0,1))
      else:
        table.append((0,1))
  l=len(table)
  dp=[[0]*2 for i in range(l+1)]
  dp[0][0]=1
  for i in range(l):
    if table[i][0]==1:
      dp[i+1][0]=dp[i][0]
      dp[i+1][1]=(dp[i][1]+dp[i][0]*table[i][1])%mod
    else:
      dp[i+1][1]=dp[i][1]
      dp[i+1][0]=(dp[i][0]+dp[i][1]*table[i][1])%mod
  #print(dp)
  #print(table)
  print(dp[l-1][0]) 
else:
  table=[[] for i in range(2**20)]
  s=set()
  ans=5*(10**8)+4
  for i in range(N):
    if B[i]!=0:
      s.add(B[i])
      if table[B[i]]:
        if table[B[i]][-1][0]==1:
          table[B[i]][-1]=(1,table[B[i]][-1][1]+1)
        else:
          table[B[i]].append((1,1))
      else:
        table[B[i]].append((1,1))
    elif B[i]==0:
      ans=(ans*2)%mod
      for k in s:
        if table[k]:
          if table[k][-1][0]==0:
            table[k][-1]=(0,table[k][-1][1]+1)
          else:
            table[k].append((0,1))
        else:
          table[k].append((0,1))
  for k in s:
    l=len(table[k])
    dp=[[0]*2 for i in range(l+1)]
    dp[0][0]=1
    for i in range(l):
      if table[k][i][0]==1:
        dp[i+1][0]=dp[i][0]
        dp[i+1][1]=(dp[i][1]+dp[i][0]*table[k][i][1])%mod
      else:
        dp[i+1][1]=dp[i][1]
        dp[i+1][0]=(dp[i][0]+dp[i][1]*table[k][i][1])%mod
    ans=(ans+dp[l-1][1])%mod
  #print(table)
  print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
MAX = 10**9 + 7

def solve():
    N = int(raw_input())
    arr = [int(_) for _ in raw_input().split()]
    xor_acu = [0] * (N + 1)
    for i in range(1, N + 1):
        xor_acu[i] = xor_acu[i - 1] ^ arr[i - 1]
    if xor_acu[N] != 0: # search for 0, X, 0, X ..., 0, X type
        X = xor_acu[N]
        dp0 = [1] * (N + 1)
        dpX = [0] * (N + 1)
        for i in range(1,N+1):
            dp0[i] = dp0[i-1] + dpX[i-1] if xor_acu[i] == 0 else dp0[i - 1]
            dpX[i] = dp0[i-1] + dpX[i-1] if xor_acu[i] == X else dpX[i - 1]
        ret = dp0[N - 1]
    else: # search for 0, X, 0, X ..., X, 0 type
        # X == 0 case
        tmp = 1
        Not0Set = set()
        for i in range(1, N):
            if xor_acu[i] == 0:
                tmp *= 2
            else:
                Not0Set.add(xor_acu[i])
        ret = tmp
        if ret > MAX:
            ret = ret % MAX
        # X != 0 case
        for X in list(Not0Set):
            RLE = [] # Run Length Encoding
            _tmp = xor_acu[0]
            cnt = 1
            all_cnt = 1
            for i in range (1, N+1):
                if xor_acu[i] == 0 or xor_acu[i] == X:
                    if xor_acu[i] == _tmp:
                        cnt += 1
                    else:
                        RLE.append((_tmp, cnt))
                        _tmp = xor_acu[i]
                        cnt = 1
                    all_cnt += 1
            RLE.append((_tmp, cnt))
            lRLE = all_cnt
            Not0dp0 = [1] * lRLE
            Not0dpX = [0] * lRLE
            ind = 1
            for i in range(len(RLE)):
                start = 1 if i == 0 else 0
                if RLE[i][0] == 0:
                    for j in range(start, RLE[i][1]):
                        Not0dp0[ind] = Not0dp0[ind - 1] + Not0dpX[ind - 1]
                        Not0dpX[ind] = Not0dpX[ind - 1]
                        ind += 1
                else:
                    for j in range(start, RLE[i][1]):
                        Not0dp0[ind] = Not0dp0[ind - 1]
                        Not0dpX[ind] = Not0dp0[ind - 1] + Not0dpX[ind - 1]
                        ind += 1
            ret += Not0dpX[ind - 2]
            if ret > MAX:
                ret = ret % MAX
    print str(ret)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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

XOR=[0]
for a in A:
    XOR.append(XOR[-1]^a)

ZEROS=[0]
for xor in XOR:
    if xor==0:
        ZEROS.append(ZEROS[-1]+1)
    else:
        ZEROS.append(ZEROS[-1])

if XOR[-1]!=0:
    SUBJ=XOR[-1]
    SUBJ_LIST=[]

    for j in range(N+1):
        if XOR[j]==SUBJ:
            SUBJ_LIST.append(j)

    #print(SUBJ_LIST)

    ZERO=1
    NOW=0

    for i in range(len(SUBJ_LIST)):
        ZERO+=NOW*(ZEROS[SUBJ_LIST[i]]-ZEROS[SUBJ_LIST[i-1]])
        NOW+=ZERO

        #print(NOW,ZERO)

    print(ZERO%mod)

else:
    SET=set(XOR)
    
    from collections import defaultdict
    SUBJ=defaultdict(list)
    for j in range(1,N+1):
        SUBJ[XOR[j]].append(j)

    ANS=1<<(ZEROS[-1]-2)

    for subj in SUBJ:
        if subj==0:
            continue
        ZERO=1
        NOW=0

        for i in range(len(SUBJ[subj])):
            
            ZERO=(ZERO+NOW*(ZEROS[SUBJ[subj][i]]-ZEROS[SUBJ[subj][i-1]]))%mod
            NOW=(NOW+ZERO)%mod

        #print(ZERO,SUBJ[subj],subj)
        ANS=(ANS+NOW)%mod

    print(ANS%mod)

Submission status: Time Limit Exceeded

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

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

XOR=[0]
for a in A:
    XOR.append(XOR[-1]^a)

ZEROS=[0]
for xor in XOR:
    if xor==0:
        ZEROS.append(ZEROS[-1]+1)
    else:
        ZEROS.append(ZEROS[-1])

if XOR[-1]!=0:
    SUBJ=XOR[-1]
    SUBJ_LIST=[]

    for j in range(N+1):
        if XOR[j]==SUBJ:
            SUBJ_LIST.append(j)

    #print(SUBJ_LIST)

    ZERO=1
    NOW=0

    for i in range(len(SUBJ_LIST)):
        ZERO+=NOW*(ZEROS[SUBJ_LIST[i]]-ZEROS[SUBJ_LIST[i-1]])
        NOW+=ZERO

        #print(NOW,ZERO)

    print(ZERO%mod)

else:
    SET=set(XOR)
    
    from collections import defaultdict
    SUBJ=defaultdict(list)
    for j in range(1,N+1):
        SUBJ[XOR[j]].append(j)

    ANS=1<<(ZEROS[-1]-2)

    for subj in SUBJ:
        if subj==0:
            continue
        ZERO=1
        NOW=0

        for i in range(len(SUBJ[subj])):
            
            ZERO+=NOW*(ZEROS[SUBJ[subj][i]]-ZEROS[SUBJ[subj][i-1]])
            NOW+=ZERO

        #print(ZERO,SUBJ[subj],subj)
        ANS=(ANS+NOW)%mod

    print(ANS%mod)