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:
def popcount(n):
    return bin(n).count("1")

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
X10 = int(X, 2)
popcountX = X.count("1")

f_table = [f(i+1) for i in range(N)]  # 1 回やれば絶対この中に入る f(i) = f_table[i-1]

for i in range(1, N+1):
    if X[i+1] == "0":
        diff = pow(2, N-i)
        popcount = popcountX + 1
    else:
        diff = -pow(2, N-i)
        popcount = popcountX - 1
    res = (int(X, 2) + diff) % popcount
    ans = f_table[res]
    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())

x=input()

import copy

bin_1cnt = [0] * 200001

for i in range(1, 200001):
    i_bin = format(i, 'b')
    i_bin_1cnt = i_bin.count('1')
    bin_1cnt[i] = i_bin_1cnt

pc_dp = [0] * 200001

for i in range(1, 200001):
    i_init = copy.deepcopy(i)
    cnt_tmp = 1
    i = i % bin_1cnt[i]
    while i != 0 and pc_dp[i] == 0:
        cnt_tmp += 1
        i = i % bin_1cnt[i]
    if i ==0:
        pc_dp[i_init] = cnt_tmp
    elif pc_dp[i] != 0:
        pc_dp[i_init] = cnt_tmp + pc_dp[i]

x_10 = int(x, 2)

for i in range(0, n):
    if x[i]=='0':
        n_i = x_10 + 2**(n-i-1)
        x_1cnt = x.count('1')+1
        n_i  = n_i % x_1cnt
        print(pc_dp[n_i]+1)
    if x[i]=='1':
        n_i = x_10 - 2**(n-i-1)
        x_1cnt = x.count('1')-1
        n_i  = n_i % x_1cnt
        print(pc_dp[n_i]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
k = x.count("1")
cnt = 0
s = int(x, 2)
if k != 1:
	k1 = s % (k-1)
k2 = s % (k+1)
while s != 0:
	targ = bin(s).count("1")
	s = s % targ
	cnt += 1

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

for i in range(n):
	if x[i] == "0":
		targ = k+1
		print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
	else:
		targ = k-1
		print(ev((k1-pow(2, n-i-1, targ)) % targ)+1)

Submission status: Runtime Error

Solution code:
import math
# from collections import defaultdict
import time
def steps(n,p):
  c = 0
  while n:
    c += 1
    n = n%p
    p = bin(n).count('1')
  return c

# n = 200000
# x = "1"*n
n = int(input())
x = input()
incs = 1
decs = 1
p = x.count('1')
ans = []
num = int(x,2)
inc = num%(p+1)
dec = num%(p-1)
start = time.time()
k = -1
for i in range(n-1,-1,-1):
  cp = p
  if x[i] == '0':
    cp += 1
    new = (inc+incs)%cp
  else:
    cp -= 1
    new = (dec-decs)%cp
  k -= 1
  incs = (incs*2)%(p+1)
  decs = (decs*2)%(p-1)
  sol = steps(new,cp)
  if sol==0:
    sol=1
  ans.append(sol)
  # steps(new,cp)
# print(time.time()-start)
ans = ans[::-1]
for x in ans:
  print(x)

Submission status: Runtime Error

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

def calc(num, cnt, ans):
  ans += 1
  if cnt == 0:
    return ans
  mod = num % cnt
  if mod == 0:
    return ans
  else:
    return(calc(mod, bin(mod).count('1'), ans))

n = int(X, 2)
c = X.count('1')
a = n % (c+1)
b = n % (c-1) + c - 1
for i in range(1, N+1):
  if X[i-1] == '0':
    p = (2**(N-i)) % (c+1)
    print(calc(a+p, c+1, 0))
  else:
    if c == 1:
      print(0)
    else:
      m = (2**(N-i)) % (c-1)
      print(calc(b-m, c-1, 0))

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
m = int(x, 2)
def pop(i):
  b = format(i, "b")
  return b.count(1)
for i in range(n):
  y = m ^ (1<<(n-1-i))
  count = 0
  while y > 0:
    y = y % pop(y)
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
x_pop=format(x,'b').count('1')
f=[0]*(x_pop+1)
for i in range(1,x_pop+1):
    popcount=format(i,'b').count('1')
    f[i]=f[i%popcount]+1
# print(f)
for i in range(len(x)):
  popcount=x_pop
    if x[i]=='1':
        x_changed=x[:i]+'0'+x[i+1:]
        popcount-=1
    else:
        x_changed=x[:i]+'1'+x[i+1:]
        popcount+=1
    num_changed=int(x_changed,2)
    # print(x_changed,num_changed)
    if num_changed<n:
        print(f[num_changed])
    else:
        print(f[num_changed%popcount]+1)

Submission status: Runtime Error

Solution code:
LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)%d
f=int(Y,2)%c
for i in range(X):
    if Y[i]=="0":
        g=e+2**(X-1-i)%d
    else:
        g=e-2**(X-1-i)%c
    if g==0:
        print(0)
    else:
        print(M[g])

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
k = x.count("1")
cnt = 0
s = int(x, 2)
k1 = s % (k-1)
k2 = s % (k+1)
while s != 0:
	targ = bin(s).count("1")
	s = s % targ
	cnt += 1

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

