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

Solution code:
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
const ll MAX_N=5e5,MOD=1e9+7;
typedef pair<ll,ll> P;
ll N,A[MAX_N+1],psm[MAX_N+2],dp[MAX_N+1][2];
map<ll,vector<P> > mp;
map<ll,ll> lst;
ll mpw(ll n,ll m){
    ll ret=1;
    while(m){
        if(m&1){
            ret*=n;
            ret%=MOD;
        }
        n*=n;
        n%=MOD;
        m>>=1;
    }
    return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
    ll ans=0;
	cin>>N;
    REP(i,N){
        cin>>A[i+1];
        A[i+1]^=A[i];
    }
    REP(i,N+1){
        psm[i+1]=psm[i];
        if(A[i]==0){
            psm[i+1]++;
        }
    }
    if(A[N]==0){
        REP(i,N){
            if(A[i]!=0){
                if(psm[i]-psm[lst[A[i]]]>0){
                    mp[A[i]].push_back(P(0,psm[i]-psm[lst[A[i]]]));
                    lst[A[i]]=i;
                }
                mp[A[i]].push_back(P(A[i],1));
            }
        }
        for(auto p:lst){
//            cout<<p.first<<' '<<p.second<<endl;
        }
        for(auto &i:mp){
            if(psm[N+1]-psm[lst[i.first]]>0){
                i.second.push_back(P(0,psm[N+1]-psm[lst[i.first]]));
            }
        }
        for(const auto &i:mp){
//            cout<<i.first<<' '<<i.second.size()<<endl;
            dp[0][0]=1;
            dp[0][1]=0;
            REP(j,i.second.size()){
                //cout<<"    "<<i.second[j].first<<','<<i.second[j].second<<endl;
            }
            FOR(j,1,i.second.size()){
                REP(k,2)dp[j][k]=dp[j-1][k];
                if(i.second[j].first==0){
                    dp[j][0]+=dp[j-1][1]*i.second[j].second;
                    dp[j][0]%=MOD;
                }else{
                    dp[j][1]+=dp[j-1][0]*i.second[j].second;
                    dp[j][1]%=MOD;
                }
            }
            ans+=dp[i.second.size()-2][1];
            ans%=MOD;
        }
//        cout<<psm[N+1]<<endl;
        ans+=mpw(2,psm[N+1]-2);
        ans%=MOD;
    }else{
        ll x=A[N];
        dp[0][0]=1;
        FOR(i,1,N+1){
            REP(j,2)dp[i][j]=dp[i-1][j];
            if(A[i]==0){
                dp[i][0]+=dp[i-1][1];
                dp[i][0]%=MOD;
            }else if (A[i]==x){
                dp[i][1]+=dp[i-1][0];
                dp[i][0]%=MOD;
            }
        }
        ans=dp[N-1][0];
    }
    cout<<ans<<endl;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

int N;
int A[514514];
int imos[514514];
LL B[1 << 20];
LL dp[1 << 20];
int precnt[1 << 20];
bool appeared[1 << 20];

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> N;
  reps(i, 1, N+1) {
    cin >> A[i];
    imos[i] = imos[i-1] ^ A[i];
  }

  //fill(B, B+(1<<20), 1);
  int cnt = 0;
  LL ans = 0;
  reps(i, 1, N) {
    int t = imos[i];
    if (t == 0) cnt++;
    else if (appeared[t]) {
      LL k = cnt - precnt[t];
      B[t] += k * dp[t];
      B[t] %= MOD;
      dp[t] += B[t];
      if (dp[t] >= MOD) dp[t] -= MOD;
      precnt[t] = cnt;
    } else {
      appeared[t] = 1;
      dp[t] = 1;
      B[t] = 1;
      precnt[t] = cnt;
    }
  }

  int t = imos[N];
  if (t == 0) {
    cnt++;
    rep(t, 1 << 20) {
      //LL k = cnt - precnt[t];
      //B[t] += k * dp[t];
      //B[t] %= MOD;
      ans += dp[t];
      //if (dp[t]) cout << t << ", " << dp[t] << endl;
      if (ans >= MOD) ans -= MOD;
      //if (appeared[t]) {
      //  ans += MOD - 1; //(1LL << ((cnt - 1) % (MOD-1))) % MOD;
      //  ans %= MOD;
      //}
      //  ans %= MOD;
      //}
    }
    if (cnt > 0) ans += 1LL << ((cnt - 1) % (MOD-1));
    ans %= MOD;
  } else {
    LL k = cnt - precnt[t];
    B[t] += k * dp[t];
    B[t] %= MOD;
    ans = B[t];
  }
  cout << ans << endl;
}

