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

Solution code:
def popcount_parity(x, a):
    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
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    x ^= x >> 1048576
    return x & a

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

A = input()
if "2" in A:
    a = ~int(A, 4)
    print(popcount_parity(a & s, 1))
else:
    a = int(A, 4)
    print(popcount_parity(a & (s << 1), 2))

Submission status: Accepted

Solution code:
n = int(input())
l = [int(s)-1 for s in input()] 

if 1 in l:
    s = 0
    for i,a in enumerate(l):
        s += a*(n-1 == (i|(n-1-i)))
    print(s%2)
else:
    l = [i//2 for i in l]
    s = 0
    for i,a in enumerate(l):
        s += a*(n-1 == (i|(n-1-i)))
    print(s%2*2)

Submission status: Accepted

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
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    return x & 1

N = int(input()) - 1
s = 1
while N:
    l = N & -N
    s |= s << 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: Accepted

Solution code:
N=int(input())
a=[int(i)-1 for i in list(input())]
def solve(seq):
    if {0}==set(seq):
        return 0
    res=0
    for k in range(N):
        tmp=0
        if ((N-1)&k)==k:
            tmp=1
        #print(tmp)
        res+=tmp*seq[k]
        res%=2
    #print("#"*30)
    if res%2==1:
        return 1
    if 1 in set(seq):
        return 0
    seq2=[seq[i]//2 for i in range(N)]
    return solve(seq2)*2
print(solve(a))

Submission status: Accepted

Solution code:
n = int(input())
a = input()

if "2" in a:
	ans = 0
	for i in range(n):
		if a[i] == "2":
			ans ^= ((n-1) == ( i | (n-1 - i)))
	if ans:
		print(1)
	else:
		print(0)

else:
	ans = 0
	for i in range(n):
		if a[i] == "3":
			ans ^= ((n-1) == ( i | (n-1 - i)))
	if ans:
		print(2)
	else:
		print(0)

Submission status: Accepted

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

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
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    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: Accepted

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:
    for i in range(N):
        a[i] = a[i]/2
    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(2)
    else:
        print(0)

Submission status: Accepted

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


def nxor(x,n,k):
    if (n&k) == k:
        return x
    else:
        return 0


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],n - 1,i)
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            cumxor = 0
            adiv = [i//2 for i in a]
            for i in range(n):
                cumxor ^= nxor(adiv[i],n - 1,i)
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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:
            cumxor = 0
            adiv = [i//2 for i in a]
            for i in range(n):
                cumxor ^= nxor(adiv[i],nck(n - 1,i))
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[int(t)-1 for t in input()]
f=1
if 1 not in a:
	a=[x//2 for x in a]
	f=2
s=sum([x for i,x in enumerate(a) if (n-1)&i==i])
print(s%2*f)


"""
メモ
初めに各要素から1を差し引いても同じ
数列に1が存在する⇒答えは2になり得ない
⇒答えの偶奇を判定できればいい⇒各要素の寄与分を考える
「nCrの偶奇 == (n&r==r)」 の関係（Lucasの定理から導かれる）が利用できる！
数列が0,2のみの場合は2を1に読み替えて同様
参考： https://mathtrain.jp/lucastheorem
"""

Submission status: Accepted

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

### n-1Ciの偶奇を求めるパート
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
n_1Ci = [0 for i in range(n)]
for i in range(1, n):
    n_1Ci[i] = n_1Ci[i-1] + num_lst[n-i] - num_lst[i]
### n-1Ciの偶奇を求めるパートここまで

# まずは答えが1かどうか判定
cnt_01 = [0, 0]
for i in range(n):
    cnt_01[a_01[i]] += 1 if n_1Ci[i] == 0 else 0
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]] += 1 if n_1Ci[i] == 0 else 0
if cnt_02[1] % 2 == 1:
    print(2)
else:
    print(0)

Submission status: Accepted

Solution code:
def is_odd_binomial(n, m):
    return ((~n) & m) == 0


N = int(input())
a = list(map(lambda x: int(x) - 1, input()))

parity = sum(a[i] for i in range(N) if is_odd_binomial(N - 1, i))
if parity % 2 == 1:
    ans = 1
elif 1 in a:
    ans = 0
elif parity % 4 == 2:
    ans = 2
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = input()

S = [int(A[i])-1 for i in range(N)]
Lucas = [0 for i in range(N)]
D = {0: 1}
base, m = 1, N - 1
while m != 0:
  if m % 2 == 1:
    L = [i for i in D]
    for i in L:
      D[i+base] = 1
  m //= 2
  base *= 2
for i in D:
  Lucas[i] = 1
oddness = 0
for i in range(N):
  if S[i] % 2 != 0:
    oddness += Lucas[i]
    oddness %= 2

if oddness == 1:
  print(1)
else:
  if 1 in S:
    print(0)
  else:
    S = [S[i]//2 for i in range(N)]
    oddness = 0
    for i in range(N):
      if S[i] % 2 != 0:
        oddness += Lucas[i]
        oddness %= 2
    if oddness == 1:
      print(2)
    else:
      print(0)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(lambda a: int(a) - 1, input()))

prd = 1
if all(a % 2 == 0 for a in A):
    prd = 2
    A = [a // 2 for a in A]

ans = 0
for i in range(N):
    if (N - 1) & i == i:
        ans ^= A[i] % 2

print(prd * ans)

Submission status: Accepted

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


from collections import defaultdict

r = 1
d = defaultdict(int)
while 2**r  <= N:
  for i in range(1,N):
    if i*(2**r) <= N:
      d[i*(2**r)] += 1
    else:
      break
  r+=1

def calc(list_of_int):
  # 1と0で構成されているとする
  length = len(list_of_int)
  res = list_of_int[0]
  
  keisu = 0
  for i,r in zip(list_of_int[1:], range(N-1)):
    keisu += d[N-r-1]-d[r+1]
    res = (res + ((2 if keisu>0 else 1)*i) )% 2
  return res

if 1 in a:
  print(calc(a))
else:
  print(calc(list(map(lambda x:x//2,a)))*2)

Submission status: Accepted

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

N = int(input())
A = list(map(int, list(input().rstrip())))


def contains(n):
    t = n&-n
    return t.bit_length()


def solve1(A, D):
    is1 = False
    cmb_e = 0
    for i, a in enumerate(A):
        if a and cmb_e == 0:
            is1 = not is1
        cmb_e += contains(D-1-i) - contains(i+1)
    return is1

B = [abs(A[i]-A[i+1]) for i in range(N-1)]
if 1 in set(B):
    C = [b%2 for b in B]
    is1 = solve1(C, N-1)
    print(1 if is1 else 0)
else:
    C = [b//2 for b in B]
    is2 = solve1(C, N-1)
    print(2 if is2 else 0)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 2回目で0か2しかない場合と1がある場合
# 1がある時は2は0に変換して良い

def lucas(B, r):
    # nCr が奇数ならTrueを返す
    R = bin(r)[2:]
    for x, y in zip(B[::-1], R[::-1]):
        if x == '0' and y == '1':
            return 0
    return 1

N = ir()
A = np.array(list(map(int, sr())))
A = np.abs(np.diff(A))
N -= 1
bl = False
if 1 not in set(A):
    bl = True
    A //= 2

# それぞれの値が答えに何回貢献しているか
result = 0
A = A.tolist()
B = bin(N-1)[2:]
for i, a in enumerate(A):
    result += a * lucas(B, i)
result %= 2

print(result * 2 if bl else result)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = [int(s)-1 for s in input()]
#print(A)
if 1 in A:
  factor = 1
else:
  factor = 2
  A = [a//2 for a in A]

n = len(A) - 1
s = 0
for i, a in enumerate(A):
  s += a * (n == ( i | (n - i) ))
print((s%2)*factor)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = [int(s)-1 for s in input()]
#print(A)
if 1 in A:
  factor = 1
else:
  factor = 2
  A = [a//2 for a in A]

n = len(A) - 1
s = 0
for i, a in enumerate(A):
  s += a * (n == ( i | (n - i) )) 
  s = s%2
print((s%2)*factor)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(a)-1 for a in input()]
r=2-(1 in A)
print(sum([A[i]&r and (N-1&i)==i for i in range(N)])%2*r)

Submission status: Accepted

Solution code:
N=int(input());A=[int(a)-1 for a in input()];print(sum([A[i] for i in range(N) if N-1&i==i])%(4>>(1 in A)))

Submission status: Accepted

Solution code:
N=int(input());A=[int(a)-1 for a in input()];print(sum([A[i] for i in range(N) if N-1&i==i])%(4>>int(1 in A)))

Submission status: Accepted

Solution code:
N=int(input())
A=[int(a)-1 for a in input()]
r=1 if 1 in A else 2
print(sum([1 if A[i]&r and (N-1&i)==i else 0 for i in range(N)])%2*r)

Submission status: Accepted

Solution code:
#!python3

import numpy as np


# input
N = int(input())
a = input()


def main():
    num, fac = [0] * (N + 1), [0] * (N + 1)
    num[0] = num[1] = 0
    fac[0] = fac[1] = 0
    for i in range(2, N, 2):
        num[i] = 1 + num[i // 2]
        fac[i] = fac[i+1] = fac[i-1] + num[i]
    
    m = np.zeros(N, dtype=int)
    for i in range(N):
        if fac[N-1] == fac[i] + fac[N-1-i]:
            m[i] = 1
    
    x = np.array([int(e) for e in a])
    x -= 1

    if (x * m).sum() % 2 == 1:
        print(1)
        return
    if 1 in x:
        print(0)
        return

    x //= 2
    if (x * m).sum() % 2 == 1:
        print(2)
    else:
        print(0)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

r = 1 if 1 in A else 2

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

ans = 0
for i, a in enumerate(A):
    if a & r:
        if parity_of_nCk(N-1,i):
            ans ^= 1

print(ans*r)

Submission status: Accepted

Solution code:
def Lucas(n, k):
    if n&k == k:
        return 1
    else:
        return 0

n = int(input())
a = list(map(int, list(input())))
odd = 0
cnt = 0
for i in range(n):
    a[i] -= 1
    if a[i] == 1:
        odd += Lucas(n-1, i)
        cnt = 1
if odd % 2 == 1:
    print(1)
else:
    if cnt == 1:
        print(0)
    else:
        for i in range(n):
            a[i] //= 2
            if a[i] == 1:
                odd += Lucas(n-1, i)
        print(odd%2 * 2)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict


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

# Do one step to reduce the list to only 0, 1, or 2
# All subsequent steps will only contain 0, 1, or 2
A = [abs(x - y) for x, y in zip(A, A[1:])]
N -= 1


def solve(A):
    N = len(A)

    def fact(n):
        if n == 0:
            return 1
        return n * fact(n - 1)

    def nCr(n, r):
        return fact(n) // (fact(n - r) * fact(r))

    def nCrMod2(n, r):
        return 0 if (n ^ r) & r else 1
        # See https://brilliant.org/wiki/lucas-theorem/
        while r:
            if r % 2 and not n % 2:
                return 0
            n //= 2
            r //= 2
        return 1

    onlyZeroesAndTwos = Counter(A)[1] == 0

    ans = None
    if onlyZeroesAndTwos:
        ans = 2 * (sum(nCrMod2(N - 1, i) * (A[i] // 2) for i in range(N)) % 2)
    else:
        ans = sum(nCrMod2(N - 1, i) * A[i] for i in range(N)) % 2

    if False:
        import numpy as np

        # Absolute difference and mod 4 sum is almost the same:
        #         abs(x - y)   (x + y) % 4
        # 0, 0    0            0
        # 0, 2    2            2
        # 2, 2    0            0
        #
        # 0, 1    1            1
        # 1, 2    1            3
        #
        # 1, 1    0            2
        #
        # When the list only contains 0 and 2, can just use mod 4 sum exactly
        # When the mod 4 sum answer is odd, know the real answer is 1?

        # nextVec[i] = (vec[i] + vec[i + 1]) % 4
        mat = np.zeros((N, N), dtype=np.int64)
        for i in range(N - 1):
            mat[i][i] = 1
            mat[i][i + 1] = 1

        vec = np.array(A, dtype=np.int64)

        for t in range(N):
            M = np.linalg.matrix_power(mat, t)
            print("t", t)
            print("M^t", M)
            print("v_t", np.matmul(M, vec)[: N - t] % 4)
            print()
        # By inspection, it turns out the M^(N - 1) * v is just the corresponding row of the pascal triangle
        for i in range(N):
            assert np.linalg.matrix_power(mat, N - 1)[0][i] == nCr(N - 1, i)

        mod4 = sum(nCr(N - 1, i) * A[i] for i in range(N)) % 4

        # If there are no ones, mod4 is the exact answer (either 0 or 2)
        ans2 = mod4
        if not onlyZeroesAndTwos:
            # If there are ones, answer is either 0 or 1
            # The answer is 1 if mod4 is 1 or 3
            ans2 = mod4 % 2
        # Check fast and slow way
        assert ans == ans2
    return ans


print(solve(A))

if False:
    # Test
    from itertools import product

    for N in range(2, 7):
        print("N", N)

        groups = defaultdict(list)
        for A in product([0, 1, 2], repeat=N):
            temp = list(A)
            for i in range(N - 1):
                temp = [abs(x - y) for x, y in zip(temp, temp[1:])]
            assert len(temp) == 1
            groups[temp[0]].append(A)

        for k, v in groups.items():
            print("ans", k)
            for A in v:
                assert k == solve(A)
                print("\t", A)
        print()

Submission status: Accepted

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

def solve(N: int, a: str):
    a = [int(a[i])-1 for i in range(N)]
    zeroone = [a[i]%2 for i in range(N)]

    SUM = 0
    comb = [0]*N
    comb[0] = 1

    for i in range(1, N):
        comb[i] = 1 if (N-1)&i == i else 0

    for i in range(N):
        SUM += zeroone[i]*comb[i]
    SUM %= 2

    if SUM == 1:
        print(1)
        return
    
    if 1 in a:
        print(0)
        return
    
    ## 0か2
    zerotwo = [a[i]//2 for i in range(N)]

    SUM = 0
    for i in range(N):
        SUM += zerotwo[i]*comb[i]
    SUM %= 2

    if SUM == 1:
        print(2)
        return
    
    print(0)
    return


def main():
    N = int(input())  # type: int
    a = input() 
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
num_mod = [0]*N
for i in range(1,N):
  tmp = 0
  t = i
  while t%2==0:
    t//=2
    tmp+=1
  num_mod[i] = num_mod[i-1]+tmp
  
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

else:
  a = [x//2 for x in a]
  x = 0
  for i,n in enumerate(a):
    if n%2==0:
      continue
    else:
      if num_mod[N-1]==(num_mod[i]+num_mod[N-1-i]):
        x+=1
  if x%2!=0:
    print(2)
  else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,list(input())))
a = list(map(lambda x:x-1,a))
x = 0
for i,n in enumerate(a):
  if n%2==0:
    continue
  else:
    if ((N-1)^i)&i==0:
      x+=1

if x%2!=0:
  print(1)
  
elif 1 in a:
  print(0)

else:
  a = [x//2 for x in a]
  x = 0
  for i,n in enumerate(a):
    if n%2==0:
      continue
    else:
      if((N-1)&i)==i:
        x+=1
  if x%2!=0:
    print(2)
  else:
    print(0)

Submission status: Accepted

Solution code:
import math

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

x = []
while len(x) != 1:
	inx = 1 << (math.floor(math.log2(N)) - 1)

	N -= inx
	x = [0] * N
	for i in range(N):
		x[i] = abs(a[i] - a[i + inx])

	a = x

print(x[0])

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = [ord(a)-48 for a in args[1]]

    A = [abs(A[i]-A[i+1]) for i in range(n-1)]
    r = 2 if A.count(1) == 0 else 1

    ret = 0
    for i in range(n-1):
        ret += (A[i]//r)*(n-2 == (i | (n-2-i)))

    return str((ret % 2)*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc043/tasks/agc043_b

まず、1度計算して 0,1,2の問題にしてよい

1が含まれているとき、答えが2にならない証明
途中経過に2が含まれていないと、2にはならない
→1が含まれているかつ、偶数がある場合、次は必ず1が含まれる
→偶数が消えない場合、最後まで1が残る
→最後まで2が消えない場合、最後は1になってしまうので×
よって、答えが2になるのは0,2のみのとき
→この時は2で割っておいて、最後に2を掛ければよい
"""
N = int(input())

div2_num = [0]
for i in range(1,N+1):

    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i //= 2
    div2_num.append(div2_num[-1] + cnt)

#print (div2_num)

def EO_nCr(n,r): #nCr%2を返す

    if div2_num[n] - (div2_num[n-r] + div2_num[r]) > 0:
        return 0
    else:
        return 1



A = list(map(int,list(input())))
#print (A)

a = []

for i in range(N-1):
    a.append(abs(A[i]-A[i+1]))



if 1 not in a:
    for i in range(N-1):
        a[i] = a[i] // 2
    lastk = 2
else:
    lastk = 1


ans = 0

for i in range(N-1):

    ans ^= (a[i]%2) * EO_nCr(N-2,i)

    #print (N-2,i,EO_nCr(N-2,i))

print (ans * lastk)

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=list(input())
A=[]
for i in range(n):
  a[i]=int(a[i])-1
  A.append(a[i]%2)

xorct=0
for i in range(n):
  if n-1==(i|n-1-i):
    xorct^=A[i]
if xorct==1:
  print(1)
  sys.exit()

if 1 in a:
  print(0)
  sys.exit()

for i in range(n):
  a[i]=a[i]//2
xorct=0
for i in range(n):
  if n-1==(i|n-1-i):
    xorct^=a[i]
if xorct==1:
  print(2)
  sys.exit()

print(0)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    A=list(map(lambda x: int(x)-1,list(input().strip())))
    ans=1
    if not 1 in A:
        ans*=2
        for i in range(n):
            A[i]>>=1
    parity=0
    for i in range(n):
        if (n-1)&i==i:
            parity^=A[i]&1
    ans*=parity
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = input()
x = []
x.extend([int(i) for i in a])

# 1,2,3 を0,1,2として考えてもよい(差は変わらないから)
# もし1と0だけだったら簡単そう
# 2は012を210にする効果しかない 1 or 0,2 と考えたら同値
# 1が混ざっている条件で最後の答えが2になることはあり得ない->2を0と考えてよい
if 2 in x:
    flag = True
    x = [1 if i == 2 else 0 for i in x]
else:
    flag = False
    x = [1 if i == 3 else 0 for i in x]
c=0
n=len(x)
n_b=bin(n-1)
if x[0]==1:
    c+=1
for i in range(1,n-1):
    tmp_nck = int((n-1) == (i | (n-1-i)))
    if x[i] == 1:
        c+=tmp_nck
if x[n-1]==1:
    c+=1
if flag:
    print(c%2)
else:
    if c%2 == 1:
        print(2)
    else:
        print(0)

Submission status: Accepted

Solution code:
def even_or_odd(a):
    ans = a[0] % 2
    for i in range(1, N):
        ans ^= int((N-1) & i == i) & a[i]
    return ans

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

if even_or_odd([x % 2 for x in a]) == 1:
    print(1)
elif 1 in a:
    print(0)
elif even_or_odd([x//2 for x in a]) == 1:
    print(2)
else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) - 1 for a in input()]
s = sum([a for i, a in enumerate(A) if (N - 1) & i == i])
print(s % (2 if 1 in A else 4))

Submission status: Accepted

Solution code:
def comb(n, r):
  return n == ( r | (n - r) ) 
  
N=int(input())
S=input()
x=0;
b=1;
for i in range(N):
  s=int(S[i])%2;
  x=(x+s*(comb(N-1,i)))%2;
  b*=s%2;
if(x%2 or b==0):
  print(x%2);exit();
x=0;
for i in range(N):
  s=(int(S[i])//2)%2;
  x=(x+s*(comb(N-1,i)))%2;

print((x%2)*2);

Submission status: Accepted

Solution code:
n = int(input())

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

ans = []
for r in range(n - 1):
    if (n - 2)^ r ^ (n - 2 - r) == 0:
        ans.append(int(a[r]))
res = 0

for i in ans:
    res = abs(res - i)
if 1 in a:
    print(res % 2)
else:
    print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input()))
if n <= 1:
    print(a[0])
    exit()
for i in range(n - 1):
    a[i] = abs(a[i + 1] - a[i])
a.pop()
n -= 1
def bc(u, v):
    return (u & v) == v
def solve(t):
    ans = 0
    for i in range(n):
        if a[i] == 1:
            ans ^= bc(n - 1, i)
    print(ans * t)
if 1 in a:
    solve(1)
else:
    for i in range(n):
        a[i] >>= 1
    solve(2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = list(map(lambda x: int(x) - 1, S()))
    ans = 1
    if not 1 in a:
        ans *= 2
        for i in range(n):
            a[i] >>= 1
    res = 0
    for i in range(n):
        #  ~ Lucas の定理から ~
        #  n C k において
        #  k の bitが立っているところについて
        #  n の bitが立っていない場合 n C k が 2の倍数になる
        #  これを超簡単にする方法 (Touristの提出を見た)
        if ((n - 1) & i == i):
            res ^= a[i] & 1
    print(res * ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
n=int(input())
s=input()
frac=[0]*(n+1)
for i in range(1,n+1):
    k=i
    frac[i]=frac[i-1]
    while k%2==0:
        k//=2
        frac[i]+=1

if "2" in s: p=2
else: p=3

ans=0
for i in range(n):
    if int(s[i])==p and frac[n-1]-frac[i]-frac[n-1-i]==0:
        ans^=1
print(ans if p==2 else ans*2)

Submission status: Accepted

Solution code:
def test(a):
    print(*a)
    for i in range(len(a) - 1):
        a = [abs(a1 - a0) for a0, a1 in zip(a, a[1:])]
        # print(' ' * i, *a)
        print(*a)


# test([2, 3, 1, 1, 3, 1, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 2, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 3, 2, 3, 1, 2])
# test([1, 2, 0, 1, 2, 2, 2, 0, 0, 2, 1])
# test([1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0])
# test([0, 0, 0, 0, 0, 1, 0, 0, 1, 2, 0, 2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ])
# test([0] * 21 + [2] + [0] * 21)
# exit()

def solve(n, aaa):
    # シェルピンスキーの三角形
    if '2' not in aaa:
        factor = '3'
        effect = 2
    else:
        factor = '2'
        effect = 1
    # print(factor, effect)

    try_list = []
    m = n - 1
    while m:
        l = 1 << (m.bit_length() - 1)
        m ^= l
        try_list.append((l, m))
    # print(try_list)

    ans = 0
    for i, a in enumerate(aaa):
        if a == factor:
            for l, m in try_list:
                if i >= l:
                    i -= l
                if i == 0:
                    ans ^= effect
                    break
                elif i > m:
                    break
    return ans


n = int(input())
aaa = input()
print(solve(n, aaa))

Submission status: Accepted

Solution code:
import sys
n=int(input())
s=input()
frac=[0]*(n+1)
for i in range(1,n+1):
    k=i
    frac[i]=frac[i-1]
    while k%2==0:
        k//=2
        frac[i]+=1

ans=0
for i in range(n):
    if int(s[i])==2 and frac[n-1]-frac[i]-frac[n-1-i]==0:
        ans^=1

if ans==1: print(1)
elif "2" in s: print(0)
else:
    ans=0
    for i in range(n):
        if int(s[i])==3 and frac[n-1]-frac[i]-frac[n-1-i]==0:
            ans^=1
    print(ans*2)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, list(input())))
t = [0 for i in range(N+1)]
i = 2
while i < N:
	for j in range(i, N+1, i):
		t[j] += 1
	i *= 2
sum_t = [0]
for i in range(1, N+1):
	sum_t.append(sum_t[-1] + t[i])

x = [max(a[i], a[i+1]) - min(a[i], a[i+1]) for i in range(N-1)]


def isCombOdd(n,k):
	bunshi = sum_t[n] - sum_t[n-k]
	bunbo = sum_t[k]
	return bunshi == bunbo

f1 = False
for n in x:
	if n == 1:
		f1 = True
		break
if f1:
	x = [n if n != 2 else 0 for n in x]

candidate = 1 if f1 else 2
ans = 0
for i in range(N-1):
	if x[i] > 0 and isCombOdd(N-2, i):
		ans = 1 - ans

print(0 if ans == 0 else candidate)

Submission status: Accepted

Solution code:
n = int(input())
aa = list(map(lambda x: int(x)-1, list(input())))

def parity(n, r):
    # parity of n choose r
    # via https://math.stackexchange.com/questions/233269/odd-and-even-numbers-in-pascals-triangle-sierpinskis-triangle
    if n <= 1:
        return 1
    if r == 1:
        return n % 2
    if r == 0:
        return 1
    if n % 2 == 0 and r % 2 != 0:
        return 0
    return parity(n//2, r//2)

def ab(x):
    if x < 0:
        return -x
    return x

ans = 0
for i, a in enumerate([a % 2 for a in aa]):
    p = parity(n-1, i)
    if p == 1:
        ans = ab(ans - a)

if ans == 1:
    print(1)
    exit(0)

if 1 in aa:
    print(0)
    exit(0)

ans = 0
for i, a in enumerate([a // 2 for a in aa]):
    p = parity(n-1, i)
    if p == 1:
        ans = ab(ans - a)
print(ans * 2)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

N = int(input())
a = input()
# a = '1' * N

def bit_count(i):
    res = 0
    while ((i>0) and (i&1 == False)):
        i  >>=1
        res += 1
        # print(i)
    return res

f = [0]
for i in range(N//2):
    f.append(f[-1] + bit_count(N-1-i) - bit_count(i+1))

def nCr(n, r):
    if r > n-r: r = n-r
    if f[r] == 0:   # 奇数
        return 1
    else:
        return 0

def main():
    ans = 0
    for i in range(N):
        now = int(a[i]) - 1     # 全体を1引いても同じ
        if now%2:
            # print(i, nCr(N-1, i))
            ans += now * (nCr(N-1, i) % 2)
            ans %= 2
    if ans:
        return ans

    if '2' in a:    # 答えが奇数でなく、入力に2が含まれる場合は答えは0
        return 0

    ans = 0
    for i in range(N):
        now = (int(a[i]) - 1) // 2     # 全体を1引いても同じ
        if now%2:
            ans += now * (nCr(N-1, i) % 2)
            ans %= 2
    return ans*2    # 答えは0か2なので2倍して出す

print(main())