Problem:


Score : 700 points

Problem Statement

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

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

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

Find x_{N,1}.

Constraints

2 \leq N \leq 10^6

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

Input

Input is given from Standard Input in the following format:

N
a_1a_2\ldotsa_N

Output

Print x_{N,1}.

Sample Input 1

4
1231

Sample Output 1

1

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

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

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

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

Sample Input 2

10
2311312312

Sample Output 2

0



Sample input:
4
1231


Sample output:
1

Submission status: Accepted

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

def mod2_pascal(n):
    res = []
    for r in range(n+1):
        res.append(1 if n == (r | (n-r)) else 0)
    return res

b = []

if N >= 3:
    for i in range(N-1):
        b.append(abs(a[i]-a[i+1]))
    mod2_line = mod2_pascal(N-2)
    ans = 0
    for i in range(N-1):
        if mod2_line[i] == 1:
            ans += b[i]
    if b.count(0) == N-1 - b.count(2):
        b_divided_by_2 = list(map(lambda x:x//2, b))
        for i in range(N - 1):
            if mod2_line[i] == 1:
                ans += b_divided_by_2[i]
        if ans%2 == 1:
            print(2)
        else:
            print(0)
    else:
        print(ans % 2)

else:
    print(abs(a[1]-a[0]))

Submission status: Accepted

Solution code:
import math
n=int(input())
alist=input()
blist=[]
swit=0
for i in range(n-1):
    now=abs(int(alist[i+1])-int(alist[i]))
    if now==1:
        swit=1
    blist.append(now)
if swit==1:
    for i in range(n-1):
        if blist[i]==2:
            blist[i]=0
else:
    for i in range(n-1):
        if blist[i]==2:
            blist[i]=1
dekai=100
while len(blist)>1:
    clist=[]
    dekai=math.floor(math.log(len(blist),2))
    katamari=2**dekai
    kosu=len(blist)-katamari+1
    nanko=0
    for i in range(katamari):
        if blist[i]==1:
            nanko+=1
    clist.append(nanko%2)
    for i in range(kosu-1):
        nanko+=blist[katamari+i]-blist[i]
        clist.append(nanko%2)
    blist=clist

if swit==1:
    print(blist[0])
else:
    print(blist[0]*2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

N = int(input())
A = list(map(int,input()))
X = 2 in A

while len(A) > 1:
    if len(A) % 2 == 1:
        for i in range(len(A)-1):
            A[i] = abs(A[i]-A[i+1])
        A.pop()
    B = []
    for i in range(len(A)//2):
        B.append(abs(A[i*2]-A[i*2+1]))
    A = B[:]

if X:
    A[0] %= 2
print(A[0])

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, list(input())))
 
while N != 0:
	digit = 1
	while digit < N // 2:
		digit *= 2
 
	x = []
	for i in range(digit, N):
		x.append(abs(a[i - digit] - a[i]))
 
	a = x
	N -= digit
	if len(x) == 1:
		break
 
print(a[0])

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    iS = input().rstrip()

    S = []
    for i in range(N-1):
        S.append(abs(int(iS[i])-int(iS[i+1])))
    N -= 1

    f = FactorialUtils(N)
    n1 = n2 = 0
    for i in range(N):
        t = f.choose(N-1,i)
        #print(t,S[i])
        if S[i] == 1: n1 += t
        elif S[i] == 2: n2 += t
    if n1&1 and n2&1: print(1)
    elif n1&1: print(1)
    elif n2&1 and n1==0: print(2)
    else: print(0)
    #print(n1,n2)

class FactorialUtils:
    def __init__(self, n):
        self.fac = [1] * (n+1)
        for i in range(2, n+1): self.fac[i] = self.fac[i-1] + (i&(-i)).bit_length()

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return 2 if (self.fac[n] - self.fac[n-r] - self.fac[r]) > 0 else 1

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input()))
if N == 2:
    print(abs(a[0]-a[1]))
    exit()
