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: Time Limit Exceeded

Solution code:
def cmbmod(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result = result*int(numerator[k])%mod
    return result
N=int(input())
a=[int(d) for d in input()]
if a[0]==1 and a[N-1]==3:
 ans=0
 b=1
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   ans+=cmbmod(N-1, i,2)
   if a[i]!=b:
    c+=1
    b=3
 if c==1:
  print(2)
 else:
  print(ans%2)
elif a[0]==3 and a[N-1]==1:
 ans=0
 b=3
 c=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   ans+=cmbmod(N-1, i,2)
   if a[i]!=b:
    c+=1
    b=1
 if c==1:
  print(2)
 else:
  print(ans%2)
else:
 ans=0
 for i in range(N):
  if a[i]==1 or a[i]==3:
   ans+=cmbmod(N-1, i,2)
 print(ans%2)

Submission status: Time Limit Exceeded

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

x = [[0 for i in range(n+1)] for j in range(n+1)]

for i, a_i in enumerate(a):
	x[1][i+1] = a_i

for i in range(2, n+1):
	for j in range(1, n+2-i):
		x[i][j] = abs(x[i-1][j] - x[i-1][j+1])
print(x[n][1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.array([int(i) for i in input()])

ans = A
for i in range(N-1):
    ans = np.abs(ans[:-1] - ans[1:])
    
print(ans[0])

Submission status: Time Limit Exceeded

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:
                l.append(x)
            elif len(l)>0 and 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: Time Limit Exceeded

Solution code:
import copy
N=int(input())
A=input()
R=list(A)
L=list(map(int,R))
B=copy.copy(L)
for i in range(N-1):
  for j in range(N-1-i):
    B[j]=abs(L[j]-L[j+1])
  B.pop(-1)
  L=copy.copy(B)
print(L[0])

Submission status: Time Limit Exceeded

Solution code:
import copy
N=int(input())
A=input()
R=list(A)
L=list(map(int,R))
B=copy.copy(L)
for i in range(N):
  for j in range(N-1-i):
    B[j]=abs(L[j]-L[j+1])
    L=copy.copy(B)
print(L[0])

Submission status: Time Limit Exceeded

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

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

print(arr[0])

Submission status: Time Limit Exceeded

Solution code:


n=int(input())
s=input()
lt=[int(i) for i in list(s)]
matrix=[int(0) for i in range(n)]
for i in range(n):
    matrix[i]=[int(0) for _ in range(n)]

for i in range(n):
    matrix[0][i]=lt[i]

for row in range(1,n):
    for col in range(n-row):
        matrix[row][col]=abs(matrix[row-1][col]-matrix[row-1][col+1])

print(matrix[n-1][0])

Submission status: Time Limit Exceeded

Solution code:
n=input()
sequence = list(input())
#print(sequence)

ans1=list()
ans2=list()
ans2=sequence
for i in range(int(n)-1):
    if(i%2==0):
        #print(ans1)
        ans1 = list()
        #print(ans1)
    else:
        
        #print(ans2)
        ans2 = list()
        #print(ans2)
    #print("////////////////////////")

    for f in range(int(n)-i-1):
        if(i%2==0):
            ans1.append(abs(int(ans2[f])-int(ans2[f+1])))
            #print(ans1[f])
        else:
            ans2.append(abs(int(ans1[f])-int(ans1[f+1])))
            #print(ans2[f])

#rint(ans1)
#print(ans2)
if(len(ans1)==1):
    print(ans1[0])
else:
    print(ans2[0])

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().strip()))
    dp = [0] * n
    for i in range(n):
        for j in range(n-i):
            if not i:
                dp[j] = nums[j]
            else:
                dp[j] = abs(dp[j] - dp[j+1])
    print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
b=str(input())
c=list(b)
a=[int(str) for str in c]

def cutting(x):
    y=[]
    for i in range(len(x)-1):
        y.append(abs(x[i]-x[i+1]))
    return y
x=a
for j in range(n-1):
    x=cutting(x)


print(x[0])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().decode().rstrip()))


def pp(A, offset=0):
    s = ' ' * offset + ' '.join(map(str, A))
    print(s)


