Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:
import sys #追加
sys.setrecursionlimit(500*500) #追加

# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def func(dic, n):
  
  if n in dic:
    return dic[n]
  
  if n == 0:
    return 0
  
  t = bin(n)
  tmp = len(t) - len(t.replace('1','' ))

  n2 = n % tmp
    
  dic[n] = 1 + func(dic, n2)
  
  return dic[n]


n = int(input())
x = input()

num1 = len(x.replace('0', ''))

x_rev = list(reversed(x))

array_minus = [-1] * (10**6)
array_plus = [-1] * (10**6)

minus = 0
plus = 0
for i in range(n):
  if x_rev[i] == '0':
    array_minus[i] = 0
    array_plus[i] = 0
  
  else:
    array_minus[i] = pow_k(2, i, num1-1)
    minus += array_minus[i]
    minus %= num1-1
    array_plus[i] = pow_k(2, i, num1+1)
    plus += array_plus[i]
    plus %= num1+1
    
dic = {}
for i in range(n):
  if x[i] == '0':
    tmp = pow_k(2, n-1-i, num1+1) + plus
    tmp %= num1+1
  
  else:
    tmp = minus - array_minus[n-i-1]
    tmp %= num1 -1
    
  print(func(dic, tmp)+1)

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import random
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

# popcount table
popcount = {}
popcount[0] = 0
def gpc(n):
    if n not in popcount:
        popcount[n] = bin(n).count("1")
    return popcount[n]

# mem rec
solutions = {}
def sol(Xk):
    # pc = popcount[Xk]
    pc = gpc(Xk)
    # print("Call {}, {}".format(Xk, pc))
    if Xk == 0:
        solutions[(Xk, 0)] = 0
        return 0
    elif (Xk, pc) in solutions:
        return solutions[Xk, pc]
    else:
        count = 1 + sol(Xk % pc)
        solutions[Xk, pc] = count
        return count

def main():
    from builtins import int, map
    N = int(input())
    X = input()
    
    # 余りが0からN - 1
    Xpc = X.count("1")
    iX = int(X, 2)
    rem_groups = [0] * N
    for k in range(1, N):
        rem_groups[k] = sol(k)

    # ans = [-1] * (N + 1)
    for k in range(N - 1, -1, -1):
        Xk = iX ^ (1 << k)
        Xkpc = Xpc
        if Xk & (1 << k) == (1 << k):
            Xkpc += 1
        else:
            Xkpc -= 1
        if Xk % Xkpc == 0:
            ans = 1
        else:
            ans = 1 + rem_groups[Xk % Xkpc]
        # ans_sol = sol(Xk)
        # print(bin(Xk), Xk, Xkpc, Xk % Xkpc, ans, ans_sol, ans == ans_sol)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
m = []
p = []
# したからi番目を反転
def reverse_x(i,x):
    a = 1<<i
    b = x^a
    return b
def f(n):
    def popcount(n):
        c = bin(n).count("1")
        return c
    count = 0
    if n % popcount(n) in m:
        count = p[m.index(n%popcount(n))]
        n = 0
    else:
        m.append(n % popcount(n))
        while n != 0:
            n = n % popcount(n)
            count += 1
        p.append(count)
    return count
for i in range(N):
    print(f(reverse_x(N-i-1,X)))

Submission status: Runtime Error

Solution code:
n=int(input())

x=input()

def n_pc(n,a):
	bit=bin(n)[2:]
	c=str(bit).count("1")
	#print(c)
	a=a+1
	if n%c!=0:
		return n_pc(n%c,a)
	if n%c==0:
		return a

y=x
for i in range(n):
	a=0
	#print(int(x))
	if x[i]=="0":
		y_list=list(x)
		y_list[i]="1"
		y="".join(y_list)
	if x[i]=="1":
		y_list=list(x)
		y_list[i]="0"
		y="".join(y_list)
	#print(y)
	ans=n_pc(int(y,2),0)
	print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    X = input()
    X = int('0b'+X,0)

    memo = [-1] * (2**(N+5))

    def f(X):
        if memo[X]!=-1:
            return memo[X]
        x = X
        count = 0
        while x>=1:
            if x%2==1:
                count += 1
            x//=2
        if X%count == 0:
            memo[X] = 1
            return memo[X]
        else:
            memo[X] = f(X%count)+1
            return memo[X]

    for i in range(N-1,-1,-1):
        x = X^(1<<i)
        if x==0:
            print(0)
        else:
            print(f(x))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
