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 cal_cnt(num):
  cnt = 0
  for bit in format(num, 'b'):
    if bit == '1':
      cnt += 1

  return cnt


def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1) if base_cnt > 1 else 0

  memo = tuple(map(cal_cnt, range(n)))

  dp = [None] * n
  dp[0] = 0

  def f(num, cnt):
    if num < n and dp[num] is not None:
      return dp[num]

    nxt = num % cnt
    res = 1 + f(nxt, memo[nxt])
    if num < n:
      dp[num] = res

    return res


  for i in range(n - 1, -1, -1):
    num = None

    if src[n - i - 1] == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    else:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod

    print(1 + f(num, memo[num]))


main()

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0); continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - 1, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X - 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')
    mx = nx % (oc - 1)
    px = nx % (oc + 1)

    tn = 1 << N - 1
    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        else:
            if oc - 1 == 0:
                ans[i] = 0
                continue
            else:
                a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count
        tn = tn >> 1

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import statistics
import itertools
from collections import deque
n=int(input())
x=str(input())
ans_lis =[0]*10000000

def p(s):
    ss=bin(s)
   c = collections.Counter(ss)
    return c['1']
def o(d):
    i=0
    while d!=0:
        i+=1
        q=p(d)
        d%=q
    return i

lis=[]
for i in range(n):
    num=x[i]
    lis.append(num)



lisss=lis
for g in range(n):
    
    if lisss[g]=='0':
        lisss[g]='1'
    
    else:
        lisss[g]='0'
    ans=0
   
    for j in range(n):
        if lisss[j]=='1':
            jj=int(j)
            ans+=2**(n-jj-1)
    print(o(ans))
    if lisss[g]=='0':
        lisss[g]='1'
    
    else:
        lisss[g]='0'

Submission status: Runtime Error

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()

x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        dv=px-1
    else:
        tmp=x1+pow2[i]
        dv=px+1
    if dv==0:
        ans.append(0)
        continue
    cnt=1
    while tmp:
        if not dv:
            break
        tmp%=dv
        dv=bin(tmp).count("1")
        if not tmp:
            break
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

def input():
    return sys.stdin.readline().rstrip()

@lru_cache(maxsize =None)
def tc(n):
    if n ==0:
        return 0

    y =n
    count =0
    while y:
     if y%2==1:
         count +=1
     y=y//2
    ans =n % count
    if ans ==0:
     return 1
    else:
     return tc(ans) +1



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

    const = 0
    for i in range(N):
        if x[i] =="1":
            const +=1



    xm = X % (const - 1)
    xp = X % (const +1)

    for i in range(N-1, -1, -1):
        if x[N-i-1] =="0":
            t = xp + pow(2,i,const +1)
            t %= const +1
        else:
            t = xm - pow(2,i,const -1)
            t %= const -1






        print(tc(t)+1)









if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)
dp = [-1] * ((2*10**5)+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1
    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)
    if (nx>>i)&1:
        r = (nx-tmp)%(pc-1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)
    else:
        r = (nx+tmp)%(pc+1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)

Submission status: Runtime Error

Solution code:
# %%
n = int(input())
x = input()

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(N):
        if X[i]=='1':
            print(0)
        elif i==N-1:
            print(2)
        else:
            print(1)
    exit()

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

    ans = 0

    a = first + 2 ** (n - i - 1) if x[i] == "0" else first - 2 ** (n - i - 1)

    a = a % temp_num_of_1

    temp = bin(a)[2:]

    ans += 1 + f(a)

    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()

x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        dv=px-1
    else:
        tmp=x1+pow2[i]
        dv=px+1
    if dv==0:
        ans.append(0)
        continue
    cnt=1
    while tmp:
        tmp%=dv
        dv=bin(tmp).count("1")
        if not tmp:
            break
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200002)
n = int(input())
q = input()
r = list(q)
ans=[]
for i in range(0,n):
    ans.append(0)
def k(x,n):
    ans = 0
    for i in range(n):
        if x&1:
            ans += 1
        x = x>>1
    return ans