def test(A):
    i = 0
    while len(A) > 1:
        pp(A, i)
        A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
        i += 1
    pp(A, i)
    return A


def convert(counts):
    ret = []
    if counts[0][1] > 1:
        ret.append((0, counts[0][1] - 1))
    for (n1, cnt1), (n2, cnt2) in zip(counts, counts[1:]):
        ret.append((abs(n1 - n2), 1))
        if cnt2 > 1:
            ret.append((0, cnt2 - 1))
    return ret


# A = []
# for _ in range(N):
#     import random
#     A.append(random.randint(1, 3))
# ans = test(A)
# print(ans)


# 0, 1, 2 だけにする
A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
# 何個続くかを持つ
counts = []
n = None
cnt = 0
for a in A:
    if n != a:
        n = a
        cnt = 0
        counts.append((n, 0))
    cnt += 1
    counts[-1] = (n, cnt)

while len(counts) >= 2 or counts[0][1] > 1:
    counts = convert(counts)
print(counts[0][0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())

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

n_val = change_base(N-1, 2)

def lucas(m, mod=2):
    #n_val = change_base(n, mod)
    m_val = change_base(m, mod)
    ret = 1
    cv = int(n_val) - int(m_val)
    if '9' in list(str(cv)):
      return 0
    else:
      return 1

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: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())
A = [int(i)-1 for i in list(input())]

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 = 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
    ret = 1
    for ni, mi in zip(n_val, m_val):
        ret *= comb_for_bit(ni, mi)
    return ret % mod

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

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: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())
A = [int(i)-1 for i in list(input())]