a1 = [abs(a[i]-a[i+1]) for i in range(N-1)]
if 1 in a1:
    s = 0
    for i in range(len(a1)):
        if ((len(a1)-1) | i) == (len(a1)-1):
            s += a1[i] % 2
    print(s % 2)
else:
    s = 0
    for i in range(len(a1)):
        if ((len(a1)-1) | i) == (len(a1)-1):
            s += a1[i] // 2
    print((s % 2) * 2)

Submission status: Accepted

Solution code:
N = int(input())
A = input()
b = []
for i in range(N-1):
    b.append(abs(int(A[i])-int(A[i+1])))
S = 0
p = 0
for i in range(N-1):
    if p == 0:
        S += b[i]
    n = N - 2 - i
    k = i + 1
    if n == 0:
        break
    else:
        while n % 2 == 0:
            p += 1
            n //= 2
        while k % 2 == 0:
            p -= 1
            k //= 2

if S % 2:
    print(1)
else:
    for i in range(N-1):
        if b[i] == 1:
            print(0)
            exit()
    if (S // 2) % 2:
        print(2)
    else:
        print(0)

Submission status: Accepted

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

def myc(n):
    ret = 0
    while n % 2 == 0:
        ret += 1
        n //= 2
    return ret

def func(c):
    odd = 0
    count = 0
    if a[0] == c:
        count += 1
    if a[-1] == c:
        count += 1
    for i in range(1, N // 2):
        odd += myc(N-i) - myc(i)
        if a[i] == c and odd == 0:
            count += 1
        if a[-i-1] == c and odd == 0:
            count += 1
    if N % 2 == 1:
        if a[N // 2] == c and odd + myc(N // 2 + 1) - myc(N // 2) == 0:
            count += 1
    return count % 2 == 0

if '2' in a:
    if func('2'):
        print(0)
    else:
        print(1)
else:
    if func('3'):
        print(0)
    else:
        print(2)

Submission status: Accepted

Solution code:
N=10**6
l=[0]*(N+1)
for i in range(1,N+1):
    c=0
    x=i
    while x%2==0:
        c+=1
        x//=2
    l[i]=c
for i in range(N):
    l[i+1]+=l[i]
def nCr(n,r):
    if l[n]>l[r]+l[n-r]:
        return 0
    else:
        return 1
n=int(input())
A=list(input())
for i in range(n):
  	A[i]=int(A[i])
AA=[0]*(n-1)
flag=0
for i in range(n-1):
    AA[i]=abs(A[i+1]-A[i])
    if AA[i]==1:
        flag=1
if flag==0:
    for i in range(n-1):
        AA[i]//=2
ans=0
for i in range(n-1):
    ans=(ans+nCr(n-2,i)*AA[i])%2
if flag==1:
    print(ans)
else:
    print(ans*2)

Submission status: Accepted

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

am = [a[i] % 2 for i in range(n)]

tmp = 0
ans = am[0] % 2

for i in range(1, n):
    ind = 0
    k = (n-i) & -(n-i)
    while k > 1:
        k = k // 2
        ind += 1
    kk = i & -i
    while kk > 1:
        kk = kk // 2
        ind -= 1
    tmp += ind
    if tmp == 0:
        ans += am[i]
        ans %= 2

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

# あとは0か2かの判定！


if 1 in a:
    print(0)
else:
    b = [1 if a[i] == 2 else 0 for i in range(n)]
    tmp = 0
    ans = b[0] % 2
    for i in range(1, n):
        ind = 0
        k = (n-i) & -(n-i)
        while k > 1:
            k = k // 2
            ind += 1
        kk = i & -i
        while kk > 1:
            kk = kk // 2
            ind -= 1
        tmp += ind
        if tmp == 0:
            ans += b[i]
            ans %= 2
    if ans == 1:
        print(2)
    else:
        print(0)

Submission status: Accepted

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

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

def comb(k):
    left = cnt[n-1]
    right = cnt[k]+cnt[n-1-k]
    return left-right == 0

f = 1 in a
if f:
    a = [int(i==1) for i in a]
else:
    a = [int(i==2) for i in a]

ans = 0
for i in range(n):
    if comb(i):
        ans += a[i]

ans %= 2
if not f:
    ans *= 2

print(ans)

Submission status: Accepted

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

while N != 0:
	digit = 1
	while digit < N // 2:
		digit *= 2

	x = []
	for i in range(digit, N):
		x.append(abs(a[i - digit] - a[i]))

	a = x
	N -= digit
	if len(x) == 1:
		break

print(a[0])

Submission status: Accepted

Solution code:
def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

N=int(input())
A=input()
A=[int(A[i]) for i in range(0,N)]
X=[abs(A[i]-A[i+1]) for i in range(0,N-1)]


cmb=[0 for i in range(0,N-1)]
cmb[0]=0
for i in range(1,N-1):
    cmb[i]=cmb[i-1]+ord(2,N-2-(i-1))-ord(2,i)
data=[0 for i in range(0,N-1)]
for i in range(0,N-1):
    if cmb[i]>0:
        data[i]=0
    else:
        data[i]=1

s=0
for i in range(0,N-1):
    s=(s+X[i]*data[i])%2
if s==1:
    print(1)
else:
    if 1 in X:
        print(0)
    else:
        X=[X[i]//2 for i in range(0,N-1)]
        s=0
        for i in range(0,N-1):
            s=(s+X[i]*data[i])%2
        if s==1:
            print(2)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9+7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# nC0~nCn odd or even
def nCk(n):
    num = [0]*(n+1)
    for i in range(n+1):
        now = 2
        while now <= i:
            num[i] += i//now
            now *= 2
    #cumnum = [num[0]]
    #for i in range(1,n+1):
    #    cumnum.append(cumnum[-1]+num[i])
    ret = [0]*(n+1)
    for i in range(n+1):
        if num[n] > num[i]+num[n-i]:
            ret[i] = 0
        else:
            ret[i] = 1
    return ret

N = I()

A = list(input())
a = [0]*N
for i in range(N):
    a[i] = int(A[i])

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

flag = False
for i in range(N-1):
    if b[i] == 1:
        flag = True
        break

nlist = nCk(N-2)

ans = 0
if not flag:
    for i in range(N-1):
        ans += nlist[i]*b[i]
        ans %= 4
    print(ans)
    #raise(ValueError)
else:
    for i in range(N-1):
        ans += nlist[i]*(b[i]%2)
        ans %= 2
    print(ans)
    #raise(ValueError)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = input().rstrip('\n')
    A = [int(a) for a in A]

    A = [abs(A[i+1] - A[i]) for i in range(N-1)]
    flg = 1
    if 1 not in A:
        flg = 2
        A = [a // 2 for a in A]
    else:
        A = [a % 2 for a in A]
    idx = []
    N -= 1
    for j in range(N.bit_length()):
        if N>>j&1:
            M = 2**j
            X = N%(M*2)
            if not idx:
                idx = list(range(M))
            else:
                idx_new = [X-1 - x for x in idx]
                idx.extend(idx_new)
    ans = 0
    #print(A)
    #print(idx)
    for i in idx:
        ans ^= A[i]
    print(ans * flg)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N=I()
    a2=input()
    a=[]
    for i in range(len(a2)):
        a.append(int(a2[i]))
    
    def calc(L):
        L1=list(L)
        nL=len(L)
        if nL%2==1 or nL<=5000:
            for i in range(nL-1):
                L1[i]=abs(L[i]-L[i+1])
            L1.pop()
                
            return L1
        else:
            L2=[]
            for i in range(0,nL,2):
                L2.append(abs(L[i]-L[i+1]))
            return L2

    while len(a)!=1:
        a=calc(a)    
    
    print(a[0])
                
        
    
main()

Submission status: Accepted

Solution code:
import sys

N = int(input())
S = input().strip()
ss = []
for c in S:
    ss.append(int(c))
if N == 2:
    print(abs(ss[0]-ss[1]))
    sys.exit()

X = []
X2 = []
fff = 0
for i in range(N-1):
    c = abs(ss[i] - ss[i+1])
    X.append(c%2)
    X2.append((c//2)%2)
    if c == 1:
        fff = 1


N=N-2

i = 0
Y = []
while N:
    if N%2:
        Y.append(i)
    i += 1
    N=N//2

C = [0]
for y in Y[::-1]:
    y = 2**y
#    print(y)
    tmp = []
    for c in C:
        tmp.append(c+y)
    for t in tmp:
        C.append(t)
r = 0
r2 = 0
for c in C:
    r = r^X[c]
    r2 = r2^X2[c]
if fff:
    print(r)
else:
    print(r2*2)

Submission status: Accepted

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

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

def next(A):
    B=[]
    for i in range(1,len(A)):
        B.append(abs(A[i]-A[i-1]))
    return B

A=next(A)

if len(A)<=3:
    while len(A)>1:
        A=next(A)
    print(A[0])
    sys.exit()

def in2(x):
    if x==0:
        return 0
    ANS=0
    while x%2==0:
        ANS+=1
        x//=2
    return ANS


if not (1 in A):
    LEN=len(A)
    SUM=0
    COMBI=0

    for i in range(LEN):
        if COMBI==0:
            SUM+=A[i]//2

        COMBI=COMBI+in2(LEN-1-i)-in2(i+1)

    if SUM%2==1:
        print(2)
    else:
        print(0)
else:
    LEN=len(A)
    SUM=0
    COMBI=0

    for i in range(LEN):
        if COMBI==0:
            SUM+=A[i]

        COMBI=COMBI+in2(LEN-1-i)-in2(i+1)

    if SUM%2==1:
        print(1)
    else:
        print(0)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import random
input = sys.stdin.readline

n = int(input())
s = input().rstrip()
a = [int(ch) for ch in s]
# a = [random.randrange(0,3) for _ in range(12)]

def naive(a):
    c = a[:]
    while len(c) > 1:
        b = []
        for c1, c2 in zip(c, c[1:]):
            b.append(abs(c1 - c2))
        c = b[:]
    return c[0]

def solve(a):
    c = a[:]
    while len(c) > 1:
        b = []
        if len(c) % 2 == 0:
            for c1, c2 in zip(c[::2], c[1::2]):
                b.append(abs(c1 - c2))
        else:
            for c1, c2 in zip(c, c[1:]):
                b.append(abs(c1 - c2))
        c = b[:]
    return c[0]

b = []
for a1, a2 in zip(a, a[1:]):
    b.append(abs(a1 - a2))
if 1 not in b:
    tmp = []
    for item in b:
        if item == 2:
            tmp.append(1)
        else:
            tmp.append(0)
    ret = solve(tmp)
    if ret == 1:
        print(2)
    else:
        print(0)
else:
    tmp = []
    for item in b:
        if item == 2:
            tmp.append(0)
        else:
            tmp.append(item)
    ret = solve(tmp)
    print(ret)

Submission status: Accepted

Solution code:
N=int(input())-1
a=input()
l=[None]*N
for i in range(N):
    l[i]=abs(int(a[i+1])-int(a[i]))
for i in range(19,0,-1):
    if N>2**i:
        t=2**i
        N-=t
        lb=[None]*N
        for i in range(N):
            if l[i+t//2]==1 and l[i]+l[i+t]==2:
                lb[i]=0
            else:
                lb[i]=abs(l[i]-l[i+t])
        l=lb
if len(l)==1:
    print(l[0])
else:
    print(abs(l[0]-l[1]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def pr2(x):
  ret = 0
  while x%2 == 0:
    ret += 1
    x //= 2
  return ret
n = int(input())
s = input()
x = []
flg = 0
if s.count("2") >= 1:
  for i in range(n-1):
    t = abs(int(s[i+1])-int(s[i]))
    x.append(t%2)
else:
  flg = 1
  for i in range(n-1):
    t = abs(int(s[i+1])-int(s[i]))
    x.append(t//2)
n -= 1
num2 = 0
ans = 0
for i in range(n):
  if i == 0:
    ans += x[i]
    continue
  num2 += pr2(n-i)-pr2(i)
  if num2>0:
    continue
  else:
    ans += x[i]
if ans%2:
  print(flg+1)
else:
  print(0)

Submission status: Accepted

Solution code:
import sys
from itertools import product
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().strip()))
A1 = [a%2 for a in A]
for i in range(31, -1, -1):
    if (1<<i) & len(A1):
        k = 1<<i
        B = []
        B.append(sum(A1[:k])%2)
        for j in range(k, len(A1)):
            B.append((B[-1] + A1[j] - A1[j-k])%2)
        A1 = B[:]
    if (1<<i) & len(A1):
        k = 1<<i
        B = []
        B.append(sum(A1[:k])%2)
        for j in range(k, len(A1)):
            B.append((B[-1] + A1[j] - A1[j-k])%2)
        A1 = B[:]
pari = A1[0]
if pari == 1:
    ans = 1
else:
    if 2 in A:
        ans = 0
    else:
        A2 = [abs(a2-a1)//2 for a1, a2 in zip(A, A[1:])]
        N2 = len(A2)
        for i in range(31, -1, -1):
            if (1<<i) & len(A2):
                k = 1<<i
                B = []
                B.append(sum(A2[:k])%2)
                for j in range(k, len(A2)):
                    B.append((B[-1] + A2[j] - A2[j-k])%2)
                A2 = B[:]
            if (1<<i) & len(A2):
                k = 1<<i
                B = []
                B.append(sum(A2[:k])%2)
                for j in range(k, len(A2)):
                    B.append((B[-1] + A2[j] - A2[j-k])%2)
                A2 = B[:]
        
        if A2[0] == 0:
            ans = 0
        else:
            ans = 2

print(ans)

Submission status: Accepted

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

# mod = 2
# l = 10**6 + 3

# M = [1]  # i!のmod
# m = 1
# for i in range(1, l):
#     m = (m * i) % mod
#     M.append(m)

# def pow(x, y, mod):  # x**y の mod を返す関数
#     ans = 1
#     while y > 0:
#         if y % 2 == 1:
#             ans = (ans * x) % mod
#         x = (x**2) % mod
#         y //= 2
#     return ans

# def inv(x, mod):  # x の mod での逆元を返す関数
#     return pow(x, mod-2, mod)

# # print(inv(8,13))

# MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
# for i in range(l-2, -1, -1):
#     MI[i] = MI[i+1] * (i+1) % mod

# def C(x, y):  # コンビネーション
#     if y < 0 or y > x:
#         return 0
#     elif x > l:  # O(min(y, x-y))
#         y = min(y, x-y)
#         ans = 1
#         for i in range(x, x-y, -1):
#             ans = (ans * i) % mod
#         return (ans * MI[y]) % mod
#     else:  # O(1)
#         ans = M[x]
#         ans = (ans * MI[y]) % mod
#         return (ans * MI[x-y]) % mod


# print(C(3,2))
ans = 0
# print(s)
if s.count("2") == 0:
    # print(s)
    for i in range(n):
        if s[i] == "3":
            # ans += C(n-1, i)%2
            if (n-1)&i == i:
                ans += 1
    # print(ans)
    print(2 * (ans%2))
else:
    for i in range(n):
        if s[i] == "2":
            # ans += C(n-1, i)%2
            if (n-1)&i == i:
                ans += 1
    print(ans%2)

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 5 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)



#a = list(map(int, input().split()))

n = int(input())
s = input()
a = []

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

non1 = 1
for i in range(n):
    a.append(int(s[i])-1)
    if(a[i]==1):
        non1 = 0
total=0
#print("n",non1)
if(non1==0):
    for i in range(n):
        total += is2(n-1,i)*(a[i]%2)
    print(total%2)
               
else:
    for i in range(n):
        total += is2(n-1,i)*(a[i]//2)
    print((total%2)*2)

Submission status: Accepted

Solution code:
def kezl(xlist):
    lenx=len(xlist)
    news=[]
    for i in range(lenx-1):
        news.append(abs(xlist[i+1]-xlist[i]))
    return news

flist=[]

import math
n=int(input())
alist=input()
blist=[]
swit=0
for i in range(n-1):
    now=abs(int(alist[i+1])-int(alist[i]))
    if now==1:
        swit=1
    blist.append(now)
#print(blist)
if swit==1:
    for i in range(n-1):
        if blist[i]==2:
            blist[i]=0
    #print(blist)
    dekai=100
    while len(blist)>1:
        clist=[]
        dekai=math.floor(math.log(len(blist),2))
        katamari=2**dekai
        kosu=len(blist)-katamari+1
        nanko=0
        for i in range(katamari):
            if blist[i]==1:
                nanko+=1
        clist.append(nanko%2)
        for i in range(kosu-1):
            nanko+=blist[katamari+i]-blist[i]
            clist.append(nanko%2)
        blist=clist
        #print(blist)
    print(blist[0])
else:
    for i in range(n-1):
        if blist[i]==2:
            blist[i]=1
    #print(blist)
    dekai=100
    while len(blist)>1:
        clist=[]
        dekai=math.floor(math.log(len(blist),2))
        katamari=2**dekai
        kosu=len(blist)-katamari+1
        nanko=0
        for i in range(katamari):
            if blist[i]==1:
                nanko+=1
        clist.append(nanko%2)
        for i in range(kosu-1):
            nanko+=blist[katamari+i]-blist[i]
            clist.append(nanko%2)
        blist=clist
        #print(blist)
    print(blist[0]*2)

Submission status: Accepted

Solution code:
def pascal_parity(N):
    if N & -N == N:
        return [1] * N
    else:
        n = N - (1<<(N.bit_length()-1))
        p = pascal_parity(n)
        return p + [0]*(N-2*n) + p

N = int(input())
A = list(map(lambda x: int(x)-1, input()))
P = pascal_parity(N)
if 1 in A:
    if sum(a*p for a,p in zip(A, P)) % 2 == 1:
        print(1)
    else:
        print(0)
else:
    pa = 0
    for p, a in zip(P, A):
        if p==1 and a==2:
            pa += 1
    if pa % 2 == 1:
        print(2)
    else:
        print(0)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
s_ = list(inputS())

s=[]
for i in range(len(s_)-1):
  s.append(abs(int(s_[i])-int(s_[i+1])))
N = N-1

def decode(s):
  #print(s)
  N = len(s)
  news = []
  if set(s)!={0,2}:
    for n in range(20):
      if ((N-1)>>n)&1:
        d = pow(2,n)
        for i in range(N-d):
          news.append(abs(s[i]%2-s[i+d]%2))
        break
  else:
    for n in range(20):
      if ((N-1)>>n)&1:
        d = pow(2,n)
        for i in range(N-d):
          news.append(abs(s[i]-s[i+d]))
        break
    
  return news

  
while len(s) > 1:
  s = decode(s)

print(s[0])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(map(int, read().decode().rstrip()))

U = N + 10
fact_ord = [0] * U
for n in range(1,U):
    fact_ord[n] = fact_ord[n//2] + (n//2)

def solve_01(A):
    ret = 0
    N = len(A) - 1
    comb_ord = [fact_ord[N] - fact_ord[i] - fact_ord[N-i] for i in range(N+1)]
    return sum(x * (y==0) for x,y in zip(A, comb_ord)) % 2

def solve(A):
    if len(A) == 1:
        return A[0]
    A = [abs(x - y) for x,y in zip(A, A[1:])]
    if all(x != 1 for x in A):
        B = [x // 2 for x in A]
        return 2 * solve_01(B)
    # 1 が存在
    A = [x % 2 for x in A]
    return solve_01(A)

print(solve(A))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input()]
def pascal_parity(n):
    def cnt2(m):
        a = m & -m
        return a.bit_length() - 1
    S = [0] * (n+1)
    for i in range(1, n):
        S[i] = S[i-1] + cnt2(n+1-i) - cnt2(i)
    return [1 if s == 0 else 0 for s in S]

def calc(L):
    return [abs(L[i] - L[i-1]) for i in range(1, len(L))]

def calc_all(L):
    for i in range(len(L)-1):
        L = calc(L)
    return L[0]

if N <= 5:
    print(calc_all(A))
else:
    A = calc(A)
    pp = pascal_parity(N-2)
    s = sum([a * pp[i] for i, a in enumerate(A)])
    if 1 in A:
        print(s % 2)
    else:
        print(s % 4)

Submission status: Accepted

Solution code:
n = int(input())
a = input()
b = []
att = 1
for i in range(n):
  b.append(int(a[i])-1)
#print(b)
for i in range(n):
  if b[i] % 2 == 1:
    break
else:
  att = 2
  for i in range(n):
    b[i] //= 2
for i in range(n):
  if b[i] == 2:
    b[i] = 0
#print(b)
pre = [0 for _ in range(10**6)]
now = 2
while now < 10**6 + 5:
  for k in range(10**6):
    try:
      pre[k*now] += 1
    except:
      now *= 2
      break
#print(pre)
nm = [0]
for i in range(1,n):
  nm.append(nm[-1]-pre[i]+pre[n-i])
for i in range(n):
  if nm[i]:
    nm[i] = 0
  else:
    nm[i] = 1
#print(nm)
ans = 0
for i in range(n):
  ans ^= b[i]*nm[i]
print(ans*att)

Submission status: Accepted

Solution code:

def solve_base(n, a_list):
    # 2 not in a_list
    # odd or even
    factorial_count_2 = [0] * n
    for i in range(1, n):
        p = i
        cnt = 0
        while p % 2 == 0:
            p = p // 2
            cnt += 1
        factorial_count_2[i] = factorial_count_2[i - 1] + cnt

    mod_2 = 0
    for i in range(n):
        if factorial_count_2[n - 1] == factorial_count_2[i] + factorial_count_2[n - 1 - i]:
            mod_2 += a_list[i] % 2
            mod_2 %= 2

    return mod_2


def solve(n, a_list):
    if 2 in a_list:
        return solve_base(n, a_list)
    else:
        return 2 * solve_base(n - 1, [abs(a_list[i] - a_list[i + 1]) // 2 for i in range(n - 1)])


def main():
    n = int(input())
    a_list = list(map(int, list(input())))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 2, 3, 1]) == 1
    assert solve(10, [2, 3, 1, 1, 3, 1, 2, 3, 1, 2]) == 0
    # assert solve(100, [2] * 100) == 0


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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
n = int(input())
a = [int(i) for i in input()]

n -= 1
d = [abs(i-j) for i,j in zip(a,a[1:])]

p2 = [0]
for i in range(1,n+2):
    r = p2[-1]
    while i&1==0:
        r += 1
        i >>= 1
    p2.append(r)    

def choose(n,k):
    if p2[n] > p2[k]+p2[n-k]: return 0
    else: return 1

#print([choose(n,k) for k in range(n+1)])

par = sum(choose(n-1,i)*di for i, di in enumerate(d))%2

if par == 1:
    print(1)
else:
    if 1 in d: print(0)
    else:
        d = [di>>1 for di in d]
        par = sum(choose(n-1,i)*di for i, di in enumerate(d))%2
        
        if par == 0:
            print(0)
        else:
            print(2)

Submission status: Runtime Error

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))
a=[i&j for i,j in zip(A[:-2],tan(n-3))]
# print(a)
print(1 if sum(a)%2==1 else 0)

Submission status: Runtime Error

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

def solve(A):
    A = [abs(x-y) for x,y in zip(A,A[1:])]
    n = len(A)
    coef = 1
    for i in range(n-1):
        coef = coef ^ (coef << 1)
    coef = map(int, bin(coef)[2:])
    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]
        coef = [nCr(n-1,i) for i in range(n)]
        ans *= 2
    return ans 

print(solve(A))

Submission status: Runtime Error

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

def x(i, j):
  if i == 1:
    return a[j - 1]
  return abs(x(i - 1, j) - x(i - 1, j + 1))

print(x(N, 1))