x = int(q, 2)
y = k(x,n)
for i in range(n):
    an = 0
    if r[n-i-1]=='1':
        z = x-2**i
        if y-1 == 0:
            ans[i] = 0
        else:
            z = z%(y-1)
            while z:
                u = k(z,10)
                z = z%u
                an += 1
            ans[i] = an+1
    else:
        z = x + 2**i
        z = z%(y+1)
        while z:
            u = k(z,10)
            z = z%u
            an += 1
        ans[i] = an+1
ans.reverse()
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    x = input()
    k = int(x,2)
    c = x.count('1')
    kp = k%(c+1)
    if c > 1:
        kn = k%(c-1)
    
    for i in range(n):
        cnt = 1
        if x[i] == '1':
            if c == 1:
                print(0)
                continue
            mod = c-1
            tmp = (kn - pow(2,n-i-1,mod))%mod
            while 1:
                if tmp == 0:
                    print(cnt)
                    break
                tmp = tmp%format(tmp, 'b').count('1')
                cnt+=1
        else:
            mod = c+1
            tmp = (kn + pow(2,n-i-1,mod))%mod
            while 1:
                if tmp == 0:
                    print(cnt)
                    break
                tmp = tmp%format(tmp, 'b').count('1')
                cnt+=1
            


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')
    mx = nx % (oc - 1)
    px = nx % (oc + 1)

    tn = 1 << N - 1
    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        else:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count
        tn = tn >> 1

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

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
if 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
    if cp > 1:
      new = (dec-decs)%cp
    else:
      new = dec-decs
  k -= 1
  incs = (incs*2)%(p+1)
  if 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 = list(input())

def popcount(n):
    bin_n = bin(n)[2:]
    count = 0
    for i in bin_n:
        count += int(i)
    return count

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

lst = [0 for i in range(n+1)]
for i in range(1, n+1):
    num = i%popcount(i)
    lst[i] = lst[num] + 1

plus = [0 for i in range(n)]
minus = [0 for i in range(n)]
plus[0] = 1
if cnt != 1:
    minus[0] = 1
for i in range(1, n):
    plus[i] = (plus[i-1]*2) % (cnt+1)
    if cnt != 1:
        minus[i] = (minus[i-1]*2) % (cnt-1)

origin = int(''.join(x), base=2)
amariplus = origin % (cnt+1)
amariminus = origin % (cnt-1)

for i in range(n):
    if x[i] == '0':
        amari = (amariplus + plus[n-i-1]) % (cnt+1)
        print(lst[amari] + 1)
    else:
        if cnt != 1:
            amari = (amariminus - minus[n-i-1]) % (cnt-1)
            print(lst[amari] + 1)
        else:
            print(0)

Submission status: Runtime Error

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()

x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        dv=px-1
    else:
        tmp=x1+pow2[i]
        dv=px+1
    if px==0:
        ans.append(0)
        continue
    cnt=1
    while tmp:
        tmp%=dv
        dv=bin(tmp).count("1")
        if not tmp:
            break
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

def complement(c):
    if c=='1':
        return '0'
    else:
        return '1'

H = {}

def pop(n):
    return "{0:b}".format(n).count('1')
def toZero(n):
    if n==0:
        return 0
    if n==1:
        return 1
    if n in H:
        return H[n]
    r = 1 + toZero(n%pop(n))
    H[n] = r
    return r

[N] = getInts()
X = input()
Xi = int(X, 2)
X = list(X)

i=0
p = pop(Xi)
while 2**i < Xi:
    toZero(2**i%(p+1))
    toZero(2**i%(p-1))
    i+=1