for i in range(n):
	if x[i] == "0":
		targ = k+1
		print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
	else:
		targ = k-1
		print(ev((k1-pow(2, n-i-1, targ)) % targ)+1)

Submission status: Runtime Error

Solution code:
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1' and (mod_m == 0 or mod_m == -1):
        print(1)
    elif x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)

Submission status: Runtime Error

Solution code:
def popcount(n):
    return bin(n).count("1")

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
X10 = int(X, 2)
popcountX = X.count("1")

f_table = [f(i+1) for i in range(N)]  # 1 回やれば絶対この中に入る f(i) = f_table[i-1]

for i in range(1, N+1):
    if X[i+1] == "0":
        diff = pow(2, N-i)
        popcount = popcountX + 1
    else:
        diff = -pow(2, N-i)
        popcount = popcountX - 1
    res = (int(X, 2) + diff) % popcount
    ans = f_table[res-1]
    print(ans)

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


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)
        if num==0:
            print(0)
        else:
            print(res_dict[num%bit_count]+1)

#         print(mods(num, bit_count, 0))
        bit_count-=1
    else:

        bit_count-=1
        num = int(S,2) - 2**(N-i-1)
        if num==0:
            print(0)
        else:
            print(res_dict[num%bit_count]+1)
        bit_count+=1

Submission status: Runtime Error

