Problem:


Score : 700 points

Problem Statement

Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2, or 3.
Let x_{i,j} defined as follows:

x_{1,j} := a_j \quad (1 \leq j \leq N)

x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)

Find x_{N,1}.

Constraints

2 \leq N \leq 10^6

a_i = 1,2,3 (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
a_1a_2\ldotsa_N

Output

Print x_{N,1}.

Sample Input 1

4
1231

Sample Output 1

1

x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1.

x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2.

x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1.

Finally, x_{4,1} = |0-1| = 1, so the answer is 1.

Sample Input 2

10
2311312312

Sample Output 2

0



Sample input:
4
1231


Sample output:
1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int1,input()))
    X=0
    c=0
    for i in range(N):
        if c==0:
            X^=a[i]%2
        K=N-1-i
        while K>0 and K%2==0:
            c+=1
            K//=2
        K=i
        while K>0 and K%2==0:
            c-=1
            K//=2
    if X==1:
        print(1)
    else:
        if 1 in a:
            print(0)
        else:
            print(2)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int1,input()))
    X=0
    c=0
    for i in range(N):
        if c==0:
            X^=a[i]
        K=N-1-i
        while K>0 and K%2==0:
            c+=1
            K//=2
        K=i+1
        while K>0 and K%2==0:
            c-=1
            K//=2
    X&=0b01
    if X==1:
        print(1)
    else:
        if 1 in a:
            print(0)
        else:
            print(2)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int1,input()))
    X=0
    c=1
    for i in range(N):
        if c%2:
            X^=a[i]
        c*=N-1-i
        c//=i+1
    X&=0b01
    if X==1:
        print(1)
    else:
        if 1 in a:
            print(0)
        else:
            print(2)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int1,input()))
    
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(N,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    X=0
    for i in range(N):
        if COM(N-1,i)%2:
            X^=a[i]
    X&=0b01
    if X==1:
        print(1)
    else:
        if 1 in a:
            print(0)
        else:
            print(2)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
  N = raw_input()
  seq = str(raw_input())
  tri = [int(i) for i in seq]
 
  for idx in range(len(seq)-1):
    curr = []
    for i in range(len(seq)-idx-1):
      curr.append(abs(tri[i] - tri[i+1]))
    tri = curr
 
  return tri[-1]
 
main()

Submission status: Wrong Answer

Solution code:

n=int(input())
s=input()
arr=[int(i) for i in list(s)]

if n<4:
    index=1
    while index<n:
        for i in range(n-index):
            arr[i]=abs(arr[i]-arr[i+1])
        index+=1    

    print(arr[0])
else:
    print(abs(abs(arr[0]-arr[1])-abs(arr[n-2]-arr[n-1])))

Submission status: Wrong Answer

Solution code:
#editorial参照

#偶奇
import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)-1
div2=[1]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
for i in range(n-1):
    p=int(((n-1)&i)==i)###nCkの偶奇らしいが、これどこから来たんだ？
    div2.append(p)
div2=np.array(div2)
print(div2)
tmp= (a*div2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
#editorial参照

#偶奇
import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)-1
div2=[0]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
tst=1
tsts=[1]
for i in range(n-1):
    p=int(((n-1)&i)==i)###nCkの偶奇らしいが、これどこから来たんだ？
    div2.append(p)
div2=np.array(div2)
tmp= (a*div2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
#editorial参照

#偶奇
import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)-1
div2=[0]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
tst=1
tsts=[1]
for i in range(n-1):
    p=int(((n-1)&i)==i)###nCkの偶奇らしいが、これどこから来たんだ？
    div2.append(p)
div2=np.array(div2)###これは2で割れる数のカウント
dv2=1-(div2>0)##これが2で割れるか否か
tmp= (a*dv2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
#editorial参照

#偶奇
import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)
div2=[0]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
tst=1
tsts=[1]
for i in range(n-1):
    cnt += bin(n-i-1)[::-1].find('1')
    cnt -= bin(i+1)[::-1].find('1')
    #tst*=n-i-1
    #tst//=i+1
    div2.append(cnt)
    tsts.append(tst)

div2=np.array(div2)###これは2で割れる数のカウント
dv2=1-(div2>0)##これが2で割れるか否か
#print(a)
#print(tsts)
#print(dv2)
tmp= (a*dv2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
#editorial参照

#偶奇
import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)
div2=[0]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
tst=1
tsts=[1]
for i in range(n-1):
    cnt += bin(n-i-1)[::-1].find('1')
    cnt -= bin(i+1)[::-1].find('1')
    div2.append(cnt)

