Problem p03051 (python)

Fixed submission:

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

Buggy submission (verdict: Runtime Error):

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