Submission status: Runtime Error

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(N + 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: Runtime Error

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)

    print(cum_xor)

    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(N + 1)]

        # cnt______[X]:美しさがXの選び方で、今まで出てきた0の数
        cnt_zero_prev_cumXOR_i = [0] * (1 << 20)
        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: Runtime Error

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

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

Solution code:
　N=input()

Submission status: Runtime Error

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

print(N-lis[0:N-1])

Submission status: Runtime Error

Solution code:
def cul(n):
    memo[1]=1
    memo[2]=1
    memo[3]=2
    if memo[n]==-1:
        t=1
        for i in range(1,N):
            t+=cul(N-i)
        memo[n]=t
    return memo[n]

import math
import sys
MOD=10**9+7

N=int(input())
memo=[-1]*(N+3)

tmp=0
l=[-1]
a=list(map(int,input().split()))
b=[]
x=[]
for i in range(N):
    tmp=tmp ^ a[i]
    x.append(tmp)
    if tmp==0:
        b.append([x[i] for i in range(len(x))])
        x=[]
if x!=[]: b.append([x[i] for i in range(len(x))])

M=tmp
if tmp!=0:
    tmp=0
    s=0
    for i in range(N):
        tmp=tmp^a[i]
        if tmp==M: s+=1
    print(cul(s))
    sys.exit()

Submission status: Runtime Error

Solution code:
def getInv(N):
    inv = [1] * (N + 1)
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

from collections import defaultdict
N = int( input())
A = list( map( int, input().split()))
Q = 10**9+7

F = [0]*(N+1)
for i in range(N):
    F[i+1] = F[i]^A[i]

ANS = defaultdict(lambda:1)
d = defaultdict( lambda :0)
h = defaultdict( int)
for f in F:
    if f == 0:
        for t in d:
            ANS[t] = (ANS[t] + ANS[t]*D[t])%Q
            h[t] += 1
        d = defaultdict( lambda :0)
    else:
        d[f] += 1
ans = 1


for a in ANS:
    ans += ANS[a]
    ans %= Q

if F[-1] == 0:
    cnt = 0
    for i in range(N+1):
        if F[i] == 0:
            cnt += 1
    modinv = getInv(cnt)
    fmodinv = [1]*(cnt+1)
    fmod = [1]*(cnt+1)

    for i in range(1,cnt+1):
        fmodinv[i] = (fmodinv[i-1]*modinv[i])%Q
        fmod[i] = (fmod[i-1]*i)%Q
    for i in range(1, cnt-1):
        ans += fmod[cnt-2]*fmodinv[i]%Q*fmodinv[cnt-2-i]%Q
        ans %= Q
        # print(fmod[cnt-2]*fmodinv[i]%Q*fmodinv[cnt-2-i]%Q)
        # print(ans)
print(ans)

Submission status: Runtime Error

Solution code:
def getInv(N):
    inv = [1] * (N + 1)
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

from collections import defaultdict
N = int( input())
A = list( map( int, input().split()))
Q = 10**9+7

F = [0]*(N+1)
for i in range(N):
    F[i+1] = F[i]^A[i]

ANS = defaultdict(lambda:1)
d = defaultdict( lambda :0)
h = defaultdict( int)
for f in F:
    if f == 0:
        for t in d:
            ANS[t] = (ANS[t] + ANS[t]*D[t])%Q
            h[t] += 1
        d = defaultdict( lambda :0)
    else:
        d[f] += 1