Solution code:
def count(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans

N = int(input())
X = input()
Xn = int(X, 2)
binc = X.count("1")
ans = [-1] * (N)
ans[0] = 0
ans[1] = 1
for i in range(2, N):
    ans[i] = ans[i%count(i)] + 1
for i in range(N):
    if X[i] == "1":
        y = Xn - 2**(N-i-1)
        c = binc - 1
    else:
        y = Xn + 2**(N-i-1)
        c = binc + 1
    y %= c
    print(ans[y] + 1)

Submission status: Runtime Error

Solution code:
import copy
n = int(input())
x = list(map(str,input()))
fun =0
popcount = x.count('1')

for j in range(n):
    ans =0
    xi = copy.copy(x)
    if xi[j] =='0':
        xi[j] ='1'
        popcount +=1
    else:
        xi[j] ='0'
        popcount -=1
    fun = int("".join(xi), 2)

    for i in range(100):
        fun = fun % popcount
        popcount = str(format(fun,'b')).count('1')
        if fun == 0:
            ans = i+1
            break
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
X = input()
n = len(X)
ans = 0
numX = X.count("1")
N = 2*(10**5)
table = []

def solve(numX,X):
    global ans
    y = int(X,2)%numX
    if y == 0:
        ans = 1
        return 0
    else:
        ans = 1 + table[y-1]

def make_table(numX,X):
    global ans
    ans += 1
    y = int(X,2)%numX
    if y == 0:
        return 0
    else:
        z = bin(y)[2:]
        make_table(z.count("1"),z)

for i in range(1,N+1):
    ans = 0
    aaa = bin(i)[2:]
    bbb = aaa.count("1")
    make_table(bbb,aaa)
    table.append(ans)

for i in range(n):
    ans = 0
    tmpX = ""
    tmp = ""
    if X[i] == "0":
        tmpnumX = numX + 1
        tmp = "1"
    else:
        tmpnumX = numX - 1
        tmp = "0"
    if i == 0:
        tmpX = tmp + X[1:]
    elif i == n-1:
        tmpX = X[:i] + tmp
    else:
        tmpX = X[:i] + tmp + X[i+1:]
    solve(tmpnumX,tmpX)
    print(ans)

Submission status: Runtime Error

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

val0 = 0
val1 = 0
cnt = 0

for i in range(0,n):
    if s[i] == '1':
        cnt += 1

for i in range(0,n):
    if s[i] == '1':
        val0 += pow(2,n-i-1,cnt+1)
        val1 += pow(2,n-i-1,cnt-1)

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

for i in range(0,n):
    ans = 0
    if s[i] == '0':
        vall = val0
        o = cnt + 1
        vall += pow(2,n-i-1,o)
        while vall != 0:
            if o == 0:
                break
            vall = vall % (o)
            o = countSetBits(vall)
            ans += 1
        print(ans)
    else:
        vall = val1
        o = cnt - 1
        vall -= pow(2,(n-i-1),o)
        while vall != 0:
            if o == 0:
                break
            vall = vall % (o)
            o = countSetBits(vall)
            ans += 1
        if(o == 1):
            print(1)
        else:
            print(ans)

Submission status: Runtime Error

Solution code:
import copy
from functools import lru_cache
n = int(input())
x = list(input())

popcount = [-1]*(n+1)
popcount[0] = 0
for i in range(1, n+1):
    if popcount[i] == -1:
        i_bin = str(bin(i))
        i_bin_one = i_bin.count("1")
        next_idx = i % i_bin_one
        popcount[i] = popcount[next_idx] + 1

#print(popcount)

x_lis = []
for i in range(n):
    x_copy = copy.copy(x)
    if x[i] == "1":
        x_copy[i] = "0"
    else:
        x_copy[i] = "1"
    x_lis.append("".join(x_copy))

for xi in x_lis:
    xi_int = int(xi, 2)
    xi_one = xi.count("1")
    nxi_idx = xi_int % xi_one
    print(popcount[nxi_idx] + 1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
x_pop=format(x,'b').count('1')
f=[0]*(x_pop+1)
for i in range(1,x_pop+1):
    popcount=format(i,'b').count('1')
    f[i]=f[i%popcount]+1
# print(f)
for i in range(len(x)):
    if x[i]=='1':
        x_changed=x[:i]+'0'+x[i+1:]
        popcount=x_pop-1
    else:
        x_changed=x[:i]+'1'+x[i+1:]
        popcount=x_pop+1
    num_changed=int(x_changed,2)
    # print(x_changed,num_changed)
    if num_changed<n:
        print(f[num_changed])
    else:
        print(f[num_changed%popcount]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
c = input()
#c = list(input())

#print(c)
a = [0] *n
for i in range(n):
    a[i] = int(c[i])
#print(a)
num_11 = [0] *(2*10**5)

for i in range (2*10**5):
    s = bin(i)
    s1 = s[2:]
    num_11[i] = s1.count("1")

amari = [0] *(2*10**5)

for i in range(1,2*10**5):
    amari[i] = i%num_11[i]

num_1 = sum(a)
num_2 = int(c,2)
#print(num_1,num_2)

ans = [0] *n

for i in range(n):
    if a[i] == 1:
        num_i = num_1 -1
        num_j = num_2 -2**(n-i-1)
    else:
        num_i = num_1 +1
        num_j = num_2 + 2**(n-i-1)
    num_j = num_j%num_i
    #print(a[i],amari[num_j],num_j)
    ans[i] += 1
    #if amari[num_j] == 0 and num_j != 0:
        #ans[i] += 1
    while num_j != 0:
        num_j = amari[num_j]
        ans[i] += 1

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

Submission status: Runtime Error

Solution code:
LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)%d
f=int(Y,2)%c
for i in range(X):
    if Y[i]=="0":
        b=d
        g=e+2**(X-1-i)%d
    else:
        b=c
        g=e-2**(X-1-i)%c
    if g==0:
        print(0)
    else:
        print(M[g%b])

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
pop = x.count("1")
lst1 = [1]
for i in range(n-1):
    lst1.append(lst1[-1] * 2 % (pop + 1))
lst1.reverse()
num1 = 0
for i in range(n):
    if x[i] == "1":
        num1 += lst[i]
        num1 %= (pop + 1)
if pop == 1 or pop == 2:
    lst2 = [0] * n
else:
    lst2 = [1]
    for i in range(n-1):
        lst2.append(lst2[-1] * 2 % (pop - 1))
    lst.reverse()
    num2 = 0
    for i in range(n):
        if x[i] == "1":
            num2 += lst2[i]
            num2 %= (pop - 1)
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        if pop == 1:
            print(0)
            continue
        elif pop == 2:
            print(1)
            continue
        else:
            num = num2 - lst2[i]
            num %= (pop - 1)
    else:
        num = num1 + lst1[i]
        num %= (pop + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
W = input()
X = int(W, 2)
T = W.count("1")
memo = dict()

def f(n: int) -> int:
  if n == 0:
    return 0
  elif n in memo:
    return memo[n]
  else:
    res = f(n % (bin(n).count("1"))) + 1
    memo[n] = res
    return res

for i in range(0, N)[::-1]:
  n  = 0
  if W[N-i-1] == '1':
    n = T - 1
  else:
    n = T + 1
  print(f((X ^ (2 ** i)) % n) + 1)

Submission status: Runtime Error

Solution code:
n = int(input())
xo = input()
output = []
import copy
fn = {}

for i in range(n):
  x = copy.copy(xo)
  if x[i] == "0":
    x = x[:i] + "1" + x[i+1:]
  else:
    x = x[:i] + "0" + x[i+1:]
  x = bin(int(x,2))
  counter = int(copy.copy(x),2)
  outi = 0
  while counter != 0:
    cop =  bin(counter).count("1")
    counter = counter%cop
    outi += 1
    if counter in fn.keys():
      outi += fn[counter]
      counter = 0
  fn[int(x)] = outi 
  output.append(str(outi))

print("\n".join(output))

Submission status: Runtime Error

Solution code:
LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)%d
f=int(Y,2)%c
for i in range(X):
    if Y[i]=="0":
        b=d
        g=e+2**(X-1-i)%d
    else:
        b=c
        g=e-2**(X-1-i)%c
    if f==0:
        print(0)
    else:
        print(M[g%b])

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = int(input(), 2)

    def popcount(num):
        return bin(num).count("1")
    
    popc_X = popcount(X)
    pop_table = {i: [popcount(i), 0, 0] for i in range(1, N+1)}
    
    def f(x, factor):
        temp = x
        temp %= (popc_X + factor)
        count = 1
        visited = []
        
        while temp > 0:
            if pop_table[temp][1] == 0:
                pop_table[temp][1] = count
            else:
                if pop_table[temp][2]:
                    count += pop_table[temp][1]
                    break

            if pop_table[temp][2] == 0:
                visited.append(temp)
            temp %= pop_table[temp][0]
            count += 1

        for v in visited:
            pop_table[v][1] = count - pop_table[v][1]
            pop_table[v][2] = 1
        return count
    

    # ans = [0]*N
    for i in range(N-1, -1, -1):
        xi = X ^ (1 << i)
        # print(xi, "xi")
        if X & (1<<i):
            factor = -1
        else:
            factor = 1
        print(f(xi, factor))
    # for a in ans:
    #     print(a)

main()

Submission status: Runtime Error

Solution code:
def popcount(n):
    return bin(n).count("1")

def f(x):
    count = 0
    while x != 0:
        count += 1
        x %= popcount(x)
    return count

N = int(input())
X = "0b"+input()
X10 = int(X, 2)
popcountX = popcount(X)

f_table = [f(i+1) for i in range(N)]  # 1 回やれば絶対この中に入る f(i) = f_table[i-1]

for i in range(1, N+1):
    if X[i+1] == "0":
        diff = pow(2, N-i)
        popcount = popcountX + 1
    else:
        diff = -pow(2, N-i)
        popcount = popcountX - 1
    res = (int(X, 2) + diff) % popcount
    ans = f_table[res-1]
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def func(n):
    bin_num = bin(n).count("1")
    #print(n% bin_num)
    if n == 0: return 0
    return n % bin_num

def main():
    N = int(input())
    X = input()
    bit_num = X.count("1")

    X_minus = [0] * N
    X_plus = [0] * N
    X_minus[0], X_plus[0] = 1, 1
    rem_minus = int(X[-1])
    rem_plus = int(X[-1])
    for i in range(1, N):
        if bit_num != 1: X_minus[i] = (X_minus[i - 1] * 2) % (bit_num - 1)
        X_plus[i] = (X_plus[i - 1] * 2) % (bit_num + 1)
        if X[-i-1] == "1":
            rem_minus += X_minus[i]
            if bit_num != 1: rem_minus %= bit_num - 1
            rem_plus += X_plus[i]
            rem_plus %= bit_num + 1

    for i in range(N):
        #print("")
        #print("i={}".format(i))
        n = list(X)
        if X[i] == '0':
            n[N - i - 1] = '1'
            bin = bit_num + 1
        if X[i] == '1':
            n[N - i - 1] = '0'
            bin = bit_num - 1
        if bin == bit_num - 1: n = (rem_minus - X_minus[-i-1]) % bin
        if bin == bit_num + 1: n = (rem_plus + X_plus[-i-1]) % bin
        #print("bin={}, n={}".format(bin, n))

        if bin == 0:
            print(0)
            continue
        cnt = 1
        while n != 0:
            n = func(n)
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0
 
 
def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]
 
 
ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
O = X.count('1')
XN = int(X, 2)

dp = [0] * (N+1)

def popcount(n):
    cnt = 0
    while n != 0:
        one = bin(n).count('1')
        n %= one
        cnt += 1
        if dp[n] > 0:
            return dp[n] + cnt
    return cnt

for i in range(1, N+1):
    dp[i] = popcount(i)

for i in range(N):
    if X[i] == '0':
        print(popcount(XN + pow(2, N-i-1, O+1)))
    else:
        print(popcount(XN - pow(2, N-i-1, O-1)))

Submission status: Runtime Error

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

def popcnt(x):
    n=x
    res=0
    while n>0:
        res+=n%2
        n//=2
    return res

table=[0,1]+[-1 for i in range(219998)]
for i in range(2,220000):
    table[i]=table[i%popcnt(i)]+1

moto=0
for i in range(N):
    if X[i]=='1':
        moto+=1

plus=0  #もとの数字に1のときのmodをしたやつ
minus=0

for i in range(N):
    plus+=int(X[i])*pow(2,N-1-i,moto-1)
    minus+=int(X[i])*pow(2,N-1-i,moto+1)
    plus%=(moto-1)
    minus%=(moto+1)

for i in range(N):
    ans=0
    if X[i]=='1':
        ans=plus
        ans-=pow(2,N-1-i,moto-1)
        ans%=(moto-1)
    else:
        ans=minus
        ans+=pow(2,N-1-i,moto+1)
        ans%=(moto+1)
    print(table[ans]+1)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
fact = math.factorial
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
X = s()[::-1]
num1 = 1
num2 = 1
num3 = 0
num4 = 0
cnt = 0
for i in range(N):
    if X[i] == '1':
        cnt += 1
cnt1 = cnt+1#0用
cnt2 = cnt-1#1用
nums = []
ans = []
for i in range(N):
    if X[i] == '0':
        nums.append(num1)
    else:
        num3 += num1
        num4 += num2
        nums.append(num2)
    num1 = (num1*2)%cnt1
    num2 = (num2*2)%cnt2
num3 %= cnt1
num4 %= cnt2
for i in range(N):
    if X[i] == '0':
        ans.append((num3+nums[i])%cnt1)
    else:
        ans.append((num4-nums[i])%cnt2)
ans.reverse()
tans = [1]*N
def f(n):
    if n == 0:
        return
    tans[i] += 1
    c = n%(list(bin(n)[2:]).count('1'))
    f(c)
for i in range(N):
    f(ans[i])
for i in range(N):
    print(tans[i])

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")

box = [0] * (maxbit + 1)

def f(i):
  cnt = 0
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

for i in range(1, min(maxbit + 1, 200000)):
  box[i] = f(i)

for i in range(lenx):
  if x[i] == "0":
    mb = maxbit + 1
    t = x10 + pow(2, (lenx - 1 - i), mb)
  else:
    mb = maxbit - 1
    t = x10 - pow(2, (lenx - 1 - i), mb)
  # print(t, mb)
  if t == 0:
    print(0)
  else:
    t %= mb 
    if t == 0:
      print(1)
    else:
      ans = f(t) + 1 
      box[t] = ans
      print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
bin_X = int(X, 2)
cnt = 0
for i in X:
    if i == '1':
        cnt += 1

def bit_count(bits):
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
    return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff)


