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: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()] 
mod = 10**9 + 7

b = [0]*N #
b[0] = A[0]
for n in range(1,N):
    b[n] = A[n] ^ b[n-1]
#print('累積論理和',b)
m = max(b)
dp = [[0]*(m+1) for j in range(2)]
dp[0] = [True]*(m+1)
dp[1] = [False]*(m+1)
cnt = [0]*(m+1)
z = 0

for i in range(N):
    if b[i] == 0:
        z +=1
    dp[0][b[i]] += dp[1][b[i]]*(z-cnt[b[i]])
    dp[0][b[i]] %= mod
    dp[1][b[i]] += dp[0][b[i]]
    dp[1][b[i]] %= mod
    cnt[b[i]] = z


if b[N-1]:
    print(dp[0][b[N-1]])
else:
    ans = pow(2, z-1, mod)
    for i in range(1,m+1):
        ans += dp[1][i]
        ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()] 
mod = 10**9 + 7

b = [0]*N
b[0] = A[0]
for n in range(1,N):
    b[n] = A[n] ^ b[n-1]

dp = [[not j for i in range(1<<20)] for j in range(2)]
cnt = [0 for i in range(1<<20)]
z = 0

for i in range(N):
    if b[i] == 0:
        z +=1
    dp[0][b[i]] += dp[1][b[i]]*(z-cnt[b[i]])
    dp[0][b[i]] %= mod
    dp[1][b[i]] += dp[0][b[i]]
    dp[1][b[i]] %= mod
    cnt[b[i]] = z

if b[N-1]:
    print(dp[0][b[N-1]])
else:
    ans = pow(2, z-1, mod)
    for i in range(1, 1<<20):
        ans += dp[1][i]
        ans %= mod
    print(ans)

Submission status: Accepted

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: Accepted

Solution code:
from itertools import accumulate
from operator import xor


def solve(acc):
    MOD = 10 ** 9 + 7
    cnt0 = 0
    dp0 = {}
    dp1 = {}
    last_0 = {}
    for a in acc:
        if a == 0:
            cnt0 += 1
        else:
            if a not in dp1:
                dp0[a] = 1
                dp1[a] = 1
                last_0[a] = cnt0
            else:
                bw0 = cnt0 - last_0[a]
                if bw0 > 0:
                    dp0[a] = (dp0[a] + dp1[a] * bw0) % MOD
                    last_0[a] = cnt0
                dp1[a] = (dp1[a] + dp0[a]) % MOD

    if acc[-1] == 0:
        return (pow(2, cnt0 - 1, MOD) + sum(dp1.values())) % MOD
    else:
        return dp0[acc[-1]]


n = int(input())
aaa = list(map(int, input().split()))
acc = list(accumulate(aaa, func=xor))
print(solve(acc))

Submission status: Accepted

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


def solve(acc):
    MOD = 10 ** 9 + 7
    cnt0 = 0
    dp0 = defaultdict(lambda: 1)
    dp1 = defaultdict(lambda: 0)
    last_0 = defaultdict(lambda: 0)
    for a in acc:
        if a == 0:
            cnt0 += 1
        else:
            if a not in dp1:
                dp1[a] = 1
                last_0[a] = cnt0
            else:
                bw0 = cnt0 - last_0[a]
                if bw0 > 0:
                    dp0[a] = (dp0[a] + dp1[a] * bw0) % MOD
                    last_0[a] = cnt0
                dp1[a] = (dp1[a] + dp0[a]) % MOD

    if acc[-1] == 0:
        return (pow(2, cnt0 - 1, MOD) + sum(dp1.values())) % MOD
    else:
        return dp0[acc[-1]]


n = int(input())
aaa = list(map(int, input().split()))
acc = list(accumulate(aaa, func=xor))
print(solve(acc))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = [0 for i in range(n)]
s[0] = a[0]
for i in range(1, n):
  s[i] = s[i-1]^a[i]

MOD = 10**9+7
dp = [[not j for i in range(1<<20)] for j in range(2)]
cnt = [0 for i in range(1<<20)]
z = 0
for i in range(n):
  if s[i]==0:
    z += 1
  dp[0][s[i]] = (dp[0][s[i]]+dp[1][s[i]]*(z-cnt[s[i]])%MOD)%MOD
  dp[1][s[i]] = (dp[1][s[i]]+dp[0][s[i]])%MOD
  cnt[s[i]] = z

if s[n-1]:
  print(dp[0][s[n-1]])