ans = 1
print(ANS)
for a in ANS:
    ans += ANS[a]
    ans %= Q

if F[-1] == 0:
    cnt = 0
    for i in range(N+1):
        if F[i] == 0:
            cnt += 1
    modinv = getInv(cnt)
    fmodinv = [1]*(cnt+1)
    fmod = [1]*(cnt+1)

    for i in range(1,cnt+1):
        fmodinv[i] = (fmodinv[i-1]*modinv[i])%Q
        fmod[i] = (fmod[i-1]*i)%Q
    for i in range(1, cnt-1):
        ans += fmod[cnt-2]*fmodinv[i]%Q*fmodinv[cnt-2-i]%Q
        ans %= Q
        # print(fmod[cnt-2]*fmodinv[i]%Q*fmodinv[cnt-2-i]%Q)
        # print(ans)
print(ans)

Submission status: Runtime Error

Solution code:
def xor(a, b):
  x = 0
  i = 1
  while a != 0 or b != 0:
    an = a % 2
    bn = b % 2
    if an != bn:
      x += i
    a //= 2
    b //= 2
    i *= 2
  return x

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

MOD = 1e9 + 7

L = [0] * N
L[0] = a[0]

Z = [0] * (N + 1)
Z[1] = 1
for i in range(1, N):
  Z[i + 1] = int(Z[i] * 2 % MOD)

for i in range(1, N):
  L[i] = xor(L[i - 1], a[i])

D = [0] * N
if L[0] == 0:
  D[0] = 1

for i in range(1, N):
  D[i] = D[i - 1]
  if L[i] == 0:
    D[i] += 1

if L[-1] == 0:
  Ans = Z[D[-1]]
  
  R = {}
  for i in range(N - 1):
    t = L[i]
    if t != 0:
      if t not in R:
        R[t] = [[1, i]]
      else:
        k = R[t][-1][1]
        if D[k] == D[i]:
          R[t][-1][0] += 1
        else:
          R[t].append([D[i] - D[k], -1])
          R[t].append([1, i])
  print(Ans)
  for i in R.values():
    t = i
    t.append([D[-1] - D[i[-1][1]] , -1])
    k = 1
    for j in range(0, len(t), 2):
      k *= t[j][0] * t[j + 1][0]
    Ans += k - 1
print(Ans)

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
    
def gcd(x,y):
    x,y=max(abs(x),abs(y)),min(abs(x),abs(y))
    if y==0:
        return x
    elif x%y==0:
        return y
    while x%y!=0:
        x,y=y,x%y
    return y

def bin_exp0(x):
    x_bin=[0]*n
    for i in range(n):
        x_bin[i]=int((x % 2**(i+1)) / 2**i)
    return x_bin

def bin_exp(x):
    b=bin(x)[2:]
    return '0'*(20-len(b))+b
    
import sys
from operator import itemgetter
from collections import deque
sys.setrecursionlimit(10*5)

n=int(input())
#a=[int(i) for i in input().split()]
a=[]
zeros=0
for i in input().split():
    k=int(i)
    if k==0:
        zeros+=1
    else:
        a.append(k)
ans=0

print(bin_exp(15),len(bin_exp(15)))

b=[]
for x in a:
    b.append(bin_exp(x))

f=[[0 for _ in range(20)] for i in range(n+1)]
for bit in range(20):
    for j in range(n):
        f[j+1][bit]=f[j][bit]+int(b[j][bit])

for m in range(1,n+1):
    flg=True
    for bit in range(20):
        if f[n][bit]%m!=0:
            flg=False
    if flg:
        #print('m=',m)
        pre=0
        for i in range(n): # loop1
            chk=True
            for bit2 in range(20):
                if f[i][bit2]-f[pre][bit2]!=f[n][bit]//m:
                    chk=False
            
            if chk:# all bit OK
                print('i=',i)
                pre=i
                ans+=1
            else:
                break # loop1
        


print(ans)

Submission status: Runtime Error

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