div2=np.array(div2)###これは2で割れる数のカウント
dv2=1-(div2>0)##これが2で割れるか否か
tmp= (a*dv2%2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
#editorial参照

#偶奇
import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)
div2=[0]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
tst=1
tsts=[1]
for i in range(n-1):
    cnt += bin(n-i-1)[::-1].find('1')
    cnt -= bin(i+1)[::-1].find('1')
    tst*=n-i-1
    tst//=i+1
    div2.append(cnt)
    tsts.append(tst)

div2=np.array(div2)###これは2で割れる数のカウント
dv2=1-(div2>0)##これが2で割れるか否か
tmp= (a*dv2%2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
#editorial参照

#偶奇
import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)
div2=[]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
for i in range(n):
    cnt += bin(n-i-1)[::-1].find('1')
    cnt -= bin(i+1)[::-1].find('1')
    div2.append(cnt)

div2=np.array(div2)
#print(a)
#print(div2)
tmp= (a*div2%2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(lambda x:int(x)-1,input()))
if a.count(1) == 0:
    print(2)
    exit()
ans = 0
for i in range(n):
    if (n-1) & i == i:
        ans += a[i]
if ans % 2 == 1:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(lambda x:int(x)-1,input()))
if a.count(1) == 0:
    print(2)
    exit()
ans = 0
for i in range(n):
    if n & i == i:
        ans += a[i]
if ans % 2 == 1:
    print(0)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
"""
NTC here
"""
 

#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def iin(): return int(input())
 
 
def lin(): return list(map(int, input().split()))

def main():
    from math import factorial
    def ncr(n, r):
        return factorial(n)//(factorial(n-r)*factorial(r))
    T = 1
    while T:
        T-=1
        n = iin()
        a = list(map(int, list(input())))
        while n>1:
            a = [abs(a[i]-a[i-1]) for i in range(1, n)]
            n-=1
            i = 0
            a = [i for i in a if i]
            n = len(a)
            # print(a)
        if a:
            print(a[0])
        else:
            print(0)





# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(lambda x: int(x)-1, list(input())))
    b = [i % 2 for i in a]

    def all_a(x):
        ans = 0
        for j, i in enumerate(x):
            ans ^= (n-1 | j == n-1)*i
        return ans

    all_b = all_a(b)
    if all_b == 1:
        print(1)
        return
    if 1 in a:
        print(0)
        return
    b = [i//2 for i in a]
    return all_a(b)*2


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = input()
    if n > 3000:return None

    def brutal(n, a):
        a = list(map(int, list(a)))
        for i in range(n-1):
            b = []
            for i in range(n-i-1):
                b.append(abs(a[i]-a[i+1]))
            a = b
        return b[0]

    print(brutal(n, a))


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(lambda x: int(x)-1, list(input())))
    b = [i % 2 for i in a]

    def lucas(a, b):
        a = bin(a)[2:]
        b = bin(b)[2:]
        a, b = "0"*len(b)+a, "0"*len(a)+b
        for i, j in zip(a, b):
            if i == "0" and j == "1":
                return 0
        return 1

    def all_a(x):
        ans = 0
        for j, i in enumerate(x):
            ans ^= lucas(n-1, j)*i
        return ans

    all_b = all_a(b)
    if all_b == 1:
        print(1)
        return
    if 1 in a:
        print(0)
        return
    b = [i//2 for i in a]
    return all_a(b)*2


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
import numpy as np

def change_base(n, base=2):
    val = []
    tmp = n
    while True:
        val = [tmp%2] + val
        tmp = tmp // 2
        if tmp == 0:
            break
    return val

n_val = np.array(change_base(N-1, 2))

def lucas(m, mod=2):
    #n_val = change_base(n, mod)
    m_val = change_base(m, mod)
    m_val = [0] * (len(n_val)-len(m_val)) + m_val
    m_val = np.array(m_val)
    ret = 1
    if np.all(n_val > m_val):
      return 1
    else:
      return 0

def comb_for_bit(n,m):
    if n<m:
        return 0
    else:
        return 1

def check(seq):
  check = 0
  for k, val in enumerate(seq):
    if val == 1:
      check += lucas(k)
  return check % 2

A = [int(i)-1 for i in list(input())]

if __name__ == '__main__':
  if 1 in A:
    A = [i % 2 for i in A]
    ret = check(A)

  else:
    A = [i // 2 for i in A]
    ret = check(A)
    if ret == 1:
      ret = 2
  print(ret)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = list(map(int,input()))
B = []

for i in range(N):
  if N-1 == (i|N-1-i):
    B.append(1)
  else:
    B.append(0)
b = 0
for i in range(N):
  b += B[i]*A[i]
if b % 2 == 1:
  print(1)
else:
  for i in range(N):
    if A[i] == 2:
      print(0)
      break
  else:
    c = 0
    for i in range(N):
      A[i] = (A[1]-1)//2
      c += B[i]*A[i]
    if c % 2 == 1:
      print(2)
    else:
      print(0)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N = int(input())
a = list(map(int, list(input())))
x = [np.array(a)]

for i in range(1,N-2):
  tmp = np.abs(x[i-1][:N-1-i] - x[i-1][1:N-i])
  x.append(tmp)

print(x[-1][0])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N = int(input())
a = list(map(int, list(input())))
x = [np.array(a)]

for i in range(1,N-2):
  tmp = np.abs(x[i-1][:N-1-i] - x[i-1][1:N-i])
  x.append(tmp)

print(x)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(input())
arr=[int(arr[i]) for i in range(n)]
if n==1:
  print(arr[0])
if n==2:
  print(abs(arr[0]-arr[1]))
else:
  tmp=[]
  for i in range(n-2):
    tmp.append(abs(abs(arr[i]-arr[i+1])-abs(arr[i+1]-arr[i+2])))
  arr=tmp
  while len(arr)>3:
    tmp=[]
    for i in range(len(arr)//2):
      tmp.append(abs(arr[2*i]-arr[2*i+1]))
    arr=tmp
  if len(arr)==1:
    print(arr[0])
  elif len(arr)==2:
    print(abs(arr[0]-arr[1]))
  elif len(arr)==3:
    print(abs(abs(arr[0]-arr[1])-abs(arr[1]-arr[2])))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def lucas(n, k):
    return (n&k) == k

N = INT()
A = [a-1 for a in list(map(int, input()))]

def check(A):
    mod2 = 0
    for i, a in enumerate(A):
        if a == 1:
            mod2 += lucas(N-1, i)
            mod2 %= 2
    return mod2

res = check(A)
if res == 1:
    print(1)
    exit()

A = [a&1 for a in A]
res = check(A)
if res == 1:
    print(2)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input()) - 1
two = False
S = 0
for i, a in zip(range(N+1), sys.stdin):
  a = int(a)
  if not two:
    two = a == 2
  if i & N == i:
    S ^= a-1

if two:
  S &= ~2

print(S)

Submission status: Wrong Answer

Solution code:
N = int(input()) - 1
two = False
S = 0
for i, a in enumerate(input()):
  a = int(a)
  if i & N == i:
    S ^= a-1
    two |= (a == 2)

if two:
  S &= ~2

print(S)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input()) - 1
two = False
S = 0
for i in range(N+1):
  a = int(sys.stdin.read(1))
  if i & N == i:
    S ^= a-1
    two |= (a == 2)

if S & 1:
  print(1)
elif two:
  print(0)
else:
  print(S & 2)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input()) - 1
two = False
S = 0
for i in range(N+1):
  a = int(sys.stdin.read(1))
  if i & N == i:
    S ^= a-1
    two |= (a == 2)

if two:
  S &= ~2

print(S)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = [(aa-1)%2 for aa in map(int,input()) ]


def lucas2(n,r):
    n_bi = bin(n)[2:]
    r_bi = bin(r)[2:].zfill(len(n_bi))
    
    ans=1
    for bn,br in zip(n_bi,r_bi):
        if bn=="0" and br=="1":
            ans=0
            break
    return ans

f = sum((a[i]*lucas2(n-1,i))%2 for i in range(n))%2
if f==1:
    ans=1
elif 2 in a:
    ans=0