def lucas(n,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
    ret = 1
    for ni, mi in zip(n_val, m_val):
        ret *= comb_for_bit(ni, mi)
    return ret % mod

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

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(N-1, k)
  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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=[int(c)-1 for c in SI()]
    cc=[1]
    for i in range(1,n):
        cc.append(-cc[-1]*(n-i)//i)
    s=sum(a*c for a,c in zip(aa,cc))%2
    if s==1:
        print(1)
        exit()
    if 1 in aa:
        print(0)
        exit()
    aa=[a//2 for a in aa]
    s=sum(a*c for a,c in zip(aa,cc))%2
    if s==1:print(2)
    else:print(0)

main()

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
from math import factorial as fc

def comb(n,k):
  if n < k:
    return 0
  else:
    return int(fc(n) / fc(k) / fc(n-k))

def n_func(x, n):
    nums = '0123456789ABCDEF'
    result = ''
    while(1):
        result = nums[int(x % n)] + result
        x = x // n
        if x==0:
            break
    return result

def lucas(n, k, p):
    n_p = n_func(n, p)
    k_p = n_func(k, p)
    k_p = k_p.zfill(len(n_p))

    result = 1
    for n_i, k_i in zip(n_p, k_p):
        result *= comb(int(n_i), int(k_i))
    return result

N = int(input())
a = list(map(int, list(input())))
a = np.array(a) - 1

if 1 in a:
  b = a % 2
  total = 0
  for idx in range(N):
    if b[idx] == 1:
      total += lucas(N-1, idx, 2)
    else:
      continue
  total = int(total) % 2
  print(total)

else:
  b = a / 2
  total = 0
  for idx in range(N):
    if b[idx] == 1:
      total += lucas(N-1, idx, 2)
    else:
      continue
  total = int(total) % 2
  print(total * 2)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
from math import factorial as fc
N = int(input())
a = list(map(int, list(input())))
a = np.array(a) - 1

if 1 in a:
  b = a % 2
  total = 0
  for i in range(N):
    if b[i] % 2 == 0:
      continue
    else:
      tmp = (fc(N-1)/(fc(i) * fc(N-1-i))) % 2
      if tmp == 0:
        continue
      else:
        total += 1
  total = int(total) % 2
  print(total)

else:
  b = a / 2
  total = 0
  for i in range(N):
    if b[i] % 2 == 0:
      continue
    else:
      tmp = (fc(N-1)/(fc(i) * fc(N-1-i))) % 2
      if tmp == 0:
        continue
      else:
        total += 1
  total = int(total) % 2
  total = int(total) % 2
  print(total * 2)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
from math import factorial as fc
N = int(input())
a = list(map(int, list(input())))
a = np.array(a) - 1

if 1 in a:
  b = a % 2
  total = 0
  for i in range(N):
    tmp = fc(N-1)/(fc(i) * fc(N-1-i)) * b[i]
    total += tmp
  total = int(total) % 2
  print(total)

else:
  b = a / 2
  total = 0
  for i in range(N):
    tmp = fc(N-1)/(fc(i) * fc(N-1-i)) * b[i]
    total += tmp
  total = int(total) % 2
  print(total * 2)

Submission status: Time Limit Exceeded

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):
  tmp = np.abs(x[i-1][:N-i] - x[i-1][1:N-i+1])
  x.append(tmp)

print(x[-1][0])

Submission status: Time Limit Exceeded

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=[]
    if len(arr)%2==9:
      for i in range(len(arr)//2):
        tmp.append(abs(arr[2*i]-arr[2*i+1]))
    else:
      for i in range(len(arr)-1):
        tmp.append(abs(arr[i]-arr[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: Time Limit Exceeded

Solution code:
n = int(input())
a = input()
for i in range(1, n):
  prev = a
  a = ''
  for j in range(n - i):
    a += str(abs(int(prev[j]) - int(prev[j+1])))
print(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, list(input())))
for i in range(1, n):
  prev = a
  for j in range(n - i):
    a[j] = abs(prev[j] - prev[j+1])
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
b=input()
k=""
while len(b)>1:
    for i in range(len(b)-1):
        c = abs(int(b[i])-int(b[i+1]))
        k=k+str(c)
    b=k
    k=""
print(b)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
b=input()
d=len(b)
k=""
while d>1:
    for i in range(len(b)-1):
        c = abs(int(b[i])-int(b[i+1]))
        k=k+str(c)
    d=d-1
    b=k
print(b[-1])

Submission status: Time Limit Exceeded

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 rec(cur):
    if len(cur) == 1:
        return cur[0]
    nxt = []
    for i in range(len(cur)-1):
        nxt.append(abs(cur[i] - cur[i+1]))
    return rec(nxt)

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

ans = rec(A)
print(ans)

Submission status: Time Limit Exceeded

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

for _ in range(n-1):
    for num in range(len(a)-1):
        a[num] = abs(a[num] - a[num+1])

print(a[0])

Submission status: Time Limit Exceeded

Solution code:
input()
xs = [int(char) for char in input()]


def f(xs):
    length = len(xs)
    if length == 1:
        return xs[0]
    else:
        new = []
        lst  = range(length)
        for i in lst:
            if i == 0:
                continue
            else:
                new.append(abs(xs[i]-xs[i-1]))
        return f(new)

print(f(xs))

Submission status: Time Limit Exceeded

Solution code:
input()
xs = [int(char) for char in input()]


def f(xs):
    if len(xs) == 1:
        return xs[0]
    else:
        new = []
        lst  = range(len(xs))
        for i in lst:
            if i == 0:
                continue
            else:
                new.append(abs(xs[i]-xs[i-1]))
        return f(new)

print(f(xs))

Submission status: Time Limit Exceeded

Solution code:
input()
xs = [int(char) for char in input()]

def f(xs):
    if len(xs) == 1:
        return xs[0]
    else:
        new = []
        for i in range(len(xs)):
            if i == 0:
                continue
            else:
                new.append(abs(xs[i]-xs[i-1]))
        return f(new)

print(f(xs))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
n = int(input())
a = list(input())
a_n = [int(s) for s in a]#配列を全て数値に変更
point = n - 1#配列の代入を始める場所
for i in range(point):
    #⓪print(i)
    for ii in range(point):
        #❶print('ii:{:.3f}'.format(a_n[ii]))
        #❷print('ii+1:{:.3f}'.format(a_n[ii+1]))
        a_n[ii] = abs(a_n[ii] - a_n[ii+1])
    point -= 1
print(a_n[0])

Submission status: Time Limit Exceeded

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

        # Check arg value
        if n_max < 0:
            raise ValueError('Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 0:
                raise ValueError('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('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('Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError('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('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('Required 0 <= n <= n_max, n: {n}, n_max: {self._n_max}')
        if not (0 <= r and r <= n):
            raise Exception('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: Time Limit Exceeded

Solution code:
n=int(input())
x=[int(s)-1for s in input()]
f=1
while f:
  y=0
  z=x[0]//f%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]//f%2)
  a=f*z
  f=2*(z<1)*(not f in x)-2*f+2
print(a)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=[int(s)-1for s in input()]
f=1
while f:
  y=0
  z=x[0]//f%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]//f%2)
  a=f*z
  f=2*(z<1)*(not f in x)
print(a)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=[int(s)-1for s in input()]
f=1
while f:
  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)
  a=f*z
  f=2*(z<1)*(not 1in x)
  x=[i//2 for i in x]
print(a)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import math
N = int(input())
a = input()

def combination(n: int, r: int) -> int:
    comb = 1
    for i in range(r):
        comb *= n-i
    comb //= math.factorial(r)
    return comb

def is_ans_odd(a: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(a):
        x = int(c)
        co = combination(len(a)-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: Time Limit Exceeded

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

S = [int(A[i])-1 for i in range(N)]

oddness = 0
for i in range(N):
  m, n = N-1, i
  if S[i] % 2 != 0:
    parity = 1
    while m != 0:
      if m % 2 == 0 and n % 2 == 1:
        parity = 0
        break
      m //= 2
      n //= 2
    oddness += parity
    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):
      m, n = N-1, i
      if S[i] % 2 != 0:
        parity = 1
        while m != 0:
          if m % 2 == 0 and n % 2 == 1:
            parity = 0
            break
          m //= 2
          n //= 2
        oddness += parity
        oddness %= 2
    if oddness == 1:
      print(2)
    else:
      print(0)

Submission status: Time Limit Exceeded

Solution code:
def calc(list_of_int):
  # 1と0で構成されているとする
  length = len(list_of_int)
  res = list_of_int[0]
  keisu = 1
  for i,r in zip(list_of_int[1:],range(N-1)):
    
    keisu = keisu*(N-r-1)//(r+1)
    # print(keisu,(N-r)-1,(r+1))
    res = (res + (keisu*i) )% 2
  return res
  
N = int(input())
S = input()
a = [int(s)-1 for s in S]
if 1 in a:
  print(calc(a))
else:
  print(calc(list(map(lambda x:x//2,a)))*2)

Submission status: Time Limit Exceeded

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(n, r):
    # nCr が奇数ならTrueを返す
    N = bin(n)[2:]; R = bin(r)[2:]
    ret = 1
    for x, y in zip(N[::-1], R[::-1]):
        if x == '0' and y == '1':
            ret = 0; break
    return ret

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()
for i, a in enumerate(A):
    result += a * lucas(N-1, i)
result %= 2

print(result * 2 if bl else result)

Submission status: Time Limit Exceeded

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(n, r):
    # nCr が奇数ならTrueを返す
    N = bin(n)[2:]; R = bin(r)[2:]
    ret = 1
    for x, y in zip(N[::-1], R[::-1]):
        if x == '0' and y == '1':
            ret = 0; break
    return ret

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()
for i in range(N):
    result += A[i] * lucas(N-1, i)
result %= 2

print(result * 2 if bl else result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
 
x = str(input())
kari_x = ""
p = 0
while len(x) > 2:
    for i in range(len(x)-2):
        if int(x[i+1]) >= int(x[i]) and int(x[i+1]) >= int(x[i+2]):
            kari_x += str(abs(int(x[i])-int(x[i+2])))
        elif int(x[i+1]) != 0:
            kari_x += str(abs(int(x[i+1])*2 - int(x[i]) -int(x[i+2])))
        else:
            kari_x += str(abs(int(x[i]) -int(x[i+2])))
    x = kari_x
    kari_x = ""
 
if len(x) == 2:
    print(abs(int(x[0])-int(x[1])))