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

Solution code:
N = int(input())
li_ = [0 for k in range(N)]
 
for i,string in enumerate(input()):
    li_[i] = int(string)



def func(i,j):
    if i==0:
        return li_[j]
    else:
        return abs(func(i-1,j)-func(i-1,j+1))

print(func(N-1,0))

Submission status: Runtime Error

Solution code:
N=int(input())
li_=list(map(int,list(input())))
 
def fun(i,j):
  if i==0:return li_[j]
  else:return abs(fun(i-1,j)-fun(i-1,j+1))

print(fun(N-1,0))

Submission status: Runtime Error

Solution code:
N=int(input())
li_=list(map(int,list(input())))

def fun(i,j):
  if i==0:return li_[j]
  else:return abs(fun(i-1,j)-fun(i-1,j+1))

print(fun(N,1))

Submission status: Runtime Error

Solution code:
N = int(input())
li_ = [0 for k in range(N)]

for i,string in enumerate(input()):
    li_[i] = int(string)



def dp(i,j):
    if i==0:
        return li_[j]
    else:
        return abs(dp(i-1,j)-dp(i-1,j+1))

print(dp(N-1,0))

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int,input()))

DP = [[0]*N for _ in range(N)]
DP[0] = a

for i in range(1,N):
    for j in range(N-i):
        DP[i][j] = abs(DP[i-1][j]-DP[i-1][j+1])

print(DP[N-1][0])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
n = int(input())
a = list(map(int, list(input())))

memo = {}
for i in range(n):
    memo[(1, i+1)] = a[i]
def dfs(i, j):
    if (i, j) in memo:
        return memo[(i,j)]
    ret = abs(dfs(i-1, j) - dfs(i-1, j+1))
    memo[(i, j)] = ret
    return ret
print(dfs(n, 1))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
a = list(map(int, list(input())))

memo = {}
for i in range(n):
    memo[(1, i+1)] = a[i]
def dfs(i, j):
    if (i, j) in memo:
        return memo[(i,j)]
    ret = abs(dfs(i-1, j) - dfs(i-1, j+1))
    memo[(i, j)] = ret
    return ret
print(dfs(n, 1))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    a=input() #1行ベクトル
    A=[int(a[i]) for i in range(N)]
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    while True:
        l=[]
        for i in range(len(A)-1):
            x=abs(A[i]-A[i+1])
            if x>0 or l[-1]!=0:
                l.append(x)
        if len(l)<2:
            break
        A=copy(l)
    if len(l)==0:
        return 0
    return l[0]


if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())

s = []

for i in range(H):

    S = list(input())
    s.append(S)

dis = [[float("inf")] * W for i in range(H)]

if s[0][0] == "#":
    dis[0][0] = 1
else:
    dis[0][0] = 0

for i in range(H):

    for j in range(W):

        if i != H-1:

            if s[i][j] == "." and s[i+1][j] == "#":

                dis[i+1][j] = min(dis[i][j] + 1,dis[i+1][j])

            else:
                dis[i+1][j] = min(dis[i][j],dis[i+1][j])

        if j != W-1:
            if s[i][j] == "." and s[i][j+1] == "#":

                dis[i][j+1] = min(dis[i][j] + 1,dis[i][j+1])

            else:
                dis[i][j+1] = min(dis[i][j],dis[i][j+1])

print (dis[-1][-1])

Submission status: Runtime Error

