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:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi
import sys
#input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  n = int(input())
  s = input()
  x = [[0 for i in range(n)] for j in range(n)]
  for i in range(n):
    x[0][i] = int(s[i])
  for i in range(1, n):
    for j in range(n-i):
      x[i][j] = abs(x[i-1][j] - x[i-1][j+1])
  print(x[n-1][0])
  

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
A = np.array(list(map(int, list(input()))))

for _ in range(n-1):
    A = np.abs(np.diff(A))
print(A[0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(input())
An = [int(x) for x in A]
for i in range(N-1):
  An1 = [abs(An[x]-An[x+1]) for x in range(N-i-1)]
  An = An1
print(An[0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
arr_rev = list(map(int, list(input())))
arr_rev.reverse()


def calc(a, b):
    return abs(-a + b)

inp = arr_rev
for i in range(N-1):
    out = [calc(inp[x], inp[x+1]) for x in range(len(inp)-1)]
    inp = out

print(inp[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in list(input())]

while len(A) > 1:
  B = []
  for i in range(len(A)-1):
    B.append(abs(A[i] - A[i+1]))
  A = B
  
print(A[0])

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())
sequence = input()

prev = [-1] * len(sequence)
for i in range(len(sequence)):
    prev[i] = int(sequence[i])

while len(prev) > 1:
    cur = [-1] * (len(prev) - 1)
    for i in range(len(cur)):
        cur[i] = abs(prev[i] - prev[i+1])
    prev = cur

print(prev[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int,list(input())))
for i in range(n):
    for j in range(len(s)-1):
        s.append(abs(s[0]-s[1]))
        s.pop(0)
print(s[0])

Submission status: Time Limit Exceeded

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

while (len(current_list)!=1) :
  current=[]
  for i,num in enumerate(current_list[:-1]) :
    current.append(abs(num-current_list[i+1]))
  
  current_list=current
  

print (current_list[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
for _ in range(n-1):
    tmp = ""
    for i, s in enumerate(S):
        if i != 0:
            tmp += str(abs(int(s) - int(S[i-1])))
    S = tmp
print(S)

Submission status: Time Limit Exceeded

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

while n > 1:
    for i, a in enumerate(a_li[:]):
        if i == n - 1:
            n -= 1
            break
        a_li[i] = abs(a_li[i] - a_li[i+1])
print(a_li[0])

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()))

N = ir()
A = np.array(list(map(int, sr())))
for _ in range(N-1):
    A = np.abs(np.diff(A))

print(A[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

s = input()
a = []

for i in s:
    a.append(int(i))

while(True):
    b = []
    for i in range(len(a) - 1):
        b.append(abs(a[i] - a[i + 1]))
    a = b[:]
    if len(a) == 1:
        break
print(a[0])

Submission status: Accepted

Solution code:
def solve_for_01(nums):
    # nums: 各要素が 0 or 1 のリスト。
    # 「x_{i+1, j} = x_{i, j} ^ x_{i, j+1} で定義。x_{N, 1} は？」という問題を解く。
    # a_{i} は (N-1)_C_i 回作用するので、(N-1)_C_i の偶奇で a_{i} が残るか否かが決まる。
    # (N-1)_C_i の偶奇については Lucasの定理から
    #   (N-1) & i == i <=> 奇数
    #   (N-1) & i != i <=> 偶数
    # が言える。
    N = len(nums)
    ans = 0
    for i, x in enumerate(nums):
        if (N - 1) & i == i:
            ans ^= x
    return ans


def main():
    # ref: https://atcoder.jp/contests/agc043/submissions/16398495
    N = int(input())
    A = list(map(lambda x: int(x) - 1, input()))
    if 1 in A:
        # 1が含まれる場合は答えは0 or 1になる。
        # 答えの偶奇だけ合致してればよいので、2 -> 0で置き換えて問題を解いてもこのケースでは大丈夫。
        print(solve_for_01([a % 2 for a in A]))
    else:
        # 1が含まれない場合はすべての数字は0 or 2。
        # 2で割ることで、すべての数字が0 or 1のケースに帰着可能。
        print(solve_for_01([a // 2 for a in A]) * 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n=int(input())
a=list(map(lambda x:int(x)-1,list(input())))
memo=[-1]*(n+1)
def log(x):
    if memo[x]!=-1:return memo[x]
    ret=0
    xx=x
    while x and x%2==0:
        x//=2
        ret+=1
    memo[xx]=ret
    return ret

def slv(n,a):
    v=a[0]
    if all(v==x for x in a):return 0
    # 答えの偶奇を求める
    chk=0
    tmppl=0
    tmpmi=0
    for i in range(n):
        x=a[i]%2
        if tmppl>tmpmi:
            pass
        else:
            chk+=a[i]
            chk%=2
        tmppl+=log(n-i-1)
        tmpmi+=log(i+1)
    if chk:return 1
    if 1 in a:return 0
    a=[x//2 for x in a]
    return slv(n,a)*2
print(slv(n,a))

Submission status: Accepted

Solution code:
N = int(input())
S = ''.join([str(int(d) - 1) for d in input()])

def solve01(s):
    "solve the problem when 's' consists of 0 or 1"
    ans = 0
    for k, d in enumerate(s):
        if k & (N - 1) == k:
            ans ^= int(d)
    return ans      

if '1' in S: # 0 or 1
    print(solve01(S.replace('2', '0')))
else: # 0 or 2
    print(solve01(S.replace('2', '1')) * 2)

Submission status: Accepted

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


def solve(n, s):
    sub = [int(s[i])-1 for i in range(n)]
    
    table = [0]*(n+1)
    p = 2
    for i in range(len(bin(n))-1):
        for j in range(p, n+1, p):
            table[j] += 1
        p *= 2
    
    for i in range(n):
        table[i+1] += table[i]
    
    ans = 0
    for i in range(n):
        if sub[i]%2:
            judge = table[n-1]-table[n-1-i]-table[i]
            if not judge:
                ans += 1
    
    
    if ans%2:
        res = 1
    else:
        if 1 in sub:
            res = 0
        else:
            res = 0
            for i in range(n):
                if sub[i]:
                    judge = table[n-1]-table[n-1-i]-table[i]
                    if not judge:
                        res += 1
            return res%2*2
    
    return res
    
    
def main():
    n = int(input())
    s = input()
    
    ans = solve(n, s)
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
s=input()
A=[int(i)-1 for i in s]

RUI2=[pow(2,i) for i in range(21)]
import bisect as bi
@lru_cache(maxsize=10**10)
def tan(n):
    if n==0:return [1]
    if n==1:return [1,1]
    if n==2:return [1,0,1]
    i= bi.bisect_right(RUI2,n)-1
    return tan(n-pow(2,i)) + [0]*(pow(2,i+1)-n-1) + tan(n-pow(2,i))


# for i in range(n-1):
#     if A[i]==A[i+1]: A[i]=0
#     elif (A[i]^A[i+1])&1 : A[i]=1
#     else:A[i]=2
# for i in range(n-2):
#     if (A[i]^A[i+1])&1 : A[i]=1
#     else:A[i]=0

# print(A[:-2],tan(n-3))
if A.count(1)!=0:
    A=[i%2!=1 for i in A]
    a=[i&j for i,j in zip(A,tan(n-1))]
    # print(a)
    print(1 if sum(a)%2==1 else 0)
else:
    a=[(i//2)&j for i,j in zip(A,tan(n-1))]
    #print(a,tan(4))
    print(2 if sum(a)%2==1 else 0)

Submission status: Accepted

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

fac2 = [0] * (n+1)
i = 2
while(i <= n ):
    for j in range(i,n+1,i):
        fac2[j] += 1
    i *= 2

for i in range(1,n+1):
    fac2[i] += fac2[i-1]

def calc(x):
    len_x = len(x)
    res = 0
    for i,xi in enumerate(x):
        if(fac2[len_x-1] - fac2[len_x-1-i] - fac2[i] > 0):
            continue
        res = res ^ xi
    return res

if(a.count('2')==0):
    x = []
    for ai in a:
        x.append(int(ai)//2)
    res = calc(x)
    if(res==0):
        print(0)
    else:
        print(2)
else:
    x = []
    for ai in a:
        x.append( (int(ai)-1) % 2)
    res = calc(x)
    print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, list(input())[: -1]))
res = 0
rres = 0
for i in range(N):
  t = (((N - 1) & i) & i) == i
  res ^= t * a[i] % 2
  rres ^= t * (a[i] // 2) % 2
if (2 in a) and res == 0: print(0)
elif res == 1: print(1)
else:
  if rres: print(2)
  else: print(0)

Submission status: Accepted

Solution code:
n=int(input())
def f(n,r):
    return n==r|(n-r)
s=list(map(int,list(input())))
b=[]
for i in range(n-1):b.append(abs(s[i]-s[i+1]))
if (0 in b and len(set(b))==2) or len(set(b))==1:
    ans=0
    anss=0
    for i in range(n-1):
        if b[i]:
            anss=b[i]
            ans+=f(n-2,i)
    if ans%2==0:
        print(0)
    else:
        print(anss)
    quit()
ans=0
for i in range(n-1):
    if b[i]%2==1:
        anss=b[i]
        ans+=f(n-2,i)
if ans%2==0:
    print(0)
else:
    print(1)

Submission status: Accepted

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

N = int(input())
a = list(map(int, list(input()[:-1])))
a = list(map(lambda x: x-1, a))
p = [0]*N

for i in range(1, N):
    t = i
    
    while t%2==0:
        t //= 2
        p[i] += 1

for i in range(1, N):
    p[i] += p[i-1]

X = 0

for i in range(N):
    if a[i]==1 and p[N-1-i]+p[i]==p[N-1]:
        X += 1

if X%2==1:
    print(1)
else:
    if 1 in a:
        print(0)
    else:
        b = [ai//2 for ai in a]
        X = 0
        
        for i in range(N):
            if b[i]==1 and p[N-1-i]+p[i]==p[N-1]:
                X += 1
        
        print(2*(X%2))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
from copy import deepcopy



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 2


n = I()
s = S()
l = len(s)
L = []
one_cnt = 0
for i in range(l - 1):
    ret = abs(int(s[i]) - int(s[i + 1]))
    L += [ret]
    if ret == 1:
        one_cnt += 1

m = 0
for j in range(l - 1):
    m += int(l - 2 & j == j) * L[j]
    m %= 2

if m % 2:
    print(1)
    exit()
else:
    if one_cnt:
        print(0)
    else:
        L = [k // 2 for k in L]
        ret2 = 0
        for jj in range(l - 1):
            ret2 += int(l - 2 & jj == jj) * L[jj]
            ret2 %= 2
        if ret2:
            print(2)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int ,input().strip()))

A = [abs(x-y) for x,y in zip(A,A[1:])]
n = len(A)
# Lucas
coef = [((n-1)&k)==k for k in range(n)]
if 1 in A:
    B = [x % 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))
else:
    B = [x // 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))*2

print(ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
N = int(input())
A = list(input().rstrip())

def two_num(x):
    res = 0
    while x%2==0:
        x //= 2
        res += 1
    return res

C_twos = [0]*N
for i in range(1, N):
    res = C_twos[i-1] + two_num(N-i) - two_num(i)
    C_twos[i] = res

if '2' in A:
    ans = 0
    for i in range(N):
        ans ^= (int(A[i])-1)&1 * (C_twos[i]==0)
    print(ans)
else:
    ans = 0
    for i in range(N):
        ans ^= (int(A[i])-1)//2 * (C_twos[i]==0)
    print(ans*2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input()))
a = [e - 1 for e in a]


def cnt_div2(x):
    ret = 0
    while x % 2 == 0 and x != 0:
        x //= 2
        ret += 1

    return ret


now = 0
cnt = [0]
for i in range(1, n):
    now += cnt_div2(n - i)
    now -= cnt_div2(i)
    cnt.append(now)

div2 = [e == 0 for e in cnt]


def f(li):
    ret = 0
    for e1, e2 in zip(li, div2):
        e1 %= 2
        ret ^= e1 * e2

    return ret


if f(a):
    ans = 1

elif 1 in a:
    ans = 0

else:
    a = [e // 2 for e in a]
    if f(a):
        ans = 2
    else:
        ans = 0

print(ans)

Submission status: Accepted

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

div=[0]*(n+1)
for i in range(1,n+1):
  div[i]+=div[i-1]
  x=i
  while not x&1:
    x>>=1
    div[i]+=1

XOR=0;one=False
for i in range(n):
  one|=a[i]==1
  if div[n-1]<=div[i]+div[n-1-i]:
    XOR^=a[i]
if XOR&1:print(1)
elif one:print(0)
elif XOR&2:print(2)
else:print(0)

Submission status: Accepted

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

div=[0]*(n+1)
for i in range(1,n+1):
  div[i]+=div[i-1]
  x=i
  while not x&1:
    x>>=1
    div[i]+=1

XOR=0
for i in range(n):
  if div[n-1]<=div[i]+div[n-1-i]:
    XOR^=a[i]
if XOR&1:
  print(1)
  exit(0)


for i in a:
  if i==1:
    print(0)
    exit(0)

XOR=0
for i in range(n):
  if div[n-1]<=div[i]+div[n-1-i]:
    XOR^=a[i]>>1
if XOR&1:
  print(2)
  exit(0)
print(0)

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
s=list(map(int,SI()))
if n==1:
    print(s[0])
    sys.exit()

def divi2(x):
    if x%2==1:
        return 0
    else:
        count=0
        while x%2==0:
            x//=2
            count+=1
        return count
#print(divi2(24))
pw2=[0 for i in range(n-1)]
for i in range(n-1):
    if i%2==1:
        pw2[i]=divi2(i+1)
#print(pw2)
#print(s)
cmbnk2=[0 for i in range(n)]
for i in range(n-1):
    cmbnk2[i+1]=cmbnk2[i]+pw2[n-2-i]-pw2[i]
#print(cmbnk2)
ans=0
'''if (s.count(1)==1 and not 2 in s ) or (s.count(3)==1 and not 2 in s ):
    ans=2
    print(ans)
    sys.exit()'''
if not 2 in s:
    for i in range(n):
        s[i]=(s[i]-1)//2
    for i in range(n):
        if cmbnk2[i]==0:
            ans+=s[i]%2
    if ans%2==0:
        print(0)
    else:
        print(2)
    sys.exit()
    
        
else:
    for i in range(n):
        if cmbnk2[i]==0:
            ans+=s[i]%2
            #print(s[i]%2)
        #print(cmbnk2[i]%2+1)
        #print(s[i])
print(ans%2)

Submission status: Accepted

Solution code:
f2=[0]*10**6
p2=2
while p2<10**6:
    for i in range(p2,10**6,p2):
        f2[i]+=1
    p2*=2
for i in range(1,10**6):
    f2[i]+=f2[i-1]

n=int(input())
s=input()

p = '2' if '2' in s else '3'

ans=0
for i,c in enumerate(s):
    if c==p:
        ans += 0 if f2[n-1]-f2[i]-f2[n-1-i] else 1
print(int(p)-1 if ans%2==1 else 0)

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#editorial参照

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

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

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

else:
    print(0)

Submission status: Accepted

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 = list(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: Accepted

Solution code:
n = int(input())
a = list(map(int, input()))
l = [0] * (n - 1)
for i in range(n - 1):
    l[i] = abs(a[i + 1] - a[i])
n -= 1
if 1 in l:
    for i in range(n):
        if l[i] == 2:
            l[i] = 0
ans = 0
for i, x in enumerate(l):
    if not (i ^ (n - 1)) & i:
        ans ^= x
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    a = input()
    nl = []
    
    for num in a:
        num = int(num)
        nl.append(num-1)

    if 1 in nl:
        cnt = 0
        for i,num in enumerate(nl):
            cnt += num*(N-1 == i|((N-1)-i))
        print(cnt%2)
    else:
        for i in range(N):
            nl[i] //= 2
        cnt = 0
        for i,num in enumerate(nl):
            cnt += num*(N-1 == i|((N-1)-i))
        print((cnt%2)*2)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def fact_mod2(n,r):
  if n==(r|(n-r)):
    return 1
  else:
    return 0

alist=[]
for s in slist:
  alist.append(int(s)-1)  
#print(alist)

parity=0
for i in range(N):
  parity+=fact_mod2(N-1,i)*alist[i]
#print(parity)

if parity%2==1:
  print(1)
else:
  if 1 in alist:
    print(0)
  else:
    for i in range(N):
      alist[i]//=2
    
    parity=0
    for i in range(N):
      parity+=fact_mod2(N-1,i)*alist[i]
    if parity%2==1:
      print(2)
    else:
      print(0)

Submission status: Accepted

Solution code:

def twos_in_factorial(n):
    return n - bin(n).count('1')


def parity_of_nCr(n, i):
    """ if odd, return False. """
    f = twos_in_factorial
    return f(n) - f(n-i) - f(i) > 0


if __name__ == "__main__":
    n = int(input())
    nums = list(map(lambda x: int(x) - 1, input().strip()))
    no_one = False
    if 1 not in nums:
        nums = [num // 2 for num in nums]
        no_one = True

    is_odd = False
    for i, num in enumerate(nums):
        if not parity_of_nCr(n-1, i) and num & 1:
            is_odd ^= 1

    if not is_odd:
        print(0)
    else:
        print(1 << no_one)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = input()
a = list(map(lambda x:int(x)-1, list(a)))
b = [0 if i % 2 == 0 else i for i in a]
cnt = 0
for i in range(n):
    if b[i] % 2:
        if (n-1) & i == i:
            cnt += 1
if cnt % 2:
    print(1)
else:
    if 1 in b:
        print(0)
    else:
        c = [i // 2 if i % 2 == 0 else i for i in a]
        cnt = 0
        for i in range(n):
            if c[i] % 2:
                if (n-1) & i == i:
                    cnt += 1
        if cnt % 2:
            print(2)
        else:
            print(0)

Submission status: Accepted

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))

    n = None
    count = 0
    filtered = []
    for a, cnt in ret:
        if a != n:
            n = a
            count = 0
            filtered.append((n, 0))
        count += cnt
        filtered[-1] = (n, count)
    return filtered

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

# cnt2[n]: n! が 2 で何回割れるか
cnt2 = []
cnt = 0
for n in range(N + 10):
    while n >= 2 and n % 2 == 0:
        n //= 2
        cnt += 1
    cnt2.append(cnt)

# 0, 1, 2 だけにする
A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
# 1が入ってるとき、2は0と同一視できる
if 1 in A:
    for i in range(len(A)):
        if A[i] == 2:
            A[i] = 0
mod = 2 if 1 in A else 4

ans = 0
n = len(A) - 1
for r in range(len(A)):
    cnt = cnt2[len(A) - 1] - cnt2[r] - cnt2[n - r]
    # cnt = math.factorial(n) // math.factorial(r) // math.factorial(n - r)
    if cnt == 0:
        ans += A[r]
        ans %= mod
    # print(n, r, cnt)
print(ans)

Submission status: Accepted

Solution code:
n,a=int(input())-1,list(map(lambda x:int(x)-1,list(input())));b=[i%2for i in a]
def c(x):
 a=0
 for j,i in enumerate(x):a^=(n|j==n)*i
 return a
if c(b):k=1
elif 1in a:k=0
else:k=c([i//2for i in a])*2
print(k)

Submission status: Accepted

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

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

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


main()

Submission status: Accepted

Solution code:
import math

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

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

Submission status: Accepted

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

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

import sys

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

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

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

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

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

if A.count(1):
    print(0)
    exit()

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

Submission status: Accepted

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

b = 1 if 1 in A else 2

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

print(ans)

Submission status: Accepted

Solution code:
import sys

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

if two:
  S &= ~2

print(S)

Submission status: Accepted

Solution code:
import sys

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

if two:
  S &= ~2

print(S)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
l = list(map(lambda x:int(x) - 1, list(ns())))
f = 1
if 1 not in l:
    l = [x//2 for x in l]
    f += 1

def Cmod2(n, r):
    return n&r == r

s = sum(Cmod2(n-1,i)*l[i] for i in range(n)) % 2
print(f*s)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(c)-1 for c in input()]
x = 0
b = 1 if any(a==1 for a in A) else 2
for k,a in enumerate(A):
    p = int(((N-1)&k)==k)
    if p and a^b==0:
        x ^= b
print(x)

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

def include_2(a):
    x = (~a) & (a >> 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
    x |= x >> 1048576
    return x & 1

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

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

Submission status: Accepted

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

def is_combination_odd(n, r):
    _n = n
    _r = r
    is_odd = True
    while _n > 0 and _r > 0:
        if _n % 0b10 < _r % 0b10:
            is_odd = False
            break
        _n >>= 1
        _r >>= 1
    #print('n: %d, r: %d, is_odd: %d' % (n, r, is_odd))
    return is_odd
    
def is_ans_odd(num_str: str) -> bool:
    is_odd = False
    for i, c in enumerate(num_str):
        is_c_odd = int(c) % 2
        is_odd ^= is_combination_odd(len(num_str)-1, i) & is_c_odd
    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: Accepted

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

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

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

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

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


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