for i in range(N):
    X[i] = complement(X[i])
    n = int("".join(X),2)
    print(toZero(n))
    X[i] = complement(X[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200002)
n = int(input())
q = input()
r = list(q)
ans = [0 for i in range(n)]
def k(x,n):
    ans = 0
    for i in range(n):
        if x&1:
            ans += 1
        x = x>>1
    return ans
x = int(q, 2)
y = k(x,n)
for i in range(n):
    an = 0
    if r[n-i-1]=='1':
        z = x-2**i
        if y-1 == 0:
            ans[i] = 0
        else:
            z = z%(y-1)
            while z:
                u = k(z,10)
                z = z%u
                an += 1
            ans[i] = an+1
    else:
        z = x + 2**i
        z = z%(y+1)
        while z:
            u = k(z,10)
            z = z%u
            an += 1
        ans[i] = an+1
ans.reverse()
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
def countSetBits(num):
    binary = bin(num)
    setBits = [ones for ones in binary[2:] if ones == '1']
    return len(setBits)
def steps(num):
    count=0
    while num>0:
        num=num%countSetBits(num)
        count=count+1
    return  count

if __name__ == "__main__":
    arr=[]
    for i in range(0, 10000):
        arr.append(2**i)
    n=int(input())
    str=input()
    num=0
    for i in range(0,n):
        if str[i]=='1':
            num+=arr[i]
    temp=num
    for i in range(n-1,-1,-1):
        temp=num
        if str[i]=='0':
            temp=temp+arr[i]
        else:
            temp=temp-arr[i]
        print(steps(temp))

Submission status: Runtime Error

Solution code:
N=int(input())
X=int(input(),2)
popx=bin(X).count('1')
def f(n,i):
    if n>>i&1:
        pop=popx+1
    else:
        pop=popx-1
    ans=1
    n%=pop
    while n != 0:
        ans+=1
        n2=bin(n)
        pop=n2.count('1')
        n=n%pop
    return ans

for i in range(N-1,-1,-1):
    xi=X^2**i
    print(f(xi,i))

Submission status: Runtime Error

Solution code:
import copy
n=int(input())
x=input()
one_count=x.count("1")
y=copy.copy(x)
z=int(y,2)
pop01=z%(one_count+1)
pop10=z%(one_count-1)

for i in range(n):
    one_count=x.count("1")
    z=int(y,2)
    y=copy.copy(x)
    count=0
    if x[i]=="0":
        one_count+=1
        z=(pop01)+((2**(n-1-i))%one_count)
        z=z%one_count
        count+=1
        y=bin(z)
    else:
        one_count-=1
        z=(pop10)-((2**(n-i-1))%one_count)
        z=z%one_count
        count+=1
        y=bin(z)
    while z!=0:
        z=z%(y.count("1"))
        y=bin(z)
        count+=1

    print(count)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
n = int(input())
q = input()
r = list(q)
ans = [0 for i in range(n)]
def k(x,n):
    ans = 0
    for i in range(n):
        if x&1:
            ans += 1
        x = x>>1
    return ans
x = int(q, 2)
y = k(x,n)
for i in range(n):
    an = 0
    if r[n-i-1]=='1':
        z = x-2**i
        if y-1 == 0:
            ans[i] = 0
        else:
            z = z%(y-1)
            while z:
                u = k(z,10)
                z = z%u
                an += 1
            ans[i] = an+1
    else:
        z = x + 2**i
        z = z%(y+1)
        while z:
            u = k(z,10)
            z = z%u
            an += 1
        ans[i] = an+1
ans.reverse()
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np


def function(N):
    for n in range(1, N+1):
        if n < 6:
            print(0)
        else:
            ans = 0
            number = int(np.sqrt(2*n))
            X = [int(i) for i in range(2, number+1)]
            for x in X:
                Y = [int(j) for j in range(x, number+1)]
                for y in Y:
                    Z = [int(k) for k in range(y, number+1)]
                    for z in Z:
                        if x**2+y**2+z**2 == 2*n:
                            if x+y > z+1 & (x+y+z) % 2 == 0:
                                if x == y & y == z:
                                    ans += 1
                                else:
                                    ans += 3

            print(ans)


if __name__ == '__main__':
    N = int(input())
    function(N)

Submission status: Runtime Error

Solution code:

def cal_cnt(num):
  cnt = 0
  for bit in format(num, 'b'):
    if bit == '1':
      cnt += 1

  return cnt


def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1)

  memo = tuple(map(cal_cnt, range(n + 1)))

  dp = [None] * (n + 1)
  dp[0] = 0

  def f(num, cnt):
    if num < n and dp[num] is not None:
      return dp[num]

    nxt = num % cnt
    res = 1 + f(nxt, memo[nxt])
    if num < n:
      dp[num] = res

    return res


  for i in range(n - 1, -1, -1):
    num = None

    if src[n - i - 1] == '0':
      mod = base_cnt + 1
      num = ((basep + pow(2, i, mod)) % mod)
    else:
      mod = base_cnt - 1
      num = ((basem - pow(2, i, mod)) % mod)

    print(1 + f(num, memo[num]))