else:
  ans = pow(2, z-1, MOD)
  for i in range(1, 1<<20):
    ans = (ans+dp[1][i])%MOD
  print(ans)

Submission status: Accepted

Solution code:
import sys
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)
    last_0 = {}
    for a in acc:
        if a == 0:
            cnt_0 += 1
        else:
            cnt = counts[a]
            if len(cnt) == 0:
                cnt.append(1)
                last_0[a] = cnt_0
            else:
                btw_0 = cnt_0 - last_0[a]
                if btw_0 > 0:
                    cnt.append(btw_0)
                    cnt.append(1)
                    last_0[a] = cnt_0
                else:
                    cnt[-1] += 1

    ans = pow(2, cnt_0 - 1, MOD)
    for i, cnt in counts.items():
        dp0 = 1
        dp1 = cnt[0]
        for c0, c1 in zip(cnt[1::2], cnt[2::2]):
            dp0 = (dp0 + dp1 * c0) % MOD
            dp1 = (dp1 + dp0 * c1) % MOD
        ans = (ans + dp1) % MOD

    return ans


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


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

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


mod = 10**9 + 7


class Counter:
    def __init__(self, zerocount):
        self.incr = 1
        self.prev_zerocount = zerocount
        self.count = 1


def main():
    n = intin()
    alist = intina()

    xorlist = []
    xor = 0
    for a in alist:
        xor = a ^ xor
        xorlist.append(xor)

    zerocount = 0
    counters = {}

    for xor in xorlist:
        if xor == 0:
            zerocount += 1
            continue
        if xor not in counters:
            counters[xor] = Counter(zerocount)
            continue

        prev_incr = counters[xor].incr
        prev_zerocount = counters[xor].prev_zerocount
        prev_count = counters[xor].count

        incr = modmlt(zerocount - prev_zerocount, prev_count)
        incr = modadd(incr, prev_incr)

        counters[xor].incr = incr
        counters[xor].prev_zerocount = zerocount
        counters[xor].count = modadd(prev_count, incr)

    if xorlist[-1]:
        print(counters[xorlist[-1]].incr)
    else:
        zerosum = pow(2, zerocount - 1, mod)
        xorsum = sum([counter.count for counter in counters.values()]) % mod
        print(modadd(zerosum, xorsum))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10**9 + 7
N = int(input())
S = []
x = 0
for a in map(int, input().split()):
    x ^= a
    S.append(x)

A = defaultdict(int)
B = defaultdict(int)
L = defaultdict(int)
Z = 0

for s in S:
    if s == 0:
        Z += 1
    else:
        A[s] = (A[s] + (Z - L[s])*B[s])%MOD
        B[s] = (A[s] + B[s] + 1)%MOD
        L[s] = Z

if S[-1] != 0:
    print((A[S[-1]] + 1)%MOD)