X = list(input())

def popcount(a):
    cnt = 0
    while True:
        y = bin(a).count("1")
        a %= y
        cnt += 1
        if a == 0:
            print(cnt)
            break

ans = 0
for i in range(len(X)):
    if X[i] == "1":
        X[i] = "0"
        Flag = True
    else:
        X[i] = "1"
        Flag = False
        
    x = "".join(X)
    n = int(x, 2)
    popcount(n)
            
    if Flag is True:
        X[i] = "1"
    else:
        X[i] = "0"

Submission status: Runtime Error

Solution code:
n = int(input())
x = str(input())

xlist = [0] *n
p= [0]*n
ans =  [0] *n

def count(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count



for i in range(n):
    xs = x
    if x[i] == '0':
        xs=x[:i]+'1'+x[i+1:]
        p[i]=1
    else:
        xs=x[:i]+'0'+x[i+1:]
        p[i]=-1
    xlist[i]=xs

i=0
c = count(int(x,2))

for xi in xlist:
    x = int(xi,2)
    if not x==0:
        x=x%(c+p[i])

        a=1
        while not x ==0:
            x = x%count(x)
            a +=1
        ans[i]=a
        i+=1
    else:
        ans[i]=0

for a in ans:
    print(a)

Submission status: Runtime Error

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

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]
    if Xc == 0:
        [print(1) for i in range(N)]
        exit()
    elif Xc == 1:
        d = X.index(1)
        for j in range(N):
            if d == j:
                print(0)
            else:
                print(1)

    ans1 = 0
    ans2 = 0
    for j in range(N):
        if X[j]:
            ans1 += pow(2,N-1-j,Xc+1)
            ans1 %= Xc+1
            ans2 += pow(2,N-1-j,Xc-1)
            ans2 %= Xc-1

    for i in range(N):
        if X[i]:# 1->0
            ans = (ans2 - pow(2,N-1-i,Xc-1)) % (Xc-1)
        else:# 0->1
            ans = (ans1 + pow(2,N-1-i,Xc+1)) % (Xc+1)
        count = 1
        while ans > 0:
            tmp = str(bin(ans)).count('1')
            ans %= tmp
            count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def power(x, n):
    if n == 0: return 1
    value = power(x, int(n / 2))
    value *= value
    if n % 2 == 1: value *= x
    return value

n = int(input())
x = list(input())

number = int(''.join(x), 2)
count = x.count('1')

def f(num, cnt):
    if num == 0:
        return cnt
    popcount = format(num, 'b').count('1')
    return f(num % popcount, cnt+1)

for i in range(n):
    if x[i] == '0':
        m = number + power(2, n-i-1)
        if m:
            print(f(m % (count+1), 1))
        else:
            print(0)
    if x[i] == '1':
        m = number + power(2, n-i-1)
        if m:
            print(f(m % (count-1), 1))
        else:
            print(0)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    X = input()
    X = int('0b'+X,0)

    memo = [-1] * (2**(N+5))

    def f(X):
        if memo[X]!=-1:
            return memo[X]
        x = X
        count = 0
        while x>=1:
            if x%2==1:
                count += 1
            x//=2
        if count==0:
            memo[X]=0
            return memo[X]
        if X%count == 0:
            memo[X] = 1
            return memo[X]
        else:
            memo[X] = f(X%count)+1
            return memo[X]

    for i in range(N-1,-1,-1):
        x = X^(1<<i)
        print(f(x))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
x = str(input())

xlist = [0] *n
p= [0]*n
ans =  [0] *n