def pop_counter(n):
    return n % bit_count(n)


ans = 0
for n, i in enumerate(X):
    ans = 1
    tmp = bin_X ^ pow(2, N - n - 1)
    if i == '1':
        tmp %= cnt - 1
    else:
        tmp %= cnt + 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
Xn = int(X, 2)
binc = X.count("1")
ans = [-1] * (N)
ans[0] = 0
ans[1] = 1
for i in range(2, N):
    ans[i] = ans[i%bin(i).count("1")] + 1
for i in range(N):
    if X[i] == "1":
        y = Xn - 2**(N-i-1)
        c = binc - 1
    else:
        y = Xn + 2**(N-i-1)
        c = binc + 1
    y %= c
    print(ans[y] + 1)

Submission status: Runtime Error

Solution code:
def f(n):
    if L[n] >= 0:
        return L[n]
    else:
        popcount = str(bin(n)).count('1')
        L[n] = max(1, f(n % popcount) + 1)

n = int(input())
x = list(map(str, (input())))
X = int(''.join(x), 2)
L = [-1] * (n + 1)
L[0] = 0
for i in range(1, n+1):
    f(i)
for i in range(n):
    if x[i] == '1':
        xx = X - 2 ** (n-i-1)
    else:
        xx = X + 2 ** (n-i-1)
    p = str(bin(xx)).count('1')
    print(1 + L[xx % p])

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
fact = math.factorial
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
X = (['1']*(10**5))[::-1]
#X = s()[::-1]
num1 = 1
num2 = 1
num3 = 0
num4 = 0
cnt = 0
for i in range(N):
    if X[i] == '1':
        cnt += 1