else:
    f = sum((a[i]//2*lucas2(n-1,i))%2 for i in range(n))%2
    if f==1:
        ans=2
    else:
        ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
al = list(input())

al = [int(a) - 1 for a in al]
flag = False
if 1 not in al:
    flag = True
    al = [a // 2 for a in al]
else:
    al = [a if a != 2 else 0 for a in al]

countl = [0]
a = 0
for i in range(1, n+1):
    if i % 2 == 0:
        a += 1
    countl.append(a)

def comb(a,b):
    if countl[a] - countl[a-b] - countl[b] > 0:
        return 0
    else:
        return 1

ans = 0
for idx, a in enumerate(al):
    if a == 1:
        ans += comb(n-1, idx)

if ans % 2 == 0:
    print(0)
else:
    if flag:
        print(2)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = [a for a in map(int,input()) ]
a2 = [(aa-1)%2 for aa in a]


def lucas2(n,r):
    n_bi = bin(n)[2:]
    r_bi = bin(r)[2:].zfill(len(n_bi))
    
    ans=1
    for bn,br in zip(n_bi,r_bi):
        if bn=="0" and br=="1":
            ans=0
            break
    return ans
  
  
f = sum((a2[i]*lucas2(n-1,i))%2for i in range(n))%2
if f==1:
    ans=1
elif 2 in a:
    ans=0
else:
    ans=2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
al = list(input())

al = [int(a) - 1 for a in al]
flag = False
if 1 not in al:
    flag = True
    al = [a // 2 for a in al]
else:
    al = [a if a != 2 else 0 for a in al]

MOD = 10**9+7
N = 10**6 + 1

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

ans = 0
for idx, a in enumerate(al):
    if a == 1:
        ans += comb(n-1, idx)
        ans %= 2

if ans % 2 == 0:
    print(0)
else:
    if flag:
        print(2)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(input())
l = []
for i in range(n-1):
    l.append(abs(int(a[i])-int(a[i+1])))

count = [0]
for i in range(2,n+1):
    c = bin(i)[::-1].index("1")
    count.append(count[-1]+c)


ki = 0
for i in range(n-1):
    if count[n-2] <= count[i]+count[n-2-i]:
        ki += 1
if ki % 2 == 1:
    print(1)
    exit()
else:
    if 1 in l:
        print(0)
        exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
b = input()
two = True
if "2" in b:
	two = False
ans = 0
a = ""
for i in range(n):
	if b[i] != "1":
		ans ^= ((n-1) == ( i | (n-1 - i)))
if ans:
	if two:
		print(2)
	else:
		print(1)
else:
	print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
b = input()
two = False
if "2" in b:
	two = True
ans = 0
a = ""
for i in range(n):
	if b[i] != "1":
		ans ^= ((n-1) == ( i | (n-1 - i)))
if ans:
	if not two:
		print(2)
	else:
		print(1)
else:
	print(1)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[int(s)-1for s in input()]
y=0
z=x[0]%2
for i in range(1,n):
  k=[n-i,i]
  for j in [0,1]:
    while k[j]%2<1:
      k[j]//=2
      y+=1-2*j
  z^=(y<1)*(x[i]%2)
print(z+2-2*(1in x))

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[int(s)-1for s in input()]
y=1
z=x[0]%2
for i in range(1,n):
  y=y*(n-i)//i
  z+=y*(x[i]%2)
print((z%2>0)+2-2*(1in x))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input()
if "2" not in a:
	if "3" not in a:
		print(0)
	else:
		l, r = 0, 0
		while a[l] != "3":
			l += 1
		while a[n-1-r] != "3":
			r += 1
		if l&1 != r&1:
			print(2)
		else:
			print(0)
else:
	b = ""
	for i in range(n):
		if a[i] == "3":
			b += "1"
		else:
			b += a[i]
	if "2" not in b:
		print(0)
	else:
		l, r = 0, 0
		while b[l] != "2":
			l += 1
		while b[n-1-r] != "2":
			r += 1
		if l&1 != r&1:
			print(1)
		else:
			print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [ int(s) - 1 for s in input()]

# r! に含まれる 2 の数
twos = {}
twos[0] = 0
for r in range(1, N):

    count = 0
    tmp = r
    while tmp % 2 != 0:
        tmp //= 2
        count += 1
    
    twos[r] = twos[r-1] + count

# {N-1}_C_r の偶数奇数判定
ncr = {}
for r in range(N):
    if twos[N-1] - twos[N-1-r] - twos[r] > 0:
        ncr[r] = 0
    else:
        ncr[r] = 1

# 答えの判定
oe = 0
for r, ai in enumerate(a):
    oe = (oe + ncr[r] * ai) % 2

if oe == 1:
    print(1)
else:
    if 1 in a:
        print(0)
    else:
        oe2 = 0
        for r, ai in enumerate(a):
            oe2 = (oe2 +ncr[r] * ai // 2 ) %2
        if oe2 == 1:
            print(2)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [ int(s) - 1 for s in input()]

# r! に含まれる 2 の数
twos = {}
twos[0] = 0
for r in range(1, N):

    count = 0
    tmp = r
    while tmp % 2 != 0:
        tmp //= 2
        count += 1
    
    twos[r] = twos[r-1] + count

# {N-1}_C_r の偶数奇数判定
ncr = {}
for r in range(N):
    if twos[N-1] - twos[N-1-r] - twos[r] > 0:
        ncr[r] = 0
    else:
        ncr[r] = 1

# 答えの判定
oe = 0
for r, ai in enumerate(a):
    oe = (oe + ncr[r] * ai) % 2

if oe == 1:
    print(1)
else:
    if 1 in a:
        print(0)
    else:
        print(2)

Submission status: Wrong Answer

Solution code:
def popcount_parity(x):
    x ^= x >> 1
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    x ^= x >> 32
    x ^= x >> 64
    x ^= x >> 128
    x ^= x >> 256
    x ^= x >> 512
    x ^= x >> 1024
    x ^= x >> 2048
    x ^= x >> 4096
    x ^= x >> 8192
    x ^= x >> 16384
    x ^= x >> 32768
    return x & 1

N = int(input()) - 1
s = 1
while N:
    l = N & -N
    s *= 1 + (1 << l)
    N ^= l

A = input()
if "2" in A:
    a = int(A.replace("1", "0").replace("3", "0").replace("2", "1"), 2)
    print(popcount_parity(a & s))
else:
    a = int(A.replace("1", "0").replace("3", "1"), 2)
    print(popcount_parity(a & s) * 2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 22 13:54:24 2020

@author: naoki
"""
import sys
#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(input())
a = list(map(lambda x:int(x)-1,list(input())))
   
all_odd = 0
kai = [0] * N

if (0 not in a) and (1 not in a):
    print(0)
    sys.exit()
if (1 not in a) and (2 not in a):
    print(0)
    sys.exit()
if (0 not in a) and (2 not in a):
    print(0)
    sys.exit()
    
for k in range(1,N):
    count = 0
    p = k
    for _ in range(N):
        if p % 2 == 1:
            kai[k] = kai[k-1] + count
            break
        p = p/2
        count += 1

all_num = 0
for k in range(N):
    if kai[-1] <= kai[k] + kai[N-1-k] and a[k] == 1:
        all_num += 1

if all_num % 2 == 1:
    print(1)
elif 1 in a:
    print(0)
else:
    print(2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 22 13:54:24 2020

@author: naoki
"""
import sys
#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(input())
a = list(map(lambda x:int(x)-1,list(input())))

if N < 10:
    for i in range(N-1):
        for j in range(N-1):
            a[j] = abs(a[j+1] - a[j])
    print(a[0])
    sys.exit()
    
all_odd = 0
kai = [0] * N

if 0 not in a and 1 not in a:
    print(0)
    sys.exit()
if 1 not in a and 2 not in a:
    print(0)
    sys.exit()
if 0 not in a and 2 not in a:
    print(0)
    sys.exit()
    
for k in range(1,N):
    count = 0
    p = k
    for _ in range(N):
        if p % 2 == 1:
            kai[k] = kai[k-1] + count
            break
        p = p/2
        count += 1

all_num = 0
for k in range(N):
    if kai[-1] == kai[k] + kai[N-1-k] and a[k] == 1:
        all_num += 1

if all_num % 2 == 1:
    print(1)
elif 1 in a:
    print(0)
else:
    print(2)

Submission status: Wrong Answer

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

fact2 = [0] * 1000011
def cnt2(n):
    if n%2 == 1:
        return 0
    else:
        fact2[n] = 1 + fact2[n//2]
        return fact2[n]

factorial = [0,0]
for i in range(2,1000010):
    factorial.append(factorial[-1] + cnt2(i))

def nck(n,k):
    return factorial[n] - factorial[k] - factorial[n - k]

def nxor(x,n):
    if n > 0:
        return 0
    else:
        return x

def main():
    n = int(input())
    a = [int(i) - 1 for i in list(input())]
    
    cumxor = 0
    amod = [i%2 for i in a]
    for i in range(n):
        cumxor ^= nxor(amod[i],nck(n - 1,i))
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

def cnt2(n,factorial):
    if n%2 == 1:
        return 0
    else:
        return 1 + factorial[n//2]

factorial = [0,0]
for i in range(2,1000010):
    factorial.append(factorial[-1] + cnt2(i,factorial))

def nck(n,k):
    return factorial[n] - factorial[k] - factorial[n - k]

def nxor(x,n):
    if n > 0:
        return 0
    else:
        return x

def main():
    n = int(input())
    a = [int(i) - 1 for i in list(input())]
    
    cumxor = 0
    amod = [i%2 for i in a]
    for i in range(n):
        cumxor ^= nxor(amod[i],nck(n - 1,i))
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 22 13:54:24 2020

@author: naoki
"""
import sys
#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(input())
a = list(map(lambda x:int(x)-1,list(input())))

all_odd = 0
kai = [0] * N

if 0 not in a and 1 not in a:
    print(0)
    sys.exit()
if 1 not in a and 2 not in a:
    print(0)
    sys.exit()
if 0 not in a and 2 not in a:
    print(0)
    sys.exit()
for k in range(2,N):
    count = 0
    p = k
    for _ in range(N):
        if p % 2 == 1:
            kai[k] = kai[k-1] + count
            break
        p = p/2
        count += 1

all_num = 0
for k in range(N):
    if kai[-1] == kai[k] + kai[N-k-1] and a[k] == 1:
        all_num += 1

if all_num % 2 ==1:
    print(1)
elif 1 in a:
    print(0)
else:
    print(2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 22 13:54:24 2020

@author: naoki
"""
#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(input())
a = list(map(lambda x:int(x)-1,list(input())))

all_odd = 0
kai = [0] * N

for k in range(2,N):
    count = 0
    p = k
    for _ in range(N):
        if p % 2 == 1:
            kai[k] = kai[k-1] + count
            break
        p = p/2
        count += 1

all_num = 0
for k in range(N):
    if kai[-1] == kai[k] + kai[N-k-1] and a[k] == 1:
        all_num += 1

if all_num % 2 ==1:
    print(1)
elif 1 in a:
    print(0)
else:
    print(2)

Submission status: Wrong Answer

Solution code:
n = int(input())
string = input()
a = []
a_01 = []
a_02 = []
bit_1 = 0
for i in range(n):
    a.append(int(string[i])-1)
    a_01.append((int(string[i])-1)%2)
    a_02.append((int(string[i])-1)//2)
    if int(string[i])-1 == 1: bit_1 = 1

### nCrを求めるパート
num_lst = [0 for i in range(n)]
for i in range(1, n):
    p = i
    cnt = 0
    while p % 2 == 0:
        p = p / 2
        cnt += 1
    num_lst[i] = cnt
nCr = [0 for i in range(n)]
for i in range(1, n):
    nCr[i] = nCr[i-1] + num_lst[n-i-1] - num_lst[i-1]
### nCrを求めるパートここまで

# まずは答えが1かどうか判定
cnt_01 = [0, 0]
for i in range(n):
    cnt_01[a_01[i]] = 0 if nCr[i] == 0 else 1
if cnt_01[1] % 2 == 1:
    print(1)
    exit()

# 答えが1でない時、配列に1が含まれるなら答えは0
if bit_1 == 1:
    print(0)
    exit()

# 配列が0と2で構成されている時
cnt_02 = [0, 0]
for i in range(n):
    cnt_02[a_02[i]] = 0 if nCr[i] == 0 else 1
if cnt_02[1] % 2 == 1:
    print(2)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
string = input()
a = []
a_01 = []
a_02 = []
bit_1 = 0
for i in range(n):
    a.append(int(string[i])-1)
    a_01.append((int(string[i])-1)%2)
    a_02.append((int(string[i])-1)//2)
    if int(string[i])-1 == 1: bit_1 = 1

### nCrを求めるパート
num_lst = [0 for i in range(n)]
for i in range(1, n):
    p = i
    cnt = 0
    while p % 2 == 0:
        p = p / 2
        cnt += 1
    num_lst[i] = cnt
nCr = [0 for i in range(n)]
for i in range(1, n):
    nCr[i] = nCr[i-1] + num_lst[n-i-1] - num_lst[i-1]
### nCrを求めるパートここまで

# まずは答えが1かどうか判定
cnt_01 = [0, 0]
for i in range(n):
    cnt_01[a_01[i]] = nCr[i]
if cnt_01[1] % 2 == 1:
    print(1)
    exit()

# 答えが1でない時、配列に1が含まれるなら答えは0
if bit_1 == 1:
    print(0)
    exit()

# 配列が0と2で構成されている時
cnt_02 = [0, 0]
for i in range(n):
    cnt_02[a_02[i]] = nCr[i]
if cnt_02[1] % 2 == 1:
    print(2)
else:
    print(0)