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:
from functools import lru_cache
from collections import defaultdict

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

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


@lru_cache(maxsize=200005)
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
    if n == 0:
        print(0)
    else:
        print(f(n, 0))

Submission status: Runtime Error

Solution code:
def popcount(n):
    cnt = 0
    for i in range(n):
        if ((n >> i) & 1):
            cnt +=1
    return cnt

def f(n):
    cnt = 1
    while True:
        if n == 0:
            break
        n = n % popcount(n)
        cnt += 1
    return cnt

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)

if __name__ == "__main__":
    n = int(input())
    x = input()
    xList = list(x)
    k = len(xList) - 1
    xNum = int("".join(xList), 2)
    numcnt = popcount(xNum)
    a = numcnt
    wk = 0
    for i in range(n):
        if xList[i] == '0':
            numcnt += 1
        else:
            numcnt -= 1
        xList[i] = str(int(xList[i]) ^ 1)
        xNum = int("".join(xList), 2)
        wk = xNum % numcnt
        if wk == 0:
            print(1)
        else:
            print(f(wk))
        xList[i] = str(int(xList[i]) ^ 1)
        numcnt = a

Submission status: Runtime Error

Solution code:
n=int(input())
x_str=input()
x=int(x_str,2)
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
x_minus=x%(x_popcount-1)
x_plus=x%(x_popcount+1)
pows_minus=[(2**i)%(x_popcount-1) for i in range(n)]
pows_plus=[(2**i)%(x_popcount+1) for i in range(n)]

for i in range(len(x_str)):
    ## xi=xi mod popcount(x)+-1
    xi=0
    if x_str[i]=='1':
        xi=(x_minus-pows_minus[n-1-i])%(x_popcount-1)
    else:
        xi=(x_plus+pows_plus[n-1-i])%(x_popcount+1)
    print(dp[xi]+1)

Submission status: Runtime Error

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

from collections import defaultdict

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

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

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())
a = input()
import copy
num = a
list_num = list(num)
list_num = [int(s) for s in list_num]
list_a = copy.copy(list_num)
list_num.reverse()
sum_num = 0
for i,s in enumerate(list_num):
  if s == 1:
    sum_num += 2**i