main()

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    X = SS()

    # 一回の操作でnはN以下になる
    # 操作後に同じ値になることもあるので覚えておく
    # popcountはそのビット見ればすぐわかる
    # 初回popcountは2種類しかない

    # x = X
    # N = 5
    # X = '10101'
    pc_X = X.count('1')

    next_X_p1 = 0
    next_X_m1 = 0
    pc_p1 = pc_X + 1
    pc_m1 = pc_X - 1
    for i in range(N):
        if X[i] == '1':
            next_X_p1 += pow(2, N - 1 - i, pc_p1)
            next_X_m1 += pow(2, N - 1 - i, pc_m1)

    dp = [-1] * N
    dp[0] = 0
    def dfs(n):
        if dp[n] == -1:
            dp[n] = 1 + dfs(n % bin(n).count('1'))
        return dp[n]
    # print(pc_X, pc_m1, pc_p1, next_X_m1, next_X_p1)
    for i in range(N):
        next = 0
        if X[i] == '1':
            next = next_X_m1 - pow(2, N - 1 - i, pc_m1)
            next %= pc_m1
        else:
            next = next_X_p1 + pow(2, N - 1 - i, pc_p1)
            next %= pc_p1

        # print('i', i, next, pc_m1)
        if pc_X == 1 and X[i] == '1' and i == N - 1:
            ans = 0
        else:
            ans = dfs(next) + 1
        print(ans)
    # print(dp)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:

def cal_cnt(num):
  cnt = 0
  for bit in format(num, 'b'):
    if bit == '1':
      cnt += 1

  return cnt


def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1)

  memo = tuple(map(cal_cnt, range(n)))

  dp = [None] * (n + 1)
  dp[0] = 0

  def f(num, cnt):
    if num < n and dp[num] is not None:
      return dp[num]

    nxt = num % cnt
    res = 1 + f(nxt, memo[nxt])
    if num < n:
      dp[num] = res

    return res


  for i in range(n - 1, -1, -1):
    num = None

    if src[n - i - 1] == '0':
      mod = base_cnt + 1
      num = ((basep + pow(2, i, mod)) % mod)
    else:
      mod = base_cnt - 1
      num = ((basem - pow(2, i, mod)) % mod)

    print(1 + f(num, memo[num]))


main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=str(input())
pop=[0]
a=1
b=0
for i in range(1,n):
    ni=0
    a=i
    while a:
        a&=(a-1)
        ni+=1
    nii=i%ni
    pop.append(pop[nii]+1)

xi=int(x,2)    

a=x1
popi=0
while a:
    a&=(a-1)
    popi+=1
x2=popi

for i in range(n):
    xi=(2**(n-1)>>i)^x1
    if (2**(n-1)>>i)&x1:
        x3=x2-1
    else:
        x3=x2+1
    popi=0
    if xi!=0:
        xi=xi%x3
        ans=pop[xi]+1
        print(ans)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
N=int(input())
X=int(input(),2)
popx=bin(X).count('1')
def f(n,i):
    if n>>i&1:
        pop=popx+1
    else:
        pop=popx-1
    ans=1
    #print('pop',pop)
    n%=pop
    while n != 0:
        ans+=1
        n2=bin(n)
        pop=n2.count('1')
        n=n%pop
    return ans

for i in range(N-1,-1,-1):
    xi=X^2**i
    #print('xi',xi)
    print(f(xi,i))

Submission status: Runtime Error

Solution code:
import numpy as np
from typing import List, Tuple

N = int(input())
X = list(map(int, input()))


def binary_mod(bits: List[int], div: int) -> int:
    val = 0
    for b in bits:
        val = (val * 2 + b) % div
    return val


def f(x):
    cnt = 0
    while x > 0:
        x = x % bin(x).count('1')
        cnt += 1
    return cnt


popcount = sum(X)
div1 = popcount + 1
div2 = popcount - 1

if popcount == 0:
    print('\n'.join(map(str, [1] * N)))