cnt1 = cnt+1#0用
cnt2 = cnt-1#1用
nums = []
ans = []
for i in range(N):
    if X[i] == '0':
        nums.append(num1)
    else:
        num3 += num1
        num4 += num2
        nums.append(num2)
    num1 = (num1*2)%cnt1
    num2 = (num2*2)%cnt2
num3 %= cnt1
num4 %= cnt2
for i in range(N):
    if X[i] == '0':
        ans.append((num3+nums[i])%cnt1)
    else:
        ans.append((num4-nums[i])%cnt2)
ans.reverse()
tans = [1]*N
def f(n):
    if n == 0:
        return
    tans[i] += 1
    c = n%(list(bin(n)[2:]).count('1'))
    f(c)
for i in range(N):
    f(ans[i])
for i in range(N):
    print(tans[i])

Submission status: Runtime Error

Solution code:
n=int(input())

x=input()

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

ans1=[0]*200000

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,ans1)
	if ans1[int(y,2)]!=ans:
		ans1[int(y,2)]=ans
	print(ans)

Submission status: Runtime Error

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

dp=[-1]*(n+1)

dp[0]=0
dp[1]=1
co=[-1]*(n+1)

def fun(num,step):
    num2=num%sum(list(map(int,bin(num)[2:])))
    if dp[num2]!=-1:
        dp[num]=dp[num2]+step
    else:
        fun(num2,step+1)