count_a = list_a.count(1)
for i in range(N):
  n = 1
  b = sum_num
  counta = count_a
  count = 0
  if list_a[i] == 0:
    counta+=1
    b += 2**(N-i-1)
  else:
    counta-=1
    b -= 2**(N-i-1)
  while n>0:
      n = b%counta
      num = str(bin(n))
      cou = list(num)
      counta = cou.count('1')
      b = n
      
      count+=1
  print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = x_num % (cnt1 - 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


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


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if (x_num - (2**(N-(i+1)))) != 0:
            print(f1((x_num - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        print(f1((x_num + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)) + 1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
x = int(s, 2)
print(x)
pcx = s.count("1")
pc_n = x % (pcx - 1)
pc_p = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc_p + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc_n - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    if d > 0:
        k0 = k % (d-1)
    k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        if x[i] == '1':
            dd = d - 1
            if dd == 0:
                wi(0)
                continue
            wi(f[(k0 - pow(2, n - i - 1, dd)) % dd] + 1)
        else:
            dd = d + 1
            wi(f[(k1 + pow(2, n - i - 1, dd)) % dd] + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return bin(x).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
jpop=popcount(x)
jop=x%(jpop+1)
jom=x%(jpop-1)
jppp=jpop+1
jppm=jpop-1
for i in range(n):
  nijo=2**(n-1-i)
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>=jppp:
      a-=jppp
  else:
    a=jom-nijo%jppm
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = x_num % (cnt1 - 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


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


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if (x_num - (2**(N-(i+1)))) != 0:
            print(f1((p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        print(f1((p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)) + 1)

Submission status: Runtime Error

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


N = int(input())
X = int(input(), 2)
X_popcount = popcount(X)

for i in range(N-1, -1, -1):
    ans = 1
    if (X >> i) & 1:
        Y = (X - 2**i) % (X_popcount - 1)
    else:
        Y = (X + 2**i) % (X_popcount + 1)
    while Y > 0:
        Y %= popcount(Y)
        ans += 1
    print(ans)

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

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

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((first_zero + pow(2, n-i-1, num_of_1 + 1)) % num_of_1 + 1))
    else:
        print(1 + f((first_one - pow(2, n-i-1, num_of_1 - 1)) % num_of_1 - 1))

Submission status: Runtime Error

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

def popcount(n):
    return bin(n).count('1')
    

to_add = 1
tot = 0
counta = 0
for i in range(n-1,-1,-1):
    if s[i]=='1':
        tot+=to_add
        counta += 1

    to_add = 2*to_add
    
to_add = to_add//2

for i in range(n):
    if s[i]=='1':
        temp = tot-to_add
        tempa = counta-1
    else:
        temp = tot+to_add
        tempa = counta+1
        
    temp = temp%tempa
    count = 1
    while temp>0:
        temp = temp%popcount(temp)
        count+=1
    print(count)
    
    to_add = to_add//2

Submission status: Runtime Error

Solution code:
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
dp[0] = 0
dp[1] = 1
pcs = [-1] * ((2*10**5)+1)
pcs[0] = 0
for i in range(1, 18):
    pcs[2**i] = 1
    pcs[2**i-1] = i
def f(n):
    if dp[n] >= 0:
        return dp[n]
    if pcs[n] >= 0:
        pc = pcs[n]
    else:
        pc = bin(n).count('1')
        pcs[n] = pc
    nn = n%pc
    d = f(nn)+1
    dp[n] = d
    return d

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

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
import time
count = 0

@lru_cache(maxsize=None)
def popcount(n):
    n = bin(n)
    n_out = n.count("1")
    return n_out

def f_count(n):
    #print(n, type(n))
    global count
    if n != 0:
        count += 1
        #print(count, n)
        f_count(n % (popcount(n)))
    return 0

def main():
    n = int(input())
    x = input()
    mod_popcount_x = popcount(int(x, 2))
    if '0' in list(x):
        x_plus = int(x, 2) % (mod_popcount_x + 1)
    if '1' in list(x):
        x_minus = int(x, 2) % (mod_popcount_x - 1)
    
    for i in range(n):
        global count
        count = 0
        if list(x)[i] == '0':
            count += 1
            d = (x_plus + 2 ** (n - 1 - i)) % (mod_popcount_x + 1)
            f_count(d)
            print(count)
        if list(x)[i] == '1':
            if not list(x).count('1') == 1: #1が一つで結果が0になる場合を除く    
                count += 1
                #変更による差
                d = (x_minus + 2 ** (n - 1 - i)) % (mod_popcount_x - 1)
                f_count(d)
                print(count)
            else: print('0')
    #print(x_plus, x_minus)
    
    return 0
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return bin(x).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
jpop=popcount(x)
jop=x%(jpop+1)
jom=x%(jpop-1)
jppp=jpop+1
jppm=jpop-1
for i in range(n):
  nijo=2**i
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>=jppp:
      a-=jppp
  else:
    a=jom-nijo%jppm
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

Submission status: Runtime Error

Solution code:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = (num + pow(2, n - (i + 1), ctmp)) % ctmp
    elif x[i] == '1':
        ctmp = cnt - 1
        tmp = (num - pow(2, n - (i + 1), ctmp)) % ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Submission status: Runtime Error

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


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

    X_minus = [0] * N # X_minus[i] = 2^i mod (bit_num - 1)
    X_plus = [0] * N # X_plus[i] = 2^i mod (bit_num + 1)
    X_minus[0], X_plus[0] = 1, 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)
    #print("X_minus={}".format(X_minus))
    #print("X_plus={}".format(X_plus))

    rem_minus = 0
    rem_plus = 0
    for i in range(N):
        if X[N-i-1] == '1':
            if bit_num != 1: rem_minus = (rem_minus + X_minus[i]) % (bit_num - 1)
            rem_plus = (rem_plus + X_plus[i]) % (bit_num + 1)
    #print(rem_minus, rem_plus)

    for i in range(N):
        if X[i] == '0':
            bit = bit_num + 1
            n = (rem_plus + X_plus[-i-1]) % bit
        if X[i] == '1':
            bit = bit_num - 1
            n = (rem_minus - X_minus[-i-1]) % bit
        if bit == 0 or bit == 1:
            print(bit)
            continue

        cnt = 1
        while n != 0:
            bit = bin(n).count("1")
            n %= bit
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    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以下になる
    # 2回目以降の操作はメモ化再帰
    # 初回popcountは2種類しかない Xのpopcountから足し引きすればよい

    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)
            if pc_m1 == 0:
                next_X_m1 += pow(2, N - 1 - i)
            else:
                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]

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

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

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

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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


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

    X_minus = [0] * N # X_minus[i] = 2^i mod (bit_num - 1)
    X_plus = [0] * N # X_plus[i] = 2^i mod (bit_num + 1)
    X_minus[0], X_plus[0] = 1, 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)
    print("X_minus={}".format(X_minus))
    print("X_plus={}".format(X_plus))

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

    for i in range(N):
        if X[i] == '0':
            bit = bit_num + 1
            n = (rem_plus + X_plus[-i-1]) % bit
        if X[i] == '1':
            bit = bit_num - 1
            n = (rem_minus - X_minus[-i-1]) % bit
        if bit == 0 or bit == 1:
            print(bit)
            continue

        cnt = 1
        while n != 0:
            bit = bin(n).count("1")
            n %= bit
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return bin(x).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
jpop=popcount(x)
jop=x%(jpop+1)
jom=x%(jpop-1)
jppp=jpop+1
jppm=jpop-1
for i in range(n-1,0,-1):
  nijo=2**i
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>=jppp:
      a-=jppp
  else:
    a=jom-nijo%jppm
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

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

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f(first_zero + pow(2, n-i-1, num_of_1 + 1)))
    else:
        print(1 + f(first_one - pow(2, n-i-1, num_of_1 - 1))

Submission status: Runtime Error

Solution code:
import sys #追加


n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)

one_cnt=s.count("1")
modp1=X%(one_cnt+1)
modm1=X%(one_cnt-1)

ans=[]

ans_memo=[0]*(2*(10**5)+2)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<2*(10**5)+1:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        if tmp_num==0:
            ans.append(0)
        else:
            
            tmp_num=(modm1-tmp%(one_cnt-1))
            if tmp_num<0:
                tmp_num+=(one_cnt-1)

            ans.append(DEF(tmp_num,1)+1)
        
    else:
        tmp_nunm=(tmp%(one_cnt+1)+modp1)%(one_cnt+1)
        #print(bin(tmp_num),n-i-1)
        #tmp_num=tmp_num%(one_cnt+1)
        ans.append(DEF(tmp_num,1)+1)

#print(ans_memo)

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

pc = X.count("1")

# X == 0 の時
if pc == 0:
    for i in range(N):
        print(1)
    exit()

sml = pc - 1
big = pc + 1

b = 0
mod_s = 0
mod_b = 0
for x in X[::-1]:
    if x == "1":
        mod_s += pow(2, b, sml)
        mod_s %= sml

        mod_b += pow(2, b, big)
        mod_b %= big

    b += 1

# print(mod_s, mod_b, sml, big)


ELE = []

b = 0
for x in X[::-1]:
    if x == "0":
        t = (mod_b + pow(2, b, big)) % big
        ELE.append((t, 1))
    else:
        t = (mod_s - pow(2, b, sml)) % sml
        if t < 0:
            t += sml
        ELE.append((t, 1))
    b += 1


def solve(x, c):
    if x == 0:
        return c

    b = 0
    nx = x
    while nx > 0:
        b += nx & 1
        nx >>= 1

    ret = solve(x % b, c + 1)
    return ret


ANS = []
for x, pc in ELE:
    ANS.append(solve(x, pc))

print("\n".join(map(str, ANS[::-1])))

Submission status: Runtime Error

Solution code:
import sys
import functools

@functools.lru_cache(maxsize=20000)
def popcount(n):
    return '{:b}'.format(n).count('1')


def f(n):
    i = 0
    # print(f'{n=}')
    while n:
        i += 1
        n %= popcount(n)
    return i


def resolve(in_):
    n = int(in_.readline())
    x = int(in_.readline(), 2)
    for i in range(n - 1, -1, -1):
        v = x ^ (2 ** i)
        print(f'{x=:b} {v=:b} {1<<i=:b}')
        print(f(v))


def main():
    resolve(sys.stdin.buffer)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
x_popcount=x.count('1')
f=[0]*(x_popcount+1)
for i in range(1,x_popcount+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_popcount-1
    else:
        x_changed=x[:i]+'1'+x[i+1:]
        popcount=x_popcount+1
    num_changed=int(x_changed,2)
    # print(x_changed,num_changed)
    if num_changed<popcount:
        print(f[num_changed])
    else:
        print(f[num_changed%popcount]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = [s for s in input()]


def popcount(n):
    cnt = n.count('1')
    mod = int(n, 2) % cnt
    return str(bin(mod))[2:]

# X = [s for s in '011']
# N = len(X)

for n in range(N):
    tmp = X.copy()
    tmp[n] = '1' if tmp[n] == '0' else '0'
    tmp_bin = ''.join(tmp)

    loop_cnt = 0
    while True:
        # print(tmp_bin)
        tmp_bin = popcount(tmp_bin)
        loop_cnt += 1

        if tmp_bin == '0':
            break

    print(loop_cnt)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

pc = X.count("1")

# X == 0 の時
if pc == 0:
    for i in range(N):
        print(1)
    exit()

sml = pc - 1
big = pc + 1

b = 0
mod_s = 0
mod_b = 0
for x in X[::-1]:
    if x == "1":
        mod_s += pow(2, b, sml)
        mod_s %= sml

        mod_b += pow(2, b, big)
        mod_b %= big

    b += 1

# print(mod_s, mod_b, sml, big)


ELE = []

b = 0
for x in X[::-1]:
    if x == "0":
        t = (mod_b + pow(2, b, big)) % big
        ELE.append((t, 1))
    else:
        t = (mod_s - pow(2, b, sml)) % sml
        ELE.append((t, 1))
    b += 1


def solve(x, c):
    if x == 0:
        return c

    b = 0
    nx = x
    while nx > 0:
        b += nx & 1
        nx >>= 1

    ret = solve(x % b, c + 1)
    return ret


ANS = []
for x, pc in ELE:
    ANS.append(solve(x, pc))

print("\n".join(map(str, ANS[::-1])))

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
b=int(s,2)
#n=100000
#b=2**100001-1
#s=format(b,"b")
bi=2**(n-1)
xf=s.count("1")
kp=b%(xf+1)
km=b%(xf-1)
for i in range(n):
  if s[i]=="1":
    k=(km-bi)%(xf-1)
  else:
    k=(kp+bi)%(xf+1)
  ans=1
  while k>0:
    x=format(k, 'b').count("1")
    k=k%x
    ans+=1  
  print(ans)
  bi=bi//2

Submission status: Runtime Error

Solution code:
from functools import lru_cache


def popcount2(x):
    ## https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266
    
    '''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


@lru_cache(None)
def func(n):
    if n == 0:
        return 0
    return func(n % popcount2(n)) + 1


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

for i in range(N):
    print(func(int(X, 2) ^ (1 << (N - i - 1))))

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以下になる
    # 2回目以降の操作はメモ化再帰
    # 初回popcountは2種類しかない Xのpopcountから足し引きすればよい

    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]

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

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

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

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
n=int(input())
m=input()
x=int(m,2)
li=list(m)
def popcount(x):
  return list(str(bin(x))).count("1")
def check(a):
  co=1
  while a!=0:
    co+=1
    a%=popcount(a)
  return co
jpop=popcount(x)
jop=x%(jpop+1)
jom=x%(jpop-1)
jppp=jpop+1
jppm=jpop-1
for i in range(0,n):
  nijo=2**(n-i-1)
  if li[i]=="0":
    a=jop+nijo%jppp
    if a>=jppp:
      a-=jppp
  else:
    a=jom-nijo%jppm
    if a<0:
      a+=jppm
  if a==0:
    print(1)
    continue
  print(check(a))

Submission status: Runtime Error

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    if d > 0:
        k0 = k % (d-1)
    k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        if x[i] == '1':
            dd = d - 1
            if dd == 0:
                wi(0)
                continue
            wi(f[(k0 - pow(2, n - i - 1, dd)) % n] + 1)
        else:
            dd = d + 1
            wi(f[(k1 + pow(2, n - i - 1, dd)) % n] + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def bin_a(i,bina):
    a=list(bina)
    if a[i]=='0':
        a[i]='1'
    else:
        a[i]='0'
    a="".join(a)
    return a

def count1(str):
    count=0
    n=len(str)
    for i in range(n):
        if str[i]=='1':
            count=count+1
    return count 

pop_bina=count1(bina)
num=int(bina,2)
trans1=num%(pop_bina+1)
trans2=num%(pop_bina-1)
for i in range(n):
    if bina[i]=='0':
        trans=trans1+2**i%(pop_bina+1)
    else:
        trans=trans2-2**i%(pop_bina-1)
    count=1
    while trans!=0:
        b_trans=format(trans, 'b')
        div=count1(b_trans)
        trans=trans%div
        count=count+1
    print(count)

Submission status: Runtime Error

Solution code:
#%%timeit
N = int(input())
X_str = input()

X = int(X_str, 2)

popcount_cache = [0, 1] + [-1] * 3 * 10 ** 5
for x in range(2, 300000):
  popcount_cache[x] =  popcount_cache[x // 2] + x % 2

# def popcount(x):
#   global popcount_cache
#   if popcount_cache[x] < 0:
#     # tmp = x
#     # p = 0
#     # while tmp not in popcount_cache:
#     #   p += tmp % 2
#     #   tmp //= 2
#     popcount_cache[x] = popcount(x // 2) + x % 2
#   return popcount_cache[x]

count_cache = [0, 1] + [-1] * 3 * 10 ** 5
for x in range(2, 300000):
  count_cache[x] = 1 + count_cache[x % popcount_cache[x]]


# def count(x):
#   #print('count', x)
#   global count_cache
#   if count_cache[x] < 0:
#     #print('count', x, popcount(x), x % popcount(x))
#     count_cache[x] = 1 + count(x % popcount[x])
#   return count_cache[x]
  
popcount_N = 0
for s in X_str:
  if s == '1':
    popcount_N += 1

Xmodpp = X % (popcount_N + 1)
Xmodpn = X % (popcount_N - 1)

ans = []
for i in range(N):
  if i == 0:
    modpp = 1
    modpn = 1
  else:
    modpp = (modpp * 2) % (popcount_N+1)
    modpn = (modpn * 2) % (popcount_N-1)
  if X_str[N - 1 - i] == '0':
    ans.append(count_cache[  (Xmodpp + modpp) % (popcount_N + 1)] + 1)
  else:
    ans.append(count_cache[  (Xmodpn - modpn) % (popcount_N - 1)] + 1)

ans.reverse()
for a in ans:
  print(a)