else:
    print((sum(B.values()) + pow(2, Z-1, MOD))%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N = int(input())
S = []

x = 0
for a in map(int, input().split()):
    x ^= a
    S.append(x)

A = defaultdict(int)
B = defaultdict(int)
L = defaultdict(int)
Z = 0

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(a+1)
else:
    for s in S:
        if s == 0:
            Z += 1
        else:
            A[s] = (A[s] + (Z - L[s])*B[s])%MOD
            B[s] = (A[s] + B[s] + 1)%MOD
            L[s] = Z
    print((sum(B.values()) + pow(2, Z-1, MOD))%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import sqrt
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N = int(input())
S = []

x = 0
for a in map(int, input().split()):
    x ^= a
    S.append(x)

A = defaultdict(int)
B = defaultdict(int)
L = defaultdict(int)
Z = 0

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(a+1)
else:
    for s in S:
        if s == 0:
            Z += 1
        else:
            A[s] = (A[s] + (Z - L[s])*B[s])%MOD
            B[s] = (A[s] + B[s] + 1)%MOD
            L[s] = Z
    print((sum(B.values()) + pow(2, Z-1, MOD))%MOD)

Submission status: Accepted

Solution code:
N=int(input())
mod=10**9+7
X=[-1]*N
for i,a in enumerate(map(int,input().split())):
    if i==0:
        X[0]=a
    else:
        X[i]=X[i-1]^a
if X[-1]>0:
    x=X[-1]
    dp0=1
    dp1=0
    zero=0
    for i in range(N):
        if X[i]==x:
            dp0=(dp0+dp1*zero)%mod
            zero=0
            dp1=(dp1+dp0)%mod
        elif X[i]==0:
            zero+=1
        
    print(dp0)
    exit()
from collections import defaultdict
dp0=defaultdict(lambda :1)
dp1=defaultdict(int)
zero=defaultdict(int)
zeronow=0
for i in range(N-1):
    x=X[i]
    if x>0:
        dp0[x]=(dp0[x]+dp1[x]*(zeronow-zero[x]))%mod
        zero[x]=zeronow
        dp1[x]=(dp1[x]+dp0[x])%mod
    elif x==0:
        zeronow+=1

print((sum(dp1.values())+pow(2,zeronow,mod))%mod)

Submission status: Accepted

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


# cumsum
b_list = [0] * N
b = 0

for i in range(N):
    a = a_list[i]
    b = a ^ b
    b_list[i] = b

v_all_dict = dict()
for b in b_list:
    v_all_dict[b] = [0, 0, 1]

zeros = 0



for i in range(N):

    b = b_list[i]

    t = v_all_dict[b][0]

    # new b
    if t < zeros:
        v_all_dict[b][2] = (v_all_dict[b][2] + v_all_dict[b][1] * (zeros - t)) % LARGE
        v_all_dict[b][0] = zeros

    # up
    v_all_dict[b][1] = (v_all_dict[b][1] + v_all_dict[b][2]) % LARGE

    # zeros
    if b == 0:
        zeros += 1

# res
if b_list[-1] == 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:
    v = b_list[-1]
    res = v_all_dict[v][2]

print(res % LARGE)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
P = 10**9+7
X = [1] * (1<<20) # 0
Y = [0] * (1<<20) # 1
Z = [0] * (1<<20) # Cnt of Zeros at Last update
Z[0] = 1
X[0] = (P+1) // 2

s = 0
for i in range(N):
    s ^= A[i]
    if s == 0:
        X[0] = (X[0] * 2) % P
        Z[0] += 1
    else:
        X[s] = (X[s] + Y[s] * (Z[0] - Z[s])) % P
        Y[s] = (X[s] + Y[s]) % P
        Z[s] = Z[0]

print((X[s] + sum(Y)*(s==0)) % P)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = [1]*U
arr_1 = [0]*U
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr_0[c]
  b = arr_1[c]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr_0[c] = a
  arr_1[c] = b
 
answer = 0
if c != 0:
  answer = arr_0[c]
else:
  answer = sum(arr_1[1:])
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = [1] * U
arr_1 = [0] * U
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr_0[c]
  b = arr_1[c]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr_0[c] = a
  arr_1[c] = b
 
answer = 0
if c != 0:
  answer = arr_0[c]
else:
  answer = sum(arr_1[1:])
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

Submission status: Runtime Error

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
dp = [{sv:0 for sv in sp} for _ in range(len(ais))]

for j in range(len(ais)):
	for i in range(j+1):
		v = p[j] ^ (p[i-1] if i-1>=0 else 0)
		dp[j][v] += (dp[i-1][v] if i-1>=0 else 1)

print sum(dp[-1].values()) % mod

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
max_a = 20 ** 2
MOD = 10 ** 9 + 7

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] ^ a[i]


if ru[-1] != 0:
    # 0, ru[-1], 0, ru[-1], 0, ..., ru[-1]
    dp = [0] * (max_a)
    dp[0] = 1
    tot_ex0 = 0
    for i in range(n):
        if i == n - 1:
            print(dp[0])
            exit()
        if ru[i + 1] == 0:
            dp[0] += tot_ex0
            dp[0] %= MOD
        elif ru[i + 1] == ru[-1]:
            dp[ru[i + 1]] += dp[0]
            dp[ru[i + 1]] %= MOD
            tot_ex0 += dp[0]
            tot_ex0 %= MOD
else:
    # 0, x, 0, x, 0, x, ..., 0 (x != 0)
    dp = [0] * max_a
    dq = [1] * max_a
    set_evaled = [0] * max_a
    times = 0
    ans = 0
    for i in range(n):
        if i == n - 1:
            ans = sum(dp)
            break
        elif ru[i + 1] == 0:
            # これを遅延評価する
            # for j in range(max_a):
            #     dq[j] += dp[j]
            times += 1
        else:
            dq[ru[i + 1]] += (times - set_evaled[ru[i + 1]]) * dp[ru[i + 1]]
            dq[ru[i + 1]] %= MOD
            set_evaled[ru[i + 1]] = times
            dp[ru[i + 1]] += dq[ru[i + 1]]
            dp[ru[i + 1]] %= MOD
    # 0, 0, 0, 0, 0, 0, ..., 0
    cnt_0 = sum([1 for i in range(n) if ru[i + 1] == 0])
    ans = (ans + pow(2, cnt_0 - 1, MOD)) % MOD
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
max_a = 20 ** 2
MOD = 10 ** 9 + 7

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] ^ a[i]