for i in range(2,n//2):
    fun(i,1)

num1=''.join(x)
num2=int(num1,2)
su = sum(list(map(int,x)))

for i in range(n):
    num4=num2
    su2=su
    if x[i]=='1':
        num4-=pow(2,(n-1-i))
        su2-=1
    else:
        num4+=pow(2,(n-1-i))
        su2+=1
    if su2 == 0:
        print('0')
    elif num4<n//2:
        print(dp[num4])
    else:
        num3=num4%su2
        if num3<n//2:
            print(dp[num3]+1)
        else:
            num5=num3%sum(list(map(int,bin(num3)[2:])))
            print(dp[num5]+2)

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

print(n)
print(len(x))

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:
import collections

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

x_list = list(x)

num_dict = dict(collections.Counter(x_list))

num_of_1 = num_dict["1"]

first_temp = int(x, 2)

for i in range(n):
    temp_num_of_1 = num_of_1 + 1 if x_list[i] == "0" else num_of_1 - 1

    ans = 0

    if temp_num_of_1 > 0:
        a = first_temp + 2 ** (n - i - 1) if x_list[i] == "0" else first_temp - 2 ** (n - i - 1)

        a = a % temp_num_of_1

        temp = list(bin(a)[2:])

        ans += 1
    
        while temp.count("1") != 0:
            a = int("".join(temp), 2)

            a = a % temp.count("1")

            temp = list(bin(a)[2:])

            ans += 1

    print(ans)