Solution code:
def main():
  N=int(input())
  seq=input()
  tri = [int(i) for i in list(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: Runtime Error

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

Solution code:
def main():
  inp = input()
  N = inp[:2]
  seq = str(inp[3:])
  print(N,seq)
  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: Runtime Error

Solution code:
inp = input()
N = inp[:2]
seq = str(inp[3:])
print(N,seq)
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

print(tri[-1])

Submission status: Runtime Error

Solution code:
n = int(raw_input())
elems = map(int,list(raw_input()))
mem = {}
def f(i,j, elems):
	if i == 1:
		return elems[j-1]
	if (i,j) not in mem:

		r = abs(f( i - 1, j,elems) - f( i - 1,j+1, elems))
		mem[(i,j)] = r 
		return r
	return mem[(i,j)]
print f(n,1,elems)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
# input = sys.stdin.buffer.readline

MOD = 10**9 + 7
INT_MAX = (1 << 63) - 1

@lru_cache(None)
def dfs(i, j, nums):
    if i == 1:
        return int(nums[j-1])
    return abs(dfs(i-1, j, nums) - dfs(i-1, j+1, nums))

if __name__ == "__main__":
    n = int(input())
    nums = input()
    print(dfs(n, 1, nums))

Submission status: Runtime Error

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

    a = list(map(lambda x: int(x)-1, list(a)))
    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

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


main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
N = int(input())
A = [int(i)-1 for i in list(input())]
_comb = {}
_comb[0] = 1
def comb(k):
  try:
    return _comb[k]
  except:
    _comb[k] = int(comb(k-1) / k * (N- k))
    return _comb[k]

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

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

Solution code:
N = int(input())
A = input()
a_list = []
for i in A:
  a_list.append(int(i))

for j in range(N-1):
	for i in range(len(a_list)-1):
  		a_list[i] = abs(a_list[i] - a_list[i+1])
    a_list.pop(-1)
print(a_list[0])

Submission status: Runtime Error

Solution code:
class MemorizedFactorial:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 0:
                raise ValueError(f'Require m >= 0, m: {m}')

        # List of n! mod m
        factv = [1] * (n_max+1)
        for i in range(2, n_max+1):
            if m:
                factv[i] = factv[i-1] * i % m
            else:
                factv[i] = factv[i-1] * i

        self._n_max = n_max
        self._m = m
        self._factv = factv

    # Return n! or n! mod m
    def factorial(self, n: int) -> int:
        if n > self._n_max:
            raise ValueError(f'n is larger than n_max, n: {n}, n_max: {self._n_max}')

        return self._factv[n]

import fractions

# WARN: Require mod number m is prime number
class MemorizedCombination:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            # Condition of Fermat's little theorem
            if not (m > n_max and fractions.gcd(m, n_max) == 1):
                raise ValueError(f'Require m >= n_max and coprime, m: {m}, n_max: {n_max}')

        mem_fact = None
        mod_inv_factv = None
        if m:
            mem_fact = MemorizedFactorial(n_max, m)
            # List of inverse r! mod m
            mod_inv_factv = [1] * (n_max+1)
            mod_inv_factv[n_max] = pow(mem_fact.factorial(n_max), m-2, m)
            for i in range(n_max-1, 1, -1):
                mod_inv_factv[i] = mod_inv_factv[i+1] * (i+1) % m
        else:
            mem_fact = MemorizedFactorial(n_max)

        self._n_max = n_max
        self._m = m
        self._mem_fact = mem_fact
        self._mod_inv_factv = mod_inv_factv

    # Return nCr or nCr mod m
    def combination(self, n: int, r: int) -> int:
        # Check arg value
        if not (0 <= n and n <= self._n_max):
            raise Exception(f'Required 0 <= n <= n_max, n: {n}, n_max: {self._n_max}')
        if not (0 <= r and r <= n):
            raise Exception(f'Required 0 <= r <= n, r: {r}, n: {n}')

        m = self._m
        mem_fact = self._mem_fact
        mod_inv_factv = self._mod_inv_factv
        comb = None
        if m:
            comb = mem_fact.factorial(n) * mod_inv_factv[r] * mod_inv_factv[n-r] % m
        else:
            comb = mem_fact.factorial(n) // mem_fact.factorial(n-r) // mem_fact.factorial(r)

        return comb

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

memfact = MemorizedFactorial(N)
#memcomb = MemorizedCombination(N)

def is_ans_odd(num_str: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(num_str):
        x = int(c)
        co = memfact.factorial(len(num_str)-1) // memfact.factorial(len(num_str)-1-i) // memfact.factorial(i)
        #co = memcomb.combination(len(num_str)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class MemorizedFactorial:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 0:
                raise ValueError(f'Require m >= 0, m: {m}')

        # List of n! mod m
        factv = [1] * (n_max+1)
        for i in range(2, n_max+1):
            if m:
                factv[i] = factv[i-1] * i % m
            else:
                factv[i] = factv[i-1] * i

        self._n_max = n_max
        self._m = m
        self._factv = factv

    # Return n! or n! mod m
    def factorial(self, n: int) -> int:
        if n > self._n_max:
            raise ValueError(f'n is larger than n_max, n: {n}, n_max: {self._n_max}')

        return self._factv[n]

import fractions

# WARN: Require mod number m is prime number
class MemorizedCombination:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            # Condition of Fermat's little theorem
            if not (m > n_max and fractions.gcd(m, n_max) == 1):
                raise ValueError(f'Require m >= n_max and coprime, m: {m}, n_max: {n_max}')

        mem_fact = None
        mod_inv_factv = None
        if m:
            mem_fact = MemorizedFactorial(n_max, m)
            # List of inverse r! mod m
            mod_inv_factv = [1] * (n_max+1)
            mod_inv_factv[n_max] = pow(mem_fact.factorial(n_max), m-2, m)
            for i in range(n_max-1, 1, -1):
                mod_inv_factv[i] = mod_inv_factv[i+1] * (i+1) % m
        else:
            mem_fact = MemorizedFactorial(n_max)

        self._n_max = n_max
        self._m = m
        self._mem_fact = mem_fact
        self._mod_inv_factv = mod_inv_factv

    # Return nCr or nCr mod m
    def combination(self, n: int, r: int) -> int:
        # Check arg value
        if not (0 <= n and n <= self._n_max):
            raise Exception(f'Required 0 <= n <= n_max, n: {n}, n_max: {self._n_max}')
        if not (0 <= r and r <= n):
            raise Exception(f'Required 0 <= r <= n, r: {r}, n: {n}')

        m = self._m
        mem_fact = self._mem_fact
        mod_inv_factv = self._mod_inv_factv
        comb = None
        if m:
            comb = mem_fact.factorial(n) * mod_inv_factv[r] * mod_inv_factv[n-r] % m
        else:
            comb = mem_fact.factorial(n) // mem_fact.factorial(n-r) // mem_fact.factorial(r)

        return comb

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

memcomb = MemorizedCombination(N)

def is_ans_odd(num_str: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(num_str):
        x = int(c)
        co = memcomb.combination(len(num_str)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
a=[int(i)-1 for i in list(input())]
def solve(seq):
    res=0
    for k in range(N):
        tmp=1
        if (N&k)==k:
            tmp=0
        res+=tmp*seq[k]
        res%=2
    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: Runtime Error

Solution code:
class MemorizedFactorial:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 0:
                raise ValueError(f'Require m >= 0, m: {m}')

        # List of n! mod m
        factv = [1] * (n_max+1)
        for i in range(2, n_max+1):
            if m:
                factv[i] = factv[i-1] * i % m
            else:
                factv[i] = factv[i-1] * i

        self._n_max = n_max
        self._m = m
        self._factv = factv

    # Return n! or n! mod m
    def factorial(self, n: int) -> int:
        if n > self._n_max:
            raise ValueError(f'n is larger than n_max, n: {n}, n_max: {self._n_max}')

        return self._factv[n]

# WARN: Require mod number m is prime number
class MemorizedCombination:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 2:
                raise ValueError(f'Require m >= 2, m: {m}')

        mem_fact = None
        mod_inv_factv = None
        if m:
            mem_fact = MemorizedFactorial(n_max, m)
            # List of inverse r! mod m
            mod_inv_factv = [1] * (n_max+1)
            mod_inv_factv[n_max] = pow(mem_fact.factorial(n_max), m-2, m)
            for i in range(n_max-1, 1, -1):
                mod_inv_factv[i] = mod_inv_factv[i+1] * (i+1) % m
        else:
            mem_fact = MemorizedFactorial(n_max)

        self._n_max = n_max
        self._m = m
        self._mem_fact = mem_fact
        self._mod_inv_factv = mod_inv_factv

    # Return nCr or nCr mod m
    def combination(self, n: int, r: int) -> int:
        # Check arg value
        if not (0 <= n and n <= self._n_max):
            raise Exception(f'Required 0 <= n <= n_max, n: {n}, n_max: {self._n_max}')
        if not (0 <= r and r <= n):
            raise Exception(f'Required 0 <= r <= n, r: {r}, n: {n}')

        m = self._m
        mem_fact = self._mem_fact
        mod_inv_factv = self._mod_inv_factv
        comb = None
        if m:
            comb = mem_fact.factorial(n) * mod_inv_factv[r] * mod_inv_factv[n-r] % m
        else:
            comb = mem_fact.factorial(n) // mem_fact.factorial(n-r) // mem_fact.factorial(r)

        return comb

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

memcomb = MemorizedCombination(N)

def is_ans_odd(num_str: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(num_str):
        x = int(c)
        co = memcomb.combination(len(num_str)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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(f.readline())
a = list(map(lambda x:int(x)-1,list(f.readline())))
   
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: Runtime Error

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 = [a//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: Runtime Error

Solution code:
#editorial参照

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

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

div2=np.array(div2)

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

else:
    print(0)

Submission status: Runtime Error

Solution code:
from functools import reduce
n = int(input())
A = list(map(int, input().split()))
cnt = 0
n1 = n - 1
mul = lambda x, y: x*y
def cmb(x, y):
    y = min(y, x-y)
    over = reduce(mul, range(x-y+1, x+1))
    under = reduce(mul, range(1, y+1))
    return over//under
for i, a in enumerate(A, 1):
    if a != 2:
        cnt += cmb(n1, i)
if cnt%2==1:
    print(1)
elif cnt > 0:
    print(0)
else:
    AA = [(a-1)//2 for a in A]
    cnt = 0
    for i, a in enumerate(AA, 1):
        if a == 1:
            cnt += cmb(n1, i)
    if cnt%2:
        print(2)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,list(input())))

for j in range(len(A)-1):
    H.append(abs(A[j]-A[j+1]))

count=[0,0,0]
for x in H:
    count[x]+=1

if count[1]==0:
    print(H[0]^H[-1])
else:
    if H[0]==2:
        H[0]=0
    if H[-1]==2:
        H[-1]=0
    print(H[0]^H[-1])

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict


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

# Do one step to reduce to make the list 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))

    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)

    total = 0
    for i in range(N):
        total = (total + nCr(N - 1, i) * A[i]) % 4

    if Counter(A)[1] == 0:
        # If there are no ones, total is the exact answer (either 0 or 2)
        return total
    else:
        # Answer has to be 0 or 1
        if total % 2:
            return 1
        else:
            return 0
    return total


print(solve(A))

if False:
    from itertools import product

    for N in range(2, 7):
        print("")
        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:
                ans = solve(A)
                assert k == ans
                print("\t", A, "\t", ans)

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict


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

# Do one step to reduce to make the list 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))

    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.
        # 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", (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)

    total = 0
    for i in range(N):
        total = (total + nCr(N - 1, i) * A[i]) % 4

    if Counter(A)[1] == 0:
        # If there are no ones, total is the exact answer (either 0 or 2)
        return total
    else:
        # Answer has to be 0 or 1
        if total % 2:
            return 1
        else:
            return 0
    return total


print(solve(A))

if False:
    from itertools import product

    for N in range(2, 7):
        print("")
        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:
                ans = solve(A)
                assert k == ans
                print("\t", A, "\t", ans)

Submission status: Runtime Error

Solution code:
import math

N = int(input())
A = list(map(int,input()))
B = []
M = math.ceil(math.log(N,2)) 

for i in range(N):
  a = 0
  for j in range(1,M+1,1):
    a += math.floor((N-1)/(2**j))-math.floor((i)/(2**j))-math.floor((N-1-i)/(2**j))
  if a == 0:
    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:
    for i in range(N):
      A[i] = (A[1]-1)//2
    for i in range(N):
      a = 0
      C = []
      for j in range(1,M+1,1):
        a += math.floor((N-1)/(2**j))-math.floor((i)/(2**j))-math.floor((N-1-i)/(2**j))
      if a == 0:
        C.append(1)
      else:
        C.append(0)
    
    for i in range(N):
      b += C[i]*A[i]
    if b % 2 == 1:
      print(2)
    else:
      print(0)

Submission status: Runtime Error

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

if len(x) > 1:
    x = [abs(x[i] - x[i + 1]) for i in range(len(x) - 1)]


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