ptn = [0] * (max_a)
ptn[0] = 1
tot_ex0 = 0

if ru[-1] != 0:
    # 0, ru[-1], 0, ru[-1], 0, ..., ru[-1]
    for i in range(n):
        if i == n - 1:
            print(ptn[0])
            exit()
        if ru[i + 1] == 0:
            ptn[0] += tot_ex0
            ptn[0] %= MOD
        elif ru[i + 1] == ru[-1]:
            ptn[ru[i + 1]] += ptn[0]
            ptn[ru[i + 1]] %= MOD
            tot_ex0 += ptn[0]
            tot_ex0 %= MOD
print(re)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
max_a = 20 ** 2
MOD = 10 ** 9 + 7

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] ^ a[i]

ptn = [0] * (max_a)
ptn[0] = 1
tot_ex0 = 0
if ru[-1] != 0:
    for i in range(n):
        if i == n - 1:
            print(tot_ex0)
            exit()
        if ru[i + 1] == 0:
            ptn[0] += tot_ex0
            ptn[0] %= MOD
        elif ru[i + 1] == ru[-1]:
            ptn[ru[i + 1]] += ptn[0]
            ptn[ru[i + 1]] %= MOD
            tot_ex0 += ptn[0]
            tot_ex0 %= MOD
print(re)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
//const long long MOD = 998244353;
const long long INF_LL = 1e18+3; const int INF_int = 1e9+3;
#define ll long long
#define rep(i,n) for(int i = 0;i<n;i++)
#define lrep(i,n) for(long long i = 0;i<n;i++)
#define All(a) a.begin(),a.end()
#define Debug_Output_ALL(a) for(auto itr = a.begin();itr!=a.end();itr++) cout << *itr << " ";cout << endl;
template <typename T>
T power(T x,T n,long long MOD = MOD){
    T ret = 1;
    while(n>0){
        if(n%2==1) ret*=x;
        n/=2,x*=x;
        if(MOD!=0) x%=MOD,ret%=MOD;
    }
    return ret;
}
int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    ll totalxor = 0;
    rep(i,n) cin >> a[i],totalxor^=a[i];
    ll ans;
    if(totalxor==0){
        vector<int> zero;
        ll now = 0;
        rep(i,n){
            now^=a[i];
            if(now==0) zero.push_back(i);
        }
        ll zsize = zero.size()-1;
        ans=power(2LL,zsize);
        map<ll,ll> mp;
        map<ll,ll> mp3;
        int nowindex = 0;
        now = 0;
        rep(i,zero.size()){
            map<ll,ll> mp2;
            for(int j = nowindex;j<zero[i];j++){
                now^=a[j];
                mp2[now]++;
            }
            for(auto x:mp2){
                if(mp.find(x.first)==mp.end()) mp[x.first]=x.second;
                else{
                    mp[x.first]*=((i+1-mp3[x.first])*(x.second)+1);
                    mp[x.first]+=(x.second);
                }
                mp[x.first]%=MOD;
                mp3[x.first] = i+1;
            }
            now = 0;
            nowindex=zero[i]+1;
        }
        for(auto x:mp){
            ans+=x.second;
        }
    }
    else{
        vector<int> zero;
        ll now = 0;
        rep(i,n){
            now^=a[i];
            if(now==0) zero.push_back(i);
        }
        ll zsize = zero.size()-1;
        ans = 1;
        int nowindex = 0;
        now = 0;
        ll last = -1;
        lrep(i,zero.size()){
            ll cnt = 0;
            for(int j = nowindex;j<zero[i];j++){
                now^=a[i];
                if(now==totalxor) cnt++;
            }
            if(cnt>0){
                ans*=((i-last)*(cnt)+1);
                ans+=cnt;
                ans%=MOD;
                last = i;
            }
            now = 0;
            nowindex=zero[i]+1;            
        }
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:

"""
Writer:SPD_9X2
https://atcoder.jp/contests/diverta2019/tasks/diverta2019_e


区分けされた部分1つ分のxorをAとすると、全体のxorは0かAかじゃないといけない
A→0→A→0となる部分に仕切りを入れられる
→DP

全体のxorが0以外の時は簡単→普通にDPすればいいだけ

全体のxorが0の時は、0を含め、出て来たすべてのxorに関して調べなきゃいけない
0が多いとき、計算量がO(N**2)になっちゃいそう…
Aをまとめて処理しなくてはいけない？

Aとしてありうるのは途中で出て来た0を含めたすべての数字
そこ1箇所で切ったのも採用可能＋今まで出て来たAのうち、それ以降で1度でも0が出たものに加えるのも可能
→0の選び方も自由だからなぁ…

愚直なdp遷移を考えてみる
dp[A] = 1 + Σdp[今まで出たA] * (その間にある0の数) →O(N**2)じゃ…(死)
どうやって高速化しよう…→上の推移式をO(1)で計算できないか？
→Σdp[今まで出たA]を記録して置けば、その間にあるAは全体で同数増加なのでO(1)で計算できる！！

"""
mod = 10**9+7
N = int(input())

a = list(map(int,input().split()))

allxor = 0
for i in range(N):
    allxor ^= a[i]

if allxor != 0: #0じゃない場合、簡単に解ける

    dp = [1,0] #0で終わってる場合数、allxorで終わってる場合数

    nxor = 0
    for i in range(N-1):
        ndp = [dp[0] % mod,dp[1] % mod]
        nxor ^= a[i]

        if nxor == 0:
            ndp[0] += dp[1]
        elif nxor == allxor:
            ndp[1] += dp[0]

        dp = ndp
        #print (dp)

    print (dp[0] % mod)

else:

    #必要なのは、各位置で今まで出た0の数
    #最後にAが出た位置
    #今までの各Aの通り数の和
    #0に関しては最後に計算する

    print (pasass)

    zsum = [1]
    sumdic = {}
    inddic = {}
    nxor = 0

    for i in range(N-1):

        nxor ^= a[i]

        if nxor == 0:
            zsum.append(zsum[-1] + 1)
            continue
        else:
            zsum.append(zsum[-1])

        if nxor not in inddic:
            inddic[nxor] = i
            sumdic[nxor] = 1
        else:
            dpa = 1 + sumdic[nxor] * ( zsum[-1] - zsum[inddic[nxor]] )
            sumdic[nxor] += dpa
            sumdic[nxor] %= mod
            inddic[nxor] = i

    ans = 0
    for i in sumdic:
        ans += sumdic[i]
        ans %= mod

    #print (ans,zsum)

    ans += pow(2,zsum[-1]-1,mod)

    print (ans % mod)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_left as bisect
import sys
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
S = [0]*(N+1)
zeros = []
count = defaultdict(list)
now = -1
for i in range(N):
    S[i] = S[i-1]^A[i]
    if S[i] == 0:
        zeros.append(i)
    else:
        count[S[i]].append(i)
if S[N-1] != 0:
    a = S[N-1]
    res = []
    for i in count[a]:
        res.append(bisect(zeros, i)-cnt)
        cnt+=res[-1]
    res0 = 1
    res1 = 0
    for c in res:
        res0 = res0+res1*c
        res1 = res1+res0
        res0%=mod
        res1%=mod
    print(res0)
    sys.exit()
ans = pow(2, len(zeros)-1, mod)
for a in count.keys():
    cnt = 0
    res = []
    for i in count[a]:
        res.append(bisect(zeros, i)-cnt)
        cnt+=res[-1]
    res0 = 1
    res1 = 0
    for c in res:
        res0 = res0+res1*c
        res1 = res1+res0
        res0%=mod
        res1%=mod
    ans+=res1
print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
n = max(A).bit_length()
S = [0]*N
for i, a in enumerate(A):
    S[i]=S[i-1]^a
index = [[-1] for _ in range(2<<n)]
cumsum = [0]*(N+1)
for i, s in enumerate(S):
    index[s].append(i)
    cumsum[i] = cumsum[i-1]
    if s == 0:
        cumsum[i]+=1
ans = 0
if S[-1] == 0:
    print(1/0)
    for i in range(1, 1<<n):
        l = len(index[i])
        if l == 1:
            continue
        dp = [0]*(l-1)
        dp_cum = [0]*(l-1)
        for j, k in enumerate(index[i][1:]):
            dp[j] = (dp_cum[j-1]*(cumsum[k]-cumsum[index[i][j]])+1)%mod
            dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
        ans+=dp_cum[-1]
        ans%=mod
    ans+=pow(2, cumsum[N-1]-1, mod)
    ans%=mod
else:
    l = len(index[S[-1]])
    dp = [0]*(l-1)
    dp_cum = [0]*(l-1)
    for j in range(l-1):
        k = index[S[-1]][j+1]
        p = index[S[-1]][j]
        dp[j] = dp_cum[j-1]*(cumsum[k]-cumsum[p])%mod+1
        dp_cum[j] = (dp_cum[j-1]*(cumsum[k]-cumsum[p])+dp[j])%mod
    ans = dp[-1]%mod
print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
n = max(A).bit_length()
S = [0]*N
for i, a in enumerate(A):
    S[i]=S[i-1]^a
index = [[-1] for _ in range(2<<n)]
cumsum = [0]*(N+1)
for i, s in enumerate(S):
    index[s].append(i)
    cumsum[i] = cumsum[i-1]
    if s == 0:
        cumsum[i]+=1
ans = 0
if S[-1] == 0:
    print(1/0)
    for i in range(1, 1<<n):
        l = len(index[i])
        if l == 1:
            continue
        dp = [0]*(l-1)
        dp_cum = [0]*(l-1)
        for j, k in enumerate(index[i][1:]):
            dp[j] = (dp_cum[j-1]*(cumsum[k]-cumsum[index[i][j]])+1)%mod
            dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
        ans+=dp_cum[-1]
        ans%=mod
    ans+=pow(2, cumsum[N-1]-1, mod)
    ans%=mod
else:
    l = len(index[S[-1]])
    dp = [0]*(l-1)
    dp_cum = [0]*(l-1)
    for j in range(l-1):
        k = index[S[-1]][j+1]
        p = index[S[-1]][j]
        dp[j] = dp_cum[j-1]*(cumsum[k]-cumsum[p])%mod+1
        dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
    ans = dp[-1]%mod
print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
n = 21
S = [0]*N
for i, a in enumerate(A):
    S[i]=S[i-1]^a
index = [[-1] for _ in range(2<<n)]
cumsum = [0]*(N+1)
for i, s in enumerate(S):
    index[s].append(i)
    cumsum[i] = cumsum[i-1]
    if s == 0:
        cumsum[i]+=1
ans = 0
if S[-1] == 0:
    for i in range(1, 1<<n):
        l = len(index[i])
        if l == 1:
            continue
        dp = [0]*(l-1)
        dp_cum = [0]*(l-1)
        for j, k in enumerate(index[i][1:]):
            dp[j] = (dp_cum[j-1]*(cumsum[k]-cumsum[index[i][j]])+1)%mod
            dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
        ans+=dp_cum[-1]
        ans%=mod
    ans+=pow(2, cumsum[N-1]-1, mod)
    ans%=mod
else:
    print(1/0)
    l = len(index[S[-1]])
    dp = [0]*(l-1)
    dp_cum = [0]*(l-1)
    for j, k in enumerate(index[S[-1]][1:]):
        dp[j] = (dp_cum[j-1]*(cumsum[k]-cumsum[index[S[-1]][j]])+1)%mod
        dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
    ans = dp[-1]%mod
print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
n = max(A).bit_length()
S = [0]*N
for i, a in enumerate(A):
    S[i]=S[i-1]^a
index = [[-1] for _ in range(2<<n)]
cumsum = [0]*(N+1)
for i, s in enumerate(S):
    index[s].append(i)
    cumsum[i] = cumsum[i-1]
    if s == 0:
        cumsum[i]+=1
ans = 0
if S[-1] == 0:
    for i in range(1, 1<<n):
        l = len(index[i])
        if l == 1:
            continue
        dp = [0]*(l-1)
        dp_cum = [0]*(l-1)
        for j, k in enumerate(index[i][1:]):
            dp[j] = (dp_cum[j-1]*(cumsum[k]-cumsum[index[i][j]])+1)%mod
            dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
        ans+=dp_cum[-1]
        ans%=mod
    ans+=pow(2, cumsum[N-1]-1, mod)
    ans%=mod
else:
    print(1/0)
    l = len(index[S[-1]])
    dp = [0]*(l-1)
    dp_cum = [0]*(l-1)
    for j, k in enumerate(index[S[-1]][1:]):
        dp[j] = (dp_cum[j-1]*(cumsum[k]-cumsum[index[S[-1]][j]])+1)%mod
        dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
    ans = dp[-1]%mod
print(ans)