def count(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count



for i in range(n):
    xs = x
    if x[i] == '0':
        xs=x[:i]+'1'+x[i+1:]
        p[i]=1
    else:
        xs=x[:i]+'0'+x[i+1:]
        p[i]=-1
    xlist[i]=xs

i=0
c = count(int(x,2))

print(c)
for xi in xlist:
    x = int(xi,2)
    if not x==0:
        x=x%(c+p[i])

        a=1
        while not x ==0:
            x = x%count(x)
            a +=1
        ans[i]=a
        i+=1
    else:
        ans[i]=0

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# coding: utf-8

import sys

sys.setrecursionlimit(10000)


def bi(x, n_digit):
    output = ""
    for i in range(n_digit-1, -1, -1):
        if x >= 2**i:
            x -= 2**i
            output += "1"
        else:
            output += "0"
    return output


def popcount(bi_n):
    output = 0
    for c in bi_n:
        if c == "1":
            output += 1
    return output


def main():
    N = int(input())
    bi_X = input()

    fs = [None] * 20

    def rec(x):
        pop_x = popcount(bi(x, 18))
        r = x % pop_x
        if r == 0:
            return 1
        elif fs[r] is not None:
            return 1 + fs[r]
        else:
            return 1 + rec(r)

    for i in range(1, 20):
        fs[i] = rec(i)
    fs[0] = 0

    pop_X = popcount(bi_X)
    qp = pop_X+1
    qm = pop_X-1

    bi_qp = [None] * N
    bi_qm = [None] * N
    bi_qp[0] = 1 % qp
    bi_qm[0] = 1 % qm
    bi_qp[1] = 2 % qp
    bi_qm[1] = 2 % qm
    for i in range(2, N):
        bi_qp[i] = ((bi_qp[1])*(bi_qp[i-1])) % qp
        bi_qm[i] = ((bi_qm[1])*(bi_qm[i-1])) % qm

    rp = 0
    rm = 0
    for i in range(N):
        p = N-1-i
        coo = int(bi_X[i])
        rp = (rp + (((coo % qp) * bi_qp[p]) % qp)) % qp
        rm = (rm + (((coo % qm) * bi_qm[p]) % qm)) % qm

    for i in range(N):
        if bi_X[i] == "0":
            ri = (rp + bi_qp[N-1-i]) % qp
            if ri < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])
        else:
            ri = (rm - bi_qm[N-1-i]) % qm
            if ri < 20:
                print(1 + fs[ri])
            else:
                pop_ri = popcount(bi(ri, 18))
                print(2 + fs[ri % pop_ri])



main()
# print(main())

Submission status: Runtime Error

Solution code:
import sys #追加
sys.setrecursionlimit(500*500) #追加

# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def func(dic, n):
  
  if n in dic:
    return dic[n]
  
  if n == 0:
    return 0
  
  t = bin(n)
  tmp = len(t) - len(t.replace('1','' ))

  n2 = n % tmp
    
  dic[n] = 1 + func(dic, n2)
  
  return dic[n]


n = int(input())
x = input()

num1 = len(x.replace('0', ''))

x_rev = list(reversed(x))

array_minus = [-1] * n
array_plus = [-1] * n

minus = 0
plus = 0
for i in range(n):
  if x_rev[i] == '0':
    array_minus[i] = 0
    array_plus[i] = 0
  
  else:
    array_minus[i] = pow_k(2, i, num1-1)
    minus += array_minus[i]
    minus %= num1-1
    array_plus[i] = pow_k(2, i, num1+1)
    plus += array_plus[i]
    plus %= num1+1
    
dic = {}
for i in range(n):
  if x[i] == '0':
    tmp = pow_k(2, n-1-i, num1+1) + plus
    tmp %= num1+1
  
  else:
    tmp = minus - array_minus[n-i-1]
    tmp %= num1 -1
    
  print(func(dic, tmp)+1)

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

def f(x):
    c = 0
    while(x):
        x = x%popcount(x)
        c+=1
    return c
n = int(input())
x = int(input(),2)

for i in reversed(range(n)):
    print(f(x ^ (1 << (i))))

