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:
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={}
    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
        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: Wrong Answer

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]
    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: Wrong Answer

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[1] % mod)

else:

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

    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: Wrong Answer

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:
    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: Wrong Answer

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:
    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]])+1)%mod
        dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
    ans = dp[-1]%mod
print(ans)

Submission status: Wrong Answer

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]])+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, k in enumerate(index[S[-1]][1:]):
        dp[j] = (dp_cum[j-1]*(cumsum[k]-cumsum[index[S[-1]][j-1]])+1)%mod
        dp_cum[j] = (dp_cum[j-1]+dp[j])%mod
    ans = dp[-1]%mod
print(ans)

Submission status: Wrong Answer

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)]
U = set()
z = 0
for x in acc:
    if x == 0:
        z += 1
        for u in U:
            dp[u][1] = (dp[u][1] + dp[u][0]) % MOD
        U = set()
    else:
        if dp[x][2] < z:
            dp[x][1] = ((z - dp[x][2]) * dp[x][1]) % MOD
            dp[x][2] = z
        dp[x][0] = (dp[x][0] + dp[x][1] + 1) % MOD
        U.add(x)
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: Wrong Answer

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)

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)

Submission status: Wrong Answer

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 += dp[1][i]
  print(ans)

Submission status: Wrong Answer

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]
    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()))
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: Wrong Answer

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(b)
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: Wrong Answer

Solution code:
def run_length_encoding(A: list)->list:
    '''A をランレングス圧縮します。
    '''
    res = []
    if len(A) == 0:
        return res

    pre = A[0]
    cnt = 0
    for a in A:
        if a == pre:
            cnt += 1
        else:
            res.append((pre, cnt))
            pre = a
            cnt = 1
    else:
        res.append((pre, cnt))

    return res


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

    B = [0] * (N+1)
    for n, a in enumerate(A):
        B[n+1] = a ^ B[n]

    if B[-1] == 0:
        X = set(B)
    else:
        X = set([B[-1]])

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

    for x in X:
        enc = run_length_encoding([b for b in B if b == 0 or b == x])
        dp[0] = [1, 0]

        for i, (b, v) in enumerate(enc):
            coeff = mod_pow(2, v-2, MOD)

            if b == 0 and x == 0:
                dp[i+1][0] = ((dp[i][0] + dp[i][1]) * coeff) % MOD
                dp[i+1][1] = ((dp[i][1] + dp[i][0]) * coeff) % MOD
            elif b == 0:
                dp[i+1][0] = (dp[i][0] + dp[i][1] * v) % MOD
                dp[i+1][1] = dp[i][1]
            elif b == x:
                dp[i+1][0] = dp[i][0]
                dp[i+1][1] = (dp[i][1] + dp[i][0] * v) % MOD
            else:
                dp[i+1][0] = dp[i][0]
                dp[i+1][1] = dp[i][1]

        res = (res + dp[len(enc)][0] - 1) % MOD

    return res


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

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

Submission status: Wrong Answer

Solution code:
def run_length_encoding(A: list)->list:
    res = []
    if len(A) == 0:
        return res

    pre = A[0]
    cnt = 0
    for a in A:
        if a == pre:
            cnt += 1
        else:
            res.append((pre, cnt))
            pre = a
            cnt = 1
    else:
        res.append((pre, cnt))

    return res


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

    B = [0] * (N+1)
    for n, a in enumerate(A):
        B[n+1] = a ^ B[n]

    if B[-1] == 0:
        X = set(B)
    else:
        X = set([B[-1]])

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

    for x in X:
        dp[0] = [1, 0]

        for i in range(N):
            b = B[i+1]

            if b == 0:
                dp[i+1][0] = (dp[i][0] + dp[i][1]) % MOD
            else:
                dp[i+1][0] = dp[i][0]

            if b == x:
                dp[i+1][1] = (dp[i][1] + dp[i][0]) % MOD
            else:
                dp[i+1][1] = dp[i][1]

        res = (res + dp[N][0] - 1) % MOD

    return res


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

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

Submission status: Wrong Answer

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))

Submission status: Wrong Answer

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
print("")

Submission status: Wrong Answer

Solution code:
N=int(input())
def makebin(i):
    S=bin(i)[2:]
    return '0'*(20-len(S))+S
def XOR(a,b):
    res=''
    for i in range(20):
        if a[i]==b[i]:
            res+='0'
        else:
            res+='1'
    return res
mod=10**9+7
X=[-1]*N
Xstr=[""]*N
for i,a in enumerate(map(makebin,map(int,input().split()))):
    if i==0:
        Xstr[0]=a
    else:
        Xstr[i]=XOR(Xstr[i-1],a)
    X[i]=int(Xstr[i],2)
print("")

Submission status: Wrong Answer

Solution code:
N=int(input())
def makebin(i):
    S=bin(i)[2:]
    return '0'*(20-len(S))+S
def XOR(a,b):
    res=''
    for i in range(20):
        if a[i]==b[i]:
            res+='0'
        else:
            res+='1'
    return res
mod=10**9+7
X=[-1]*N
Xstr=[""]*N
for i,a in enumerate(map(makebin,map(int,input().split()))):
    if i==0:
        Xstr[0]=a
    else:
        Xstr[i]=XOR(Xstr[i-1],a)
    X[i]=int(Xstr[i],2)
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))

Submission status: Wrong Answer

Solution code:
N=int(input())
def makebin(i):
    S=bin(i)[2:]
    return '0'*(20-len(S))+S
def XOR(a,b):
    a=makebin(a)
    b=makebin(b)
    res=''
    for i in range(20):
        if a[i]==b[i]:
            res+='0'
        else:
            res+='1'
    return int(res,2)
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]=XOR(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))

Submission status: Wrong Answer

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 = {}
    # print(acc)
    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
        # print(f'a:{a}  cnt:{dict(counts)}  last0:{dict(last_0)}')
    # print(dict(counts))
    ans = pow(2, cnt_0 - 1, MOD)
    for i, cnt in counts.items():
        c1 = cnt[0]
        ans = (ans + c1) % MOD
        if len(cnt) > 2:
            loc = {c1: 0}
            for c0, c1 in zip(cnt[1::2], cnt[2::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)

    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()))
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: 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)
    last_0 = defaultdict(lambda: 0)
    # print(acc)
    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
        # print(f'a:{a}  cnt:{dict(counts)}  last0:{dict(last_0)}')
    # print(dict(counts))
    ans = pow(2, cnt_0 - 1, MOD)
    for i, cnt in counts.items():
        c1 = cnt[0]
        ans = (ans + c1) % MOD
        if len(cnt) > 2:
            loc = {c1: 0}
            for c0, c1 in zip(cnt[1::2], cnt[2::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)

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

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][1]

print(res)

Submission status: Wrong Answer

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))

Submission status: Wrong Answer

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

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:
    res = 1
print(res)

Submission status: Wrong Answer

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
    
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:
    print(1)

Submission status: Wrong Answer

Solution code:
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])

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

    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])%(10**9+7)
                tmp_x %= 10**9+7
            else:
                tmp_0 += (tmp_x * dic[d][i])%(10**9+7)
                tmp_0 %= 10**9+7

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

    print(ans)

Submission status: Wrong Answer

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

bins = [0] * 20
b_list = [0] * N

b = 0

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

print(1)

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()

b = 0

for i in range(N):
    
    a = a_list[i]
    b = a ^ b
    
    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
b_list = [0] * N


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)
    b_list[i] = b
    
print(1)

Submission status: Wrong Answer

Solution code:
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])

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

    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

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

    print(ans)