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: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = np.ones(U,dtype=np.int64)
arr_1 = np.zeros(U,dtype=np.int64)
 
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 = arr_1[1:].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1
 
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[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b
 
answer = 0
if c != 0:
  answer = arr[c,0]
else:
  answer = arr[1:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1
 
zero_update = np.zeros(U,dtype=np.int64) #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[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b
 
answer = 0
if c != 0:
  answer = arr[c,0]
else:
  answer = arr[1:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

dp = [[None for _ in range(N)] for __ in range(N+1)]
dp[0] = [0 for _ in range(N)]

def xors(i, j):
    xor = A[i-1]
    for k in range(i,j):
        xor ^= A[k]
    return xor


for i in range(1, N+1):
    dp[i][0] = 1
    for j in range(1,i):
        dp[i][j] = 0
        for k in range(j):
            if xors(k+1, j) == xors(j+1, i):
                dp[i][j] += dp[j][k]

print(sum(dp[-1]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7
data = [[[a[0], 1, a[0], 1]]]
for i in range(n-1):
    data_temp = []
    for j in data[-1]:
        if j[0] == j[2]:
            new_data = [j[0], j[1]+1, a[i+1], j[3]]
            for k in data_temp:
                if k[0] == new_data[0] and k[1] == new_data[1] and k[2] == new_data[2]:
                    k[3] = (k[3] + new_data[3]) % mod
                    break
            else:
                data_temp.append(new_data)
        if j[1] == 1:
            new_data2 = [j[2]^a[i+1], j[1], j[2]^a[i+1],j[3]]
        else:
            new_data2 = [j[0], j[1], j[2]^a[i+1],j[3]]
        for k in data_temp:
            if k[0] == new_data2[0] and k[1] == new_data2[1] and k[2] == new_data2[2]:
                k[3] = (k[3] + new_data2[3]) % mod
                break
        else:
            data_temp.append(new_data2)
    data.append(data_temp)
    del data[0]
count = 0
for i in data[-1]:
    if i[0] == i[2]:
        count =(count + i[3]) % mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
C = np.zeros(N,dtype = np.int64) # cumsum
 
cum = 0
for i,a in enumerate(A):
  cum ^= a
  C[i] = cum
 
arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1
 
zero_update = np.zeros(U,dtype=np.int64) #0が出てきて更新した回数
zero_cnt = 0
 
for i in range(N):
  c = C[i]
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b
 
answer = 0
final = C[-1]
if final != 0:
  answer = arr[final,0]
else:
  answer = arr[1:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def cnt(l, r, x):
    if r == n - 1:
        return 1
    t = (l, r, x)
    if t in memo:
        return memo[t]
    re = 0
    dpi = dp[r + 1]
    for j in range(r + 1, n):
        if dpi[j] == x:
            re += cnt(r + 1, j, x)
    memo[t] = re
    return re

memo = {}
md = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]
for i, dpi in enumerate(dp):
    s = dpi[i]
    for j in range(i + 1, n):
        dpi[j] = s = s ^ a[j]
ans = 0
for r in range(n):
    ans = (ans + cnt(0, r, dp[0][r])) % md
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

MOD = 10**9 + 7
U = 2 ** 20

N = int(input())
A = [int(x) for x in input().split()]
C = np.zeros(N,dtype = np.int64) # cumsum

cum = 0
for i,a in enumerate(A):
  cum ^= a
  C[i] = cum

arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1

zero_update = np.zeros(U,dtype=np.int64) #0が出てきて更新した回数
zero_cnt = 0

for i in range(N):
  c = C[i]
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b

answer = 0
final = C[-1]
if final != 0:
  answer = arr[final,0]
else:
  answer = arr[:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

MOD = 10**9 + 7

N = int(input())
A = [int(x) for x in input().split()]
C = np.zeros(N,dtype = np.int64) # cumsum

cum = 0
for i,a in enumerate(A):
  cum ^= a
  C[i] = cum

X = list(set(C)) # 候補
if 0 in X:
  X.remove(0)

X_to_idx = {x:i for i,x in enumerate(X)}

L = len(X)

arr = np.zeros((L,2),dtype=np.int64)
arr[:,0] = 1
# a,0,...でいまのところ矛盾なくできている列
# 0,a,...

zero_update = np.zeros(L,dtype=np.int64) #0が出てきて更新した回数
zero_cnt = 0

for i in range(N):
  c = C[i]
  if c == 0:
    zero_cnt += 1
    continue
  idx = X_to_idx[c]
  # 蓄積された0の回数分アップデート
  n = zero_cnt - zero_update[idx]
  zero_update[idx] = zero_cnt
  a = arr[idx,0]
  b = arr[idx,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[idx,0] = a
  arr[idx,1] = b

answer = 0
final = C[-1]
if final != 0:
  idx = X_to_idx[final]
  answer = arr[idx,0]
else:
  answer = arr[:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N = int(input())
a = tuple([int(i) for i in input().split(" ")])


def beauty(l):
    retval = 0
    for i in l:
        retval = retval ^ i
    return retval


@lru_cache()
def is_able(l, k):
    retval = 0
    if beauty(l) == k:
        retval += 1
    for i in range(1, len(l)):
        if beauty(l[:i:]) != k:
            continue
        else:
            retval += is_able(l[i::], k)
    return retval


retval = 0
for i in range(21):
    retval += is_able(a, i)
print(retval % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N=int(input())
a=tuple([int(i) for i in input().split(" ")])

def beauty(l):
    retval=0
    for i in l:
        retval=retval^i
    return retval


@lru_cache()
def is_able(l,k):
    retval=0
    if beauty(l)==k:
        retval+=1
    for i in range(1,len(l)):
        if beauty(l[:i:])!=k:
            continue
        else:
            retval+= is_able(l[i::],k)
    return retval

retval=0
for i in range(21):
    retval+=is_able(a,i)
print(retval%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
max_a = 2 ** 20
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: Accepted

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

data=[0]
for i in range(N):
    data.append(data[-1]^A[i])

if data[-1]==0:
    ans=0
    zero=[int(data[i]==0) for i in range(N+1)]
    for i in range(1,N+1):
        zero[i]+=zero[i-1]

    val={}
    for i in range(N+1):
        if data[i]!=0:
            if data[i] not in val:
                val[data[i]]=[]
            val[data[i]].append(i)

    for v in val:
        B=0
        W=1
        for i in range(len(val[v])):
            j=val[v][i]
            if i!=len(val[v])-1:
                B+=W
                W+=B*(zero[val[v][i+1]]-zero[j])
                B%=mod;W%=mod
            else:
                B+=W
                B%=mod
        ans+=B
        ans%=mod

    n=data.count(0)
    ans+=pow(2,n-2,mod)
    ans%=mod
    print(ans)
else:
    val=data[-1]
    que=[0]*2**20
    dp=[0]*(N+1)
    dp[0]=1
    que[0]=1
    for i in range(1,N+1):
        j=data[i]
        dp[i]=que[j^val]
        que[data[i]]+=dp[i]
        que[data[i]]%=mod

    print(dp[N]%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
acc = [0]
acc0 = [0]*(n+1)
for i in range(n):
  acc.append(acc[-1]^a[i])
  if i:
    acc0[i+1] += acc0[i]
  if acc[-1] == 0:
    acc0[i+1] += 1
if acc[-1] != 0:
  s = acc[-1]
  ansls = []
  cnt0 = 0
  cnts = 0
  flg = 0
  dp = [0,0]
  for i in range(1,n+1):
    if acc[i] == s:
      dp = [dp[0]+dp[1]+1,dp[1]]
    elif acc[i] == 0:
      dp = [dp[0],dp[0]+dp[1]]
    dp[0] %= mod
    dp[1] %= mod
  print((dp[1]+1)%mod)
else:
  dcn = defaultdict(list)
  dp = defaultdict(list)
  c0 = 0
  for i in range(1,n+1):
    if acc[i]:
      dcn[acc[i]].append(i)
    else:
      c0 += 1
  ans = pow(2,c0-1,mod)
  for i in range(1,n+1):
    t = acc[i]
    if t:
      if not dp[t]:
        dp[t] = [1,0]
      else:
        idx = bisect.bisect_left(dcn[t],i)
        n0 = acc0[i]-acc0[dcn[t][idx-1]]
        dp[t][1] += n0*dp[t][0]
        dp[t][0] += dp[t][1]+1
        dp[t][0] %= mod
        dp[t][1] %= mod
  for t,ls in dp.items():
    ans += ls[0]
    ans %= mod
  print(ans)

Submission status: Accepted

Solution code:
import sys

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={}
    cnt0=[1]*len(cs)
    for i,s in enumerate(cs[1:],1):
        if s==0:
            cnt0[i]=cnt0[i-1]+1
        elif s in cnt:
            cnt0[i]=cnt0[i-1]
            c0=cnt0[i]-cnt0[cnt[s][2]]
            cnt[s][0]=(cnt[s][0]+cnt[s][1]*c0)%md
            cnt[s][1]=(cnt[s][1]+cnt[s][0])%md
            cnt[s][2]=i
        else:
            cnt0[i]=cnt0[i-1]
            cnt[s]=[1,1,i]
    #print(cnt)
    #print(cnt0)

    if cs[-1]==0:ans=sum(v[1] for v in cnt.values())+pow(2,cnt0[-1]-2,md)
    else:ans=cnt[cs[-1]][0]
    print(ans%md)

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    mod = 1000000007

    for i in range(N-1):
        A[i+1] ^= A[i]
    if A[-1]:
        a = A[-1]
        ans_a = 0
        ans_zero = 1
        for i in range(N-1):
            if A[i] == a:
                ans_a = (ans_a + ans_zero)%mod
            elif A[i] == 0:
                ans_zero = (ans_zero + ans_a)%mod
        print(ans_zero)
    else:
        dic = {}
        zero_num = 0
        for a in A:
            if a:
                if a in dic:
                    dic[a].append(zero_num)
                else:
                    dic[a] = [zero_num]
            else:
                zero_num += 1
        ans = (1 << (zero_num-1))%mod
        for X in dic.values():
            ans_x = 1
            ans_zero = 1
            for i in range(1, len(X)):
                ans_zero = (ans_zero + ans_x * (X[i] - X[i-1])) % mod
                ans_x = (ans_x + ans_zero) % mod
            ans = (ans + ans_x)%mod
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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に関しては最後に計算する
    

    zsum = [1]
    lastA = {}
    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
            lastA[nxor] = 1
        else:
            dpa = lastA[nxor] + sumdic[nxor] * (zsum[-1] - zsum[inddic[nxor]])
            lastA[nxor] = dpa % mod
            sumdic[nxor] += dpa % mod
            sumdic[nxor] %= mod
            inddic[nxor] = i

            #print (i,nxor,sumdic)

    ans = 0
    #print (sumdic)
    for i in sumdic:
        ans += sumdic[i]
        ans %= mod

    #print (ans,zsum)

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

    print (ans % mod)

Submission status: Accepted

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 = []
    cnt = 0
    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
    ans%=mod
print(ans)

Submission status: Accepted

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

mod=10**9+7

S=[A[0]]
for i in range(1,N):
    S.append(S[-1]^A[i])

if S[-1]==0:
    sss=max(S)
    data=[[] for i in range(sss+1)]

    for i in range(N):
        data[S[i]].append(i)

    count_0=[0]*N
    for u in data[0]:
        count_0[u]+=1
    for i in range(1,N):
        count_0[i]+=count_0[i-1]
    
    ans=pow(2,len(data[0])-1,mod)

    for i in range(1,sss+1):
        if data[i]:
            h=data[i]
            l=len(h)
            dp=[1,1]
            for j in range(1,l):
                d=[0,0]
                num=count_0[h[j]]-count_0[h[j-1]]
                d[0]=(dp[0]+dp[1]*num)%mod
                d[1]=(dp[0]+dp[1]+dp[1]*num)%mod
                dp=d
            ans=(ans+dp[1])%mod

else:
    qqq=S[-1]
    h=[]
    count_0=[0]*N
    for i in range(N):
        if S[i]==qqq:
            h.append(i)
        elif S[i]==0:
            count_0[i]=1

    for i in range(1,N):
        count_0[i]+=count_0[i-1]
    
    ans=0

    l=len(h)
    dp=[1,1]
    for j in range(1,l):
        d=[0,0]
        num=count_0[h[j]]-count_0[h[j-1]]
        d[0]=(dp[0]+dp[1]*num)%mod
        d[1]=(dp[0]+dp[1]+dp[1]*num)%mod
        dp=d
    ans=(ans+dp[0])%mod
print(ans)

Submission status: Accepted

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

MOD = 10**9+7
N = int(readline())
A = list(map(int, readline().split()))
SA = [0]*N
SA[0] = A[0]
for i in range(1, N):
    SA[i] = SA[i-1]^A[i]
table = [int(sa == 0) for sa in SA]
for i in range(1, N):
    table[i] += table[i-1]

table.append(0)
cnt = 0
pre = [-1]*(1<<20)
dp0 = [1]*(1<<20)
dp = [0]*(1<<20)
for i in range(N):
    a = SA[i]    
    if a:
        y = table[i]-table[pre[a]]
        pre[a] = i
        dp[a], dp0[a] = dp0[a] + (1+y)*dp[a], dp0[a] + y*dp[a]
        dp[a] %= MOD
        dp0[a] %= MOD
    else:
        cnt += 1

if SA[-1]:
    ans = dp0[SA[-1]]
else:
    ans = pow(2, cnt-1, MOD)
    for t in dp:
        ans = (ans+t)%MOD
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import xor

MOD = 10**9 + 7
M = 2**20

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    Bs = list(accumulate([0]+As, xor))

    if Bs[-1] != 0:
        dp = [1, 0]
        for B in Bs[:-1]:
            if B == 0:
                dp[0] = (dp[0]+dp[1]) % MOD
            elif B == Bs[-1]:
                dp[1] = (dp[0]+dp[1]) % MOD
        return dp[0]
    else:
        ans = (2 ** (Bs.count(0)-2)) % MOD
        RunLens = [[] for _ in range(M)]
        num0 = 0
        num0Prevs = [0] * M
        numBs = [0] * M
        for B in Bs:
            if B == 0:
                num0 += 1
            else:
                if num0 != num0Prevs[B]:
                    RunLens[B].append(numBs[B])
                    RunLens[B].append(num0 - num0Prevs[B])
                    numBs[B] = 0
                    num0Prevs[B] = num0
                numBs[B] += 1
        for B in range(M):
            RunLens[B].append(numBs[B])
            RunLens[B].append(num0 - num0Prevs[B])

        for B in range(M):
            if len(RunLens[B]) == 2: continue
            dp = [1, 0]
            for i, RL in enumerate(RunLens[B][2:-1], 1):
                dp[i%2] = (dp[i%2] + dp[1-i%2]*RL) % MOD
            ans = (ans + dp[1]) % MOD
        return ans

print(solve())

Submission status: Accepted

Solution code:
def pow(n,k,m):#n^k mod m
    ans = 1
    while k>0:
        if(k & 1):ans = (ans*n) % m
        n = (n*n)%m
        k >>= 1
    return ans

MOD = 10**9 + 7

n = int(input())

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

for i in range(1,n):
    a[i] = a[i]^a[i-1] #累積和

zero = [0 for i in range(n)] #zero[i] = i番目までの0の個数

if a[0] == 0: zero[0] = 1

for i in range(1,n):
    if a[i] == 0:zero[i] = zero[i-1]+1
    else : zero[i] = zero[i-1]

dp = [0 for i in range(n)]

pre,dpsum = {},{}

for i in range(n):
    if a[i] == 0:continue
    if pre.get(a[i]) is None:
        dp[i] = 1
        pre[a[i]] = i
        dpsum[a[i]] = 1
    else:
        j = pre[a[i]]
        z = zero[i]-zero[j]
        dp[i] = (dpsum[a[i]]*z + dp[j]) % MOD
        pre[a[i]] = i
        dpsum[a[i]] = (dp[i]+dpsum[a[i]]) % MOD

if a[-1] != 0:
    print(dp[-1])
else:
    print((pow(2,zero[-1]-1,MOD)+sum(dp)) % MOD)

Submission status: Accepted

Solution code:
MAX = 10**9 + 7
MAXAi = 1<<20

def solve2():
    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]
    dp = [[not j for i in range(MAXAi)] for j in range(2)]
    cnt = [0 for i in range (MAXAi)]
    cnt_zero = 0
    for i in range(1, N + 1):
        if xor_acu[i] == 0:
            cnt_zero += 1
        dp[0][xor_acu[i]] += dp[1][xor_acu[i]] * (cnt_zero - cnt[xor_acu[i]])
        dp[0][xor_acu[i]] %= MAX
        dp[1][xor_acu[i]] += dp[0][xor_acu[i]]
        dp[1][xor_acu[i]] %= MAX
        cnt[xor_acu[i]] = cnt_zero
    if xor_acu[N] != 0:
        ret = dp[0][xor_acu[N]]
    else:
        ret = pow(2, cnt_zero - 1, MAX)
        for j in range(1, MAXAi):
            ret += dp[1][j]
            ret %= MAX
    print str(ret)

if __name__ == '__main__':
    solve2()

Submission status: Accepted

Solution code:
# 参考にしたもの
# 1.解説 累積XORのケツが0な場合はこっちのやり方に則った
# 2.シナモンロールさんのブログ(https://cinnamo-coder.hatenablog.com/entry/2019/05/12/172458)


def main():
    import sys
    input = sys.stdin.readline

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

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

    if cum_xor[-1] != 0:
        dp = [[0]*2 for i in range(N+1)]
        # dp[i][0]:i番目まで見て、選んだやつらの最後が0の数
        # dp[i][1]:i番目まで見て、選んだやつらの最後がXの数
        # 累積XORの最後がX(!=0)なら 0X0X0X0Xになるように選ぶ( X XOR X = 0 だしね♡)
        X = cum_xor[-1]
        dp[0][0] = 1
        for i in range(1, N + 1):  # 最後の要素はどうせXなので回さなくても良い
            dp[i][0] = dp[i - 1][0] % mod
            dp[i][1] = dp[i - 1][1] % mod
            if cum_xor[i] == 0:
                dp[i][0] += dp[i - 1][1]
            elif cum_xor[i] == X:
                dp[i][1] += dp[i-1][0]
        # N-1番目までで、最後が0になってる選び方をして、それに最後の奴を加えるだけなのでdp[N-1][0]
        print(dp[N-1][0] % mod)
    else:
        # dp[X][j]:美しさをXとしたとき、最後に選んだのが(0 / X)
        dp = [[1, 0] for i in range((1 << 20) + 1)]

        # cnt______[X]:美しさがXの選び方で、今まで出てきた0の数
        cnt_zero_prev_cumXOR_i = [0] * ((1 << 20)+1)
        cnt_zero_now = 0

        for i in range(1, N + 1):
            if cum_xor[i] == 0:
                cnt_zero_now += 1
            else:
                # まず更新してなかった0の部分をまとめて更新
                dp[cum_xor[i]][0] += dp[cum_xor[i]][1] * \
                    (cnt_zero_now - cnt_zero_prev_cumXOR_i[cum_xor[i]])
                dp[cum_xor[i]][0] %= mod
                # そしたらいまの数(cum_xor[i])を取った場合の数を加えて更新
                dp[cum_xor[i]][1] += dp[cum_xor[i]][0]
                dp[cum_xor[i]][1] %= mod
                # 0の数の更新
                cnt_zero_prev_cumXOR_i[cum_xor[i]] = cnt_zero_now
        ans = 0
        for c in set(cum_xor):
            ans += dp[c][1]
            ans %= mod
        ans += 2 ** (cnt_zero_now - 1)
        print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import xor

# 入力
N = int(input())
A = list(map(int, input().split()))

MOD = 10**9 + 7

acc = list(accumulate(A, xor))
M = max(acc)
dp = [[0, 0, 0] for _ in range(M + 1)]
z = 0
for x in acc:
    if x == 0:
        z += 1
    else:
        dp[x][1] = (dp[x][1] + (z - dp[x][2]) * dp[x][0]) % MOD
        dp[x][0] = (dp[x][0] + dp[x][1] + 1) % MOD
        dp[x][2] = z
for x in range(1, M + 1):
    dp[x][1] = (dp[x][1] + (z - dp[x][2]) * dp[x][0]) % MOD
ans = (
    dp[acc[-1]][1] + 1 if acc[-1] != 0 else
    sum(dp[x][0] for x in range(1, M + 1)) + pow(2, acc.count(0) - 1, MOD)
) % MOD

# 出力
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B=[0]*N
mod=10**9+7
B[0]=A[0]
for i in range(1,N):
    B[i]=A[i]^B[i-1]
F=[0]*(1<<20)
dp=[1]*(1<<20)
dp1=[0]*(1<<20)
x=1
#print(B)
for i in range(N):
    if B[i]==0:
        x+=1
    dp[B[i]]+=dp1[B[i]]*(x-F[B[i]])
    dp[B[i]]%=mod
    dp1[B[i]]+=dp[B[i]]
    dp1[B[i]]%=mod
    F[B[i]]=x
    #print(dp[:16],dp1[:16])
#print(dp[:10],B,x)
if B[-1]!=0:
    print(dp[B[-1]])
else:
    ans=pow(2,x-2,mod)
    for i in range(1,1<<20):
        ans+=dp1[i]
        ans%=mod
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
mod=10**9+7
n=int(input())
A=tuple(map(int,input().split()))
Acc=[0]*n
for i,a in enumerate(A):
    if i==0:
        Acc[0]=a
    else:
        Acc[i]=Acc[i-1]^a

def solve(Acc):
    total_0=0
    dp_0=defaultdict(lambda: 1)
    dp_x=defaultdict(int)
    cnt_0=defaultdict(int)
    for a in Acc:
        if a:
            if a not in dp_x:
                dp_x[a]=1
                cnt_0[a]=total_0
            else:
                dp_0[a]=(dp_0[a]+dp_x[a]*(total_0-cnt_0[a]))%mod
                cnt_0[a]=total_0
                dp_x[a]=(dp_x[a]+dp_0[a])%mod
        else:
            total_0+=1
    if Acc[-1]:
        return dp_0[Acc[-1]]
    return (sum(dp_x.values())+pow(2,total_0-1,mod))%mod

print(solve(Acc))

Submission status: Accepted

Solution code:
def mod_pow(a: int, n: int, mod: int)->int:
    '''a の n 乗を計算します。
    '''
    res = 1
    while n > 0:
        if n & 1:
            res = (res * a) % mod
        a = (a * a) % mod
        n >>= 1
    return res


def xor_partitioning(N: int, A: list)->int:
    MOD = 10**9 + 7

    # dp[i][0] = i マス目まで処理した時に現在こまが置かれているますに 0 が書かれている
    # dp[i][1] = i マス目まで処理した時に現在こまが置かれているマスに X が書かれている。
    dp = [[0, 1] for _ in range(1 << 20)]
    memo = [0] * (1 << 20)

    b = 0
    num_zero = 0

    for a in A:
        b ^= a

        if b == 0:
            num_zero += 1
        else:
            dp[b][1] += dp[b][0] * (num_zero-memo[b])
            dp[b][1] %= MOD

            dp[b][0] += dp[b][1]
            dp[b][0] %= MOD

            memo[b] = num_zero

    if b > 0:
        return dp[b][1]

    return (sum(_dp[0] for _dp in dp) + mod_pow(2, num_zero-1, MOD)) % MOD


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]

    ans = xor_partitioning(N, A)
    print(ans)

Submission status: Accepted

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a % b
    return b

mod = 7 + 10 ** 9

def solve():
    N = int(single_input())
    A = [int(a) for a in line_input()]

    DP = [[0, 1] for i in range(2 ** 20)]
    memo = [0] * (2 ** 20)
    cumulative_xor = 0
    zeros = 0
    for i in range(N):
        cumulative_xor ^= A[i]
        if cumulative_xor == 0: zeros += 1  
        else:
            DP[cumulative_xor][1] += DP[cumulative_xor][0] * (zeros - memo[cumulative_xor])
            DP[cumulative_xor][1] %= mod
            DP[cumulative_xor][0] += DP[cumulative_xor][1]
            DP[cumulative_xor][0] %= mod
            memo[cumulative_xor] = zeros

    if cumulative_xor > 0: print(DP[cumulative_xor][1])
    else:
        ans = pow(2, zeros - 1, mod)
        for i in range(2**20): 
            ans += DP[i][0]
            ans %= mod
        print(ans)
        
    return 0
  
if __name__ == "__main__":
    solve()

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] = [1]*(m+1)
cnt = [0]*(m+1)
z = 0 #zero_count

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
    #print('i=',i,',bi=',b[i],',dp=',dp,'zero',z)


if b[N-1]:
    print(dp[0][b[N-1]])
else:
    ans = pow(2, z-1, mod) #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]
#print('累積論理和',b)
m = max(b)
dp = [[0]*(m+1) for j in range(2)]
dp[0] = [1]*(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)