Submission status: Runtime Error

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

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]
    if Xc == 0:
        [print(1) for i in range(N)]
        exit()
    elif Xc == 1:
        d = X.index(1)
        for i in range(N):
            if d == i:
                print(0)
            else:
                print(1)

    ans1 = 0
    ans2 = 0
    for j in range(N):
        if X[j]:
            ans1 += pow(2,N-1-j,Xc+1)
            ans1 %= Xc+1
            ans2 += pow(2,N-1-j,Xc-1)
            ans2 %= Xc-1

    for i in range(N):
        if X[i]:# 1->0
            ans = (ans2 - pow(2,N-1-i,Xc-1)) % (Xc-1)
        else:# 0->1
            ans = (ans1 + pow(2,N-1-i,Xc+1)) % (Xc+1)
        count = 1
        while ans > 0:
            tmp = str(bin(ans)).count('1')
            ans %= tmp
            count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    X = input()
    X = int('0b'+X,0)

    memo = [-1] * 5*10**N

    def f(X):
        if memo[X]!=-1:
            return memo[X]
        x = X
        count = 0
        while x>=1:
            if x%2==1:
                count += 1
            x//=2
        if count==0:
            memo[X]=0
            return memo[X]
        if X%count == 0:
            memo[X] = 1
            return memo[X]
        else:
            memo[X] = f(X%count)+1
            return memo[X]

    for i in range(N-1,-1,-1):
        x = X^(1<<i)
        print(f(x))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def popcount(x):
  return int(x.count('1'))

N = int(input())
X = str(input())

def f(n):
  a = 0
  while n != "0b0":
    n = bin(int(n.lstrip("0b"), 2) % popcount(n.lstrip("0b")))
    a += 1
  return a
  

for i in range(N):
  if X[i] == '1':
    y = 0
  else:
    y = 1
    
  x = '0b' + X[:i] + str(y) + X[i+1:]
  print(f(x))

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
from functools import lru_cache

from collections import defaultdict
from copy import deepcopy

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N = int(input())
X = input().strip()
L = list(X)

D = defaultdict(int)
D[0] = 0

@lru_cache(maxsize=1000)
def f(x, ans):
    ans += 1
    b = str(bin(x)[2:])
    c = b.count('1')
    m = x % c
    if m == 0:
        return ans
    return f(m, ans)


for i in range(1, 200001):
    D[i] = f(i, 0)

base = n = int(X, 2)
for i in reversed(range(N)):
    k = 1 << i
    if L[N-i-1] == '1':
        n = base - k
    else:
        n = base + k
    print(f(n, 0))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
l = []
for i in range(len(X)):
    l.append(int(X[i]))
#print(l)
ans = []
def div(n, m):
    size = len(bin(n))-2
    cnt = 0
    for i in range(size):
        if n >> i & 1:
            cnt += 1
    r = n % cnt
    if r == 0:
        global ans
        return ans.append(m+1)
    else:
        div(r, m+1)

num = 0

for i in range(N):
    if l[i] == 1:
        num += 2**(N-i-1)
#print(num)
for i in range(N):
    if l[i] == 1:
        num -= 2**(N-i-1)
    else:
        num += 2**(N-i-1)
    div(num, 0)
    if l[i] == 1:
        num += 2**(N-i-1)
    else:
        num -= 2**(N-i-1)

for i in range(N):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(200000)

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")

#bit数
calc_dict = {i:-1 for i in range(22000)}
res_dict =  {i:-1 for i in range(2*(10**5))}

res_dict = {i:-1 for i in range(1001)}
res_dict[0]=0

for i in range(1, 1001):
    if calc_dict[i]==-1:
        calc_dict[i] = bin(i).count("1")
    
    res_dict[i] = i%calc_dict[i]+1




def mods(N, m, count):
    temp = N%m
    count+=1
    while temp!=0:

        if temp in res_dict:
#             print(count, temp, res_dict[temp])
#             print("come")
#             print()
            return count+res_dict[temp]
        
        if calc_dict[temp]==-1:
            calc_dict[temp] = bin(temp).count("1")
            
        temp = temp%calc_dict[temp]
        count+=1

    return count

bit_count = S.count("1")
for i in range(len(S)):
    if S[i]=="0":

        bit_count+=1
        num = int(S,2) + 2**(N-i-1)