N = int(input())
A = list(map(int, input().split()))
s = 0
for a in A:
    s ^= a
#print(s)
comb = Combination(501010)
mod = 10**9 + 7
if s!=0:
    S = s
    s = 0
    an = 0
    for a in A:
        s ^= a
        if s==S:
            an += 1
            s = 0
    ans = 0
    for i in range(0, an, 2):
        ans += comb(an-1, i)
        ans %= mod
    print(ans)
else:
    assert False

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
B = [[0 for j in range(20)] for i in range(N + 1)]
D = defaultdict(list)
D[0].append(0)
for i in range(N):
  a = A[i]
  b = 0
  for j in range(20):
    B[i + 1][j] = B[i][j]
    B[i + 1][j] += a % 2
    B[i + 1][j] %= 2
    b += B[i + 1][j] * 2 ** j
    a //= 2
  D[b].append(i + 1)
cnt = 0
def zig(A, Z):
  As, Ar, Zs, Zr = 0, 0, 0, 0
  i, j = len(A) - 1, len(Z) - 1
  if A[-1] > Z[-1]:
    while A[i] > Z[-1]:
      i -= 1
    Zr = 1
  else:
    while Z[j] > A[-1]:
      j -= 1
    Ar = 1
  while i > 0 and j > 0:
    if Ar:
      j -= 1
      while A[i] > Z[j]:
        As +- Ar
        i -= 1
        if i == 0:
          break
      Zr = As % p
      As, Ar = 0, 0
    else:
      i -= 1
      while Z[j] > A[i]:
        Zs += Zr
        j -= 1
        if j == 0:
          break
      Ar = Zs % p
      Zs = 0
  return Zr
if b != 0:
  cnt += zig(D[b], D[0])
else:
  for k in D.keys():
    if k:
      cnt += zig(D[k], D[0]) + 1
    else:
      cnt += 2 ** (len(D[0]) - 2) % p
print(cnt % p)

Submission status: Runtime Error

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

bins = [0] * 20

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

for i in range(N):
    a = a_list[i]
    b = 0
    for k in range(20):
        r = (a // (2**k)) % 2
        bins[k] = (bins[k] + r) % 2
        b += bins[k]*(2**k)
    if b == 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][2] = (v_all_dict[v][2] + v_all_dict[v][1] * (zeros - z)) % LARGE
                v_all_dict[v][1] = (v_all_dict[v][1] + v_all_dict[v][2] * v_dict[zeros][v]) % LARGE
        zeros += 1
        v_dict[zeros] = dict()
    else:
        if b in v_dict[zeros].keys():
            v_dict[zeros][b] += 1
        else:
            v_dict[zeros][b] = 1

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from math import sqrt
def inpl(): return list(map(int, input().split()))

N = int(input())
A = inpl()
S = []
x = 0
for i in range(N):
    x ^= A[i]
    S.append(x)
if S[-1] != 0:
    print(2**(S.count(S[-1])-1))
else:
    raise

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import math, itertools, operator
from math import *
from math import factorial as fact
from itertools import permutations, combinations
from functools import reduce
from statistics import mean, median, median_low, median_high, mode
# Before Python 3.5
from fractions import gcd

import numpy as np
#import scipy, scipy.special
#from sympy import isprime, nextprime
#from sympy.ntheory import factorint
#from sympy import divisors

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(inp = input, sep = ' ', conv = int):
    return map(conv, inp().split(sep = sep))

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

N = int(input())
A = list(input_ints())

dp = np.empty((N))

def func(N, A, up_prod, i_start):
    if i_start == N:
        return 1
    if dp[i_start] >= 0:
        return dp[i_start]
    prod = 0
    cnt = 0
    for i in range(i_start, N):
        prod ^= A[i]
        if prod == up_prod:
            cnt += func(N, A, up_prod, i + 1)
    dp[i_start] = cnt
    return cnt

prod = 0
cnt = 0
for i in range(0, N):
    dp.fill(-1)
    prod ^= A[i]
    cnt += func(N, A, prod, i + 1)

print(int(cnt % (1e9+7)))