else:
    rem1 = binary_mod(X, div1)
    rem2 = binary_mod(X, div2)

    for i in range(N):
        if X[i] == 0:
            r = (rem1 + pow(2, N - 1 - i, div1)) % div1
            print(f(r) + 1)
        else:
            r = (rem2 - pow(2, N - 1 - i, div2) + div2) % div2
            print(f(r) + 1)

Submission status: Runtime Error

Solution code:
import numpy as np
from typing import List, Tuple

N = int(input())
X = list(map(int, input()))


def binary_mod(bits: List[int], div: int) -> int:
    val = 0
    for b in bits:
        val = (val * 2 + b) % div
    return val


def f(x):
    cnt = 0
    while x > 0:
        x = x % bin(x).count('1')
        cnt += 1
    return cnt


popcount = sum(X)
div1 = popcount + 1
div2 = popcount - 1

if popcount == 0:
    print('\n'.join(map(str, [0] * N)))
else:
    rem1 = binary_mod(X, div1)
    rem2 = binary_mod(X, div2)

    for i in range(N):
        if X[i] == 0:
            r = (rem1 + pow(2, N - 1 - i, div1)) % div1
            print(f(r) + 1)
        else:
            r = (rem2 - pow(2, N - 1 - i, div2) + div2) % div2
            print(f(r) + 1)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')
    mx = nx % (oc - 1)
    px = nx % (oc + 1)

    tn = 1 << N - 1
    for i in range(N):

        if X[i] == '0':
            a = (px + tn % (oc + 1)) % (oc + 1)
        else:
            a = (mx - tn % (oc - 1)) % (oc - 1)

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count
        tn = tn >> 1

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def change_num(tmp, i):
    if tmp[i] == "0":
        return int(tmp, 2)+pow(2, N-i-1)
    else:
        return int(tmp, 2)-pow(2, N-i-1)


N = int(input())
X = input()
flag = 0

for i in range(N):
    tmp = change_num(X, i)
    while True:
        num1 = 0
        for i in bin(tmp):
            # if i == 1:
            if "1" in i:
                num1 += 1

        tmp = tmp % num1
        flag += 1
        if tmp == 0:
            break
    print(flag)
    flag = 0

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)
    puls1 = X % (popc_X + 1)
    minu1 = X % (popc_X - 1)
    dic = {0: minu1, 1: puls1}
    tow = [1]
    for i in range(1,N):
        tow.append(2*tow[i-1])
    pop_table = {i: [popcount(i), 0, 0] for i in range(1, 1+N)}
    def f(x, factor, i):
        temp = dic[factor]
        if factor:
            temp += tow[i] % (popc_X + 1)
        else:
            temp -= tow[i] % (popc_X - 1) 
        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 = 0
        else:
            factor = 1
        print(f(xi, factor, i))
    # for a in ans:
    #     print(a)

main()

Submission status: Runtime Error

Solution code:
import copy

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

nbits=sum([int(X[i]) for i in range(N)])


# print(nbits)

MAXBIT=60
def strmod(bitstr,m):
    if len(bitstr)>MAXBIT:
        l = eval("0b"+bitstr[:MAXBIT])
        l_bitstr="{:b}".format(l % m)
        ans=strmod(l_bitstr+bitstr[MAXBIT:], m)
    else:
        ans="{:b}".format(eval("0b"+bitstr) % m)
    return ans

for i in range(N):

    if X[i]=='0':
        c='1'
        n = nbits + 1
    else:
        c='0'
        n = nbits - 1
    Y=X[:i]+c+X[i+1:]

    # print("Y=",Y)
    ans = 0
    while True:
        ans += 1
        mstr = strmod(Y,n)
        n=sum([int(mstr[i]) for i in range(len(mstr))])
        # print(mstr, n)
        if n == 0:
            break
        Y = mstr
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    lowNumber = []
    for i in range(MOD):
        anscur = i
        cnt = 1
        while anscur != 0:
            oneCount = bin(anscur).count('1')
            anscur %= oneCount
            cnt += 1
        lowNumber.append(cnt)
    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] * 200001
    POWEROFTWOM1 = [0] * 200001
    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]
            xMODP1 %= MODP1
            xMODM1 += POWEROFTWOM1[N - i - 1]
            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
        ans += str(lowNumber[anscur])
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()