#         print(num, bit_count)
        print(mods(num, bit_count, 0))
        bit_count-=1
    else:

        bit_count-=1
        num = int(S,2) - 2**(N-i-1)
        print(mods(num, bit_count, 0))
        bit_count+=1

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
m = [-1]
p = [-1]
# したからi番目を反転
def reverse_x(i,x):
    a = 1<<i
    b = x^a
    return b
def f(n):
    def popcount(n):
        c = bin(n).count("1")
        return c
    count = 0
    if n % popcount(n) in m:
        count = p[m.index(n%popcount(n))]
        n = 0
    else:
        m.append(n % popcount(n))
        while n != 0:
            n = n % popcount(n)
            count += 1
        p.append(count)
    return count
for i in range(N):
    print(f(reverse_x(N-i-1,X)))

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(v+1):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(20):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt


# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1,v+1)
        if v!=1:
            r[i] += pow(2, n-i-1,v-1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1,v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1,v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

Submission status: Runtime Error

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

input = sys.stdin.readline


def dfs(lst, start, n):
    cnt = [0 for _ in range(n+1)]
    cnt[0] = 0
    cnt[1] = 1
    ones = [0 for _ in range(n+1)]
    ones[0] = 0
    ones[1] = 1

    queue = [1]

    while queue:
        parent = queue.pop()
        tmp = parent << 1
        x = tmp
        c = ones[parent]
        if x <= n:
            r = x % c
            cnt[x] = cnt[r] + 1
            ones[x] = ones[parent]
            queue.append(x)
        x += 1
        if x <= n:
            c += 1
            r = x % c
            cnt[x] = cnt[r] + 1
            ones[x] = ones[parent] + 1
            queue.append(x)

    return cnt


def resolve():
    n = int(input())
    x = input()

    now = 2
    next_ = 2*2

    xx = int(x, base=2)
    cc = x.count('1')
    bit = 1 << (n-1)

    cnt = dfs({}, 1, n)


    for _ in range(n):
        flag = 1 if xx & bit else -1
        r = (xx - flag *  bit) % (cc - flag)
        print(cnt[r] + 1)
        bit >>= 1

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 100001
    POWEROFTWOM1 = [0] * 100001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODM1 += POWEROFTWOM1[N - i - 1]
    xMODP1 %= MODP1
    xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = sum(map(lambda x: x == '1',ans2))
            anscur %= oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Runtime Error

Solution code:
def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)

def f(N:int,s:int):
    bina=list(bin(N))
    array=bina[2:]
    c=0
    for i in array:
        if i=="1":
            c+=1
    p=N%c
    s+=1
    if p==0:
        return s
    else:
        return f(p,s)


N=int(input())
binary=input()
a="0b"+binary
binary=int(a,0)
for i in reversed(range(N)):
    print(f(toggle_nth_bit(binary,i),0))

Submission status: Runtime Error

Solution code:
n=int(input())
s=[int(c) for c in input()]

pc=sum(s)

resm=[0]*n
resp=[0]*n

jm=1
jp=1

totm=0
totp=0
for i in range(n):
    resm[n-i-1]=jm%(pc-1)
    resp[n-i-1]=jp%(pc+1)

    jm=(2*jm)%(pc-1)
    jp=(2*jp)%(pc+1)

    totm+=resm[n-i-1]*s[n-i-1]
    totm%=pc-1

    totp+=resp[n-i-1]*s[n-i-1]
    totp%=pc+1

def popc(x):
    return sum([int(c) for c in format(x,'b')])

for i in range(n):
    if s[i]==1:
        pcc=pc-1
        cres=(totm+pc-1-resm[i])%(pc-1)
    else:
        pcc=pc+1
        cres=(totp+resp[i])%(pc+1)
    
    if cres==0:
        print(1)
        continue

    cnt=1
    while cres>0:
        cres%=popc(cres)
        cnt+=1
    
    print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
def num_cnt(num):
    cnt = 0
    s = 0
    for i in range(len(num)):
        #print(num[-i - 1])
        if num[-i - 1] == 1:
            cnt += 1
            s += 2 ** i
    return cnt, sdef num_cnt(num):
    cnt = 0
    s = 0
    for i in range(len(num)):
        #print(num[-i - 1])
        if num[-i - 1] == 1:
            cnt += 1
            s += 2 ** i
    return cnt, s
for i in range(n):
    num = x[:i]
    if x[i] == '0':
        num += '1'
    else:
        num += '0'
    num += x[i + 1:]
    #print(num)
    ans = 0
    #pop = num.count('1')
    #num = int(num, 2) % pop
    pop, hoge = num_cnt(num)
    num = hoge % pop
    num = bin(num)
    ans = 1
    #print(num)
    while int(num, 2) != 0:
        #pop = num.count('1')
        #num = int(num, 2) % pop
        pop, hoge = num_cnt(num)
        num = hoge % pop
        num = bin(num)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

s = int(input(), 2)


def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


def popcnt3(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


for i in range(n):
    ss = s ^ (1 << (n-i-1))
    c = 0
    t = popcnt3(ss)
    while ss != 0:
        ss -= t*(ss//t)
        t = popcnt3(ss)
        c += 1
    # print(ss, popcnt5(ss), c)
    print(c)

Submission status: Runtime Error

Solution code:
def fast_powmod(n, m):
    pow2 = 2
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = (result * pow2) % m
        pow2 = (pow2 * pow2) % m
        n >>= 1

    return result

def popcnt3(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

n = int(input())
x = input()

res = dict()
res[1] = 1
res[2] = 1
for i in range(3, 2 * 10**5 + 1):
    val = i % popcnt3(i)
    if val == 0:
        res[i] = 1
    else:
        res[i] = res[val] + 1

count = 0
for i in x:
    if i == "1":
        count += 1

x = x[::-1]
small = 0
big = 0
for i in range(len(x)):
    if x[i] == "1":
        small += fast_powmod(i, count - 1)
        big += fast_powmod(i, count + 1)

try:
    small %= count - 1
except:
    small = 0

big %= count + 1

anse = []
for i in range(len(x)):
    if x[i] == "1":
        done = False
        ans = 0
        cur = small - fast_powmod(i, count - 1)
        try:
            cur %= count - 1
            if cur == 0:
                anse.append(1)
            else:
                anse.append(res[cur] + 1)
        except:
            anse.append(1)

    else:
        done = False
        ans = 0
        cur = big + fast_powmod(i, count + 1)
        cur %= count + 1
        if cur == 0:
            anse.append(1)
        else:
            anse.append(res[cur] + 1)


for i in anse[::-1]:
    print(i)
                
        
        
# print(small, big)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
x = int(input().rstrip(),2)
#print(x)
anslist = []
pop = [0]*(int('1'*n,2)+1)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f
def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)

for i in range(1,len(pop)):
    pop[i] = popcount(i)

for i in range(n):
    '''
    b = list(x)
    if b[n-i] == '1':
        b[n-i] = '0'
    else:
        b[n-i] = '1'
    p = int(''.join(b),2)
    '''
    p = toggle_nth_bit(x,i)
    #print(p)
    ans = 0
    while True:
        if p == 0:
            break
        p = p%pop[p]
        ans += 1
    anslist.append(ans)

for i in range(len(anslist)-1,-1,-1):
    print(anslist[i])

Submission status: Runtime Error

Solution code:
def resCount(n):
    tmp = bin(n).count('1')
    if tmp == 1:
        return 1
    elif tmp == 0:
        return 0
    else:
        return 1 + resCount(n % tmp)

for i in range(N):
    res, n = 1, int(X, 2) ^ (1<<(N-i-1))
    print(resCount(n))

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

N,X = open(0).read().split()
N = int(N)
X = int(X,2)

for i in range(0, N):
    x = X
    x = x ^ (1 << (N - 1 - i))
    ans = 0
    while x != 0:
        x = x % popcount(x)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(v+1):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt


# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1,v+1)
        if v!=1:
            r[i] += pow(2, n-i-1,v-1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1,v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1,v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)