Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

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

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

Input

Input is given from Standard Input in the following format:

N
X

Output

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

Sample Input 1

3
011

Sample Output 1

2
1
1

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

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

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

Sample Input 2

23
00110111001011011001110

Sample Output 2

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



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:
import sys
import  math
from heapq import *
import fractions
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

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

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

mlist_num_1up=[0]*N
mlist_num_1down=[0]*N
mlist_num_1up[0]=1
mlist_num_1down[0]=1

if(num_1==0):
    for i in range(N):
        a=1
        print(a)
        sys.exit(0)
        
for i in range(1,N):
    mlist_num_1up[i]=(mlist_num_1up[i-1]*2)%(num_1+1)
    mlist_num_1down[i]=(mlist_num_1down[i-1]*2)%(num_1-1)

mlist_num_1up.reverse()
mlist_num_1down.reverse()

upmod_ori=0
downmod_ori=0
for i in range(N):
    if(X[i]=='1'):
        upmod_ori+=mlist_num_1up[i]
        downmod_ori+=mlist_num_1down[i]


fans=[0]*31
fans[0]=0
fans[1]=1
for i in range(2,31):
    mod=0
    for p in range(7):
        if((i>>p) & 1):
            mod+=1
    fans[i]=fans[i%mod]+1
    
for i in range(N):
    if(X[i]=='1'):
        mod=downmod_ori-mlist_num_1down[i]
        mod%=(num_1-1)
    else:
        mod=upmod_ori+mlist_num_1up[i]
        mod%=(num_1+1)
    mod1=0
    for p in range(31):
        if((mod>>p) & 1):
            mod1+=1
    print(fans[mod1]+1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
first_bit_cnt = [X.count('1')]*N
for i in range(N):
    if X[i] == '1':
        first_bit_cnt[i] -= 1
    else:
        first_bit_cnt[i] += 1
X = int('0b'+X,0)
target = [0]*N
bit = 1
for i in range(N):
    target[N-1-i] = X^bit
    bit = bit<<1
popcount = [0]*(N+1)
for i in range(1,N+1):
    tmp = bin(i)[2:]
    popcount[i] = tmp.count('1')
ans = [0]*N
for i in range(N):
    tmp = target[i]%first_bit_cnt[i]
    cnt = 1
    if tmp == 0:
        ans[i] = cnt
        continue
    while True:
        tmp = tmp%popcount[tmp]
        cnt += 1
        if tmp == 0:
            break
    ans[i] = cnt
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)

p = [0]*(2*10**5+1)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        n = n % b
        p[i] += 1

for i in range(1, N+1):
    d = D
    c = C
    if X[i-1] == "1":
        c -= 1
        d -= 1 << (N-i)
    else:
        c += 1
        d += 1 << (N-i)

    d = d % c
    print(p[d]+1)

Submission status: Runtime Error

Solution code:
def toggleKthBit(n, k): 
  return (n ^ (1 << (k-1))) 
def popcount(x):
    x -= (x >> 1) & 0x5555555555555555
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    return ((x * 0x0101010101010101) & 0xffffffffffffffff ) >> 56
N = int(input())
X = int(input())

ans = -1
dp = [-1] * 100000000
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    if dp[ans] != -1:
      ans = ans % dp[ans]
    else:
      dp[ans] = popcount(ans)
      ans = ans % dp[ans]
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)
    https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266'''

    # 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

N = int(input())
X = input()
Xn = int(X, 2)
F = [-1] * (2**N+10)
F[0] = 0
F[1] = 1
popcounts = [-1] * (2**N+1)
for i in range(N):
    if X[i] == "1":
        y = Xn - 2**(N-i-1)
    else:
        y = Xn + 2**(N-i-1)
    cnt = 0
    yy = y
    while True:
        if F[y] == -1:
            if popcounts[y] == -1:
                popcounts[y] = popcount(y)
            y = y % popcounts[y]
            cnt += 1
            continue
        else:
            F[yy] = cnt + F[y]
            print(F[yy])
            break

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N = int(input())
X = int(input())
xx = int(str(X),2)
iti = str(X).count('1')

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

def rec(a):
    ico = str(bin(a)).count('1')
    b = a%ico
    if b == 0:
        dp[b] = 1
        return 1
    if dp[b] != -1:
        dp[a] = dp[b] + 1
        return dp[a]
    res = rec(b) +1
    return res
for i in range(N-1,-1,-1):
    han = 2**i
    if xx & han:
        ans = rec(xx-han)
        print(ans)
    else:
        ans = rec(xx+han)
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
Xs = list(map(int, list(input())))
rXs = Xs[::-1]

num = sum(Xs)
pos = 0
neg = 0

pow_pos = [0]*N
pow_neg = [0]*N
dic = {0: 0, 1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 2, 8: 1}

for m in range(1, num+2):
    c = bin(m)[2:].count('1')
    dic[m] = dic[m%c]+1
    
for i in range(N):
    pow_pos[i] = pow(2, i, num+1)
    if not num==1:
        pow_neg[i] = pow(2, i, num-1)

for i, x in enumerate(rXs):
    if x==0:
        continue
    pos += pow_pos[i]
    if not num==1:
        neg += pow_neg[i]

anss = []
for i, x in enumerate(rXs):
    if num==1 and x==1:
        ans.append(0)
        continue
    if x==0:
        mod = num+1
        tmp = (pos+pow_pos[i])%mod
    else:
        mod = num-1
        tmp = (neg-pow_neg[i])%mod
    ans = dic[tmp]+1
    anss.append(ans)

for ans in anss[::-1]:
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
 
 
def fx(x):
    xbin = bin(x)
    popcount = xbin.count("1")
    return (x % popcount)
 
 
for i in range(N):
    fn = 0
    if X[i] == "0":
        Xi = int(X, 2) + 2 ** (N - i - 1)
    else:
        Xi = int(X, 2) - 2 ** (N - i - 1)
 
    while True:
        Xi = fx(Xi)
        fn += 1
        if Xi == 0:
            break
        else:
            pass
 
    print(fn)

Submission status: Runtime Error

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

MAX = 2*10**5+1
ppc = [0]*MAX

def popcount(n):
  if ppc[n]>0:
    ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

for i in range(2*10**5):
  popcount(i+1)
  
bit = int('0b'+x,0)

for i in range(n,0,-1):
  tmp = bit ^ (1 << (i-1))
  bn = bin(tmp).count('1')      
  print(ppc[tmp%bn]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
x_cou = x.count("1")
x_bin = int(x,2)


list_f = [0 for i in range(10**6+1)]
for i in range(1,10**6+1):
  bi = bin(i).count("1")
  if i%bi==0:
    list_f[i] =1
  else:
    amari = i%bi
    list_f[i] = 1+ list_f[amari]
#print(list_f[:20])
if int(x)==1:
  print(1)
  exit()
  
for i in range(0,n):
  if x[i]=="0":
    t = x_bin+ 2**(n-1-i)
    t_bin=bin(t).count("1")
    t_amari = t%t_bin
    if t_amari==0:
      print(1)
    else:
      print(list_f[t_amari]+1)
 
  else:
    t = x_bin - 2**(n-1-i)
    t_bin=bin(t).count("1")
    t_amari = t%t_bin
#    print(1,t_amari)
    if t_amari==0:
      print(1)
    else:
      print(list_f[t_amari]+1)

Submission status: Runtime Error

Solution code:
def main()
    n=int(input())
    x=int(input(),2)
    def nth_bit(num,n):
        return num ^ (1 << n)
    def popdividenumber(n):
        ans=0
        while True:
            n=n%(bin(n).count("1"))
            ans+=1
            if n==0:
                return ans
    for i in range(1,n+1):
        xi=nth_bit(x,n-i)
        if xi==0b1:
          print(0)
        else:
          print(popdividenumber(xi))
main()

Submission status: Runtime Error

Solution code:
def popcount(n):
    count = 0
    while n > 0:
        count += 1
        n = n % bin(n).count("1")
    return count


n = int(input())

a = input()

#x = bin(int(input()))

x = int(a,2)
nlis = range(n)

c1 = bin(x).count("1")

for i in reversed(nlis):
    check = 2 ** i
    ans = x ^ check

    if a[i] == "0":
        c2 = c1 + 1
    else:
        c2 = c1 - 1

    n = n % c2

    ans = popcount(ans)

    #ans = bin(ans)

    print(ans)

Submission status: Runtime Error

Solution code:
memo = {}
def f(x):
    if x==0:
        return 0
    if x==1:
        return 1
    if x in memo:
        return memo[x]
    k = sum(list(map(int,list(bin(x)[2:]))))
    memo[x] = 1+f(x%k)
    return memo[x]
    
N = int(input())
X = input().strip()
n = sum(list(map(int,list(X))))
C = {i:0 for i in range(N)}  # mod n-1
C[0] = 1
for i in range(1,N):
    C[i] = (C[i-1]*2)%(n-1)
D = {i:0 for i in range(N)} # mod n+1
D[0] = 1
for i in range(1,N):
    D[i] = (D[i-1]*2)%(n+1)
cnt0 = 0
cnt1 = 0
for i in range(N):
    if X[i]=="1":
        cnt0 = (cnt0+C[N-1-i])%(n-1)
        cnt1 = (cnt1+D[N-1-i])%(n+1)
for i in range(N):
    if X[i]=="1":
        a = (cnt0-C[N-1-i])%(n-1)
        print(1+f(a))
    else:
        a = (cnt1+D[N-1-i])%(n+1)
        print(1+f(a))

Submission status: Runtime Error

Solution code:
def pop(a):
    b = a
    num = 0
    while b > 0:
        if b % 2 == 1:
            num += 1
        b = int(b/2)
    return int(num)


def function(N, X):
    X = [int(X[i]) for i in range(N)]
    for j in range(N):
        number = 0
        for i in range(N):
            if i == j:
                if X[i] == 0:
                    number += 2**(N-i-1)
            else:
                number += 2**(N-i-1)*X[i]
        ans = 1
        if pop(number) == 0:
            print(ans)
        else:
            a = number % pop(number)
            while a > 0:
                a = a % (pop(a))
                ans += 1
            print(ans)


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

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def powmod(x, n, k):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x
            ans %= k
        x = x*x
        x %= k
        n = n >> 1
    return ans % k

def popcnt(n):
    return bin(n).count("1")

def main():
    N = I()
    X = S()
    cnt = 0
    for i in range(len(X)):
        if int(X[i]) & 1  == 1:
            cnt += 1
    a = cnt + 1
    b = cnt - 1

    pow2a = [0] * (N+1)
    pow2b = [0] * (N+1) # 2 ^ i mod b

    suma = 0
    sumb = 0
    dX = X[::-1]
    for i in range(N):
        pow2a[i] = powmod(2, i, a)
        pow2b[i] = powmod(2, i, b)
        if int(dX[i]) == 1:
            suma += pow2a[i]
            sumb += pow2b[i]
            suma %= a
            sumb %= b
    # rev
    X = X[::-1]
    # i=0 -> 2^(len(X) - i)
    # 0 ... len(X) - 1
    subx = []
    ans = [1] * N
    for i in range(len(X)):
        cp_suma = suma
        cp_sumb = sumb
        if int(X[i]) == 0:
            # 1にするので、加算してからaでわる
            # i = 0なら2^0 = 1のくらい
            cp_suma += pow2a[i]
            cp_suma %= a
            res = cp_suma
        else:
            # 0 にするので引き算してからbでわる
            cp_sumb -= pow2b[i]
            cp_sumb %= b
            res = cp_sumb
        subx.append(res)

    subx = subx[::-1]
    for i, a in enumerate(subx):
        while a > 0:
            a %= popcnt(a)
            ans[i] += 1
    for a in ans:
        print(a)


main()

Submission status: Runtime Error

Solution code:

def popcnt(x):
    return bin(x).count("1")

def main():
    N = int(input())
    Xs = input()
    X = int(Xs, 2)
    d = popcnt(X)

    lut = [0] * N
    lut[1] = 1
    for i in range(2, N):
        Xi = i % popcnt(i)
        lut[i] = lut[Xi] + 1

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm
    # print(lut)
    # print(format(X, 'b'))
    
    ans = []
    for i in range(N):
        mask = 1 << (N-i-1)
        Xi = X ^ mask
        if Xs[i] == '1':
            m = (mm - pow(2, N-i-1, dm)) % dm
            # m = (mm - mask) % dm
        else:
            # m = (mp + mask) % dp
            m = (mp + pow(2, N-i-1, dp)) % dp
        # print(Xi, Xs[N-i-1], m)
        # print(format(Xi, 'b'))

        # Xi2 = Xi % dd
        # ans.append((Xi, Xi2))
        ans.append(lut[m] + 1)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

for i in range(N):
    res, tmp = 1, int(X, 2) ^ (1<<(N-i-1))
    while (tmp := (tmp % len(format(tmp, 'b').replace('0','')))) != 0:
        res += 1
    print(res)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
import sys
sys.setrecursionlimit(10**6)
from functools import *
@lru_cache(None)
def popcount(x):
  if x==0: return 0
  return popcount(x%bin(x).count('1'))+1
for i in range(n):
  if int(x[i]):
    d=c-1
    if c<1: print(0)
    print(popcount((t-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    print(popcount((t+pow(2,n-i-1,d))%d)+1)

Submission status: Runtime Error

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)

    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


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

X_int = int(X, 2)

for i in range(N):
    mask = ['0']*N
    mask[i] = '1'
    mask = int(''.join(mask), 2)
    Xi = X_int ^ mask
    
    n = Xi
    ans = 0
    while n > 0:
        ans += 1
        n %= popcount(n)
    print(ans)

Submission status: Runtime Error

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

# memo = [0]*(n+1)

# for val in range(1, n+1):
#     tmp = val
#     cnt = 0
#     while tmp > 0:
#         if tmp & 1:
#             cnt += 1
#             tmp = (tmp-1)//2
#         else:
#             tmp = tmp//2
#     memo[val] = memo[val % cnt] + 1


x_cnt = 0
for i, y in enumerate(x):
    if y == 1:
        x_cnt += 1

aa = x_cnt + 1
bb = x_cnt - 1

a = [1 % aa]
b = [1 % bb]

for _ in range(n-1):
    a.append(a[-1]*2 % aa)
    b.append(b[-1]*2 % bb)

a = a[::-1]
b = b[::-1]

x_ps = 0
x_ng = 0
for i, val in enumerate(x):
    if val == 1:
        x_ps += a[i]
        x_ng += b[i]

for i in range(n):
    ans = 0
    if x[i] == 0:
        cnt = x_cnt + 1
        val = (x_ps + a[i]) % cnt
    else:
        cnt = x_cnt - 1
        if cnt == 0:
            print(ans)
            continue
        val = (x_ng - b[i]) % cnt

    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1) // 2
        else:
            tmp = tmp // 2

    ans += 1
    while val > 0:
        ans += 1
        val = val % cnt
        tmp = val % cnt
        cnt = 0
        while tmp > 0:
            if tmp & 1:
                cnt += 1
                tmp = (tmp-1) // 2
            else:
                tmp = tmp // 2
    print(ans)

Submission status: Runtime Error

Solution code:
def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


def calc(val, my_dict, cnt):
    num_one = bin(val).count('1')
    if val in my_dict:
        return cnt + my_dict[val]
    else:
        if num_one == 0:
            return cnt
        nex = val % num_one
        ret = calc(nex, my_dict, cnt+1)
        my_dict[val] = ret - cnt
        return ret


n = int(input())
x = input()
tmp = list(x)
my_dict = dict()

num_one = tmp.count('1')
num_one_plus = num_one + 1
num_one_minus = num_one - 1

modsum_plus = 0
modsum_minus = 0
for i in range(1, n+1):
    if tmp[-i] == '1':
        modsum_plus += modpow(2, i-1, num_one_plus) % num_one_plus
        modsum_minus += modpow(2, i-1, num_one_minus) % num_one_minus

for i in range(n):
    if tmp[i] == '0':
        val = (modsum_plus + modpow(2, n-i-1, num_one_plus)) % num_one_plus
    else:
        val = (modsum_minus - modpow(2, n-i-1, num_one_minus)) % num_one_minus
    print(calc(val, my_dict, 1))

Submission status: Runtime Error

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

def popcount(num):
    return num.count('1')

popc = [-1]*(n+1)
dp = [-1]*(n+1)#index=わったあまり

for i in range(1,n+1):
    now = list(x)
    if now[i-1] == '0':
        now[i-1] = "1"
    else:
        now[i-1] = "0"
    now = "".join(now)
    
    ans = 0
    hozon = int(now,2)%popcount(now)
    while True:
        """
        if popc[int(now,2)] == -1:
            popc[int(now,2)] = popcount(now)
        """
        
        amari = int(now,2)%popcount(now) 
        if dp[amari] != -1:
            ans += dp[amari]
            dp[hozon] = ans
            break
        now = amari
        ans += 1
        if now == 0:
            break
        now = bin(now)[2:]
    
    print(ans)

Submission status: Runtime Error

Solution code:
def toggleKthBit(n, k): 
  return (n ^ (1 << (k-1))) 
def popcount(x):
    x -= (x >> 1) & 0x5555555555555555
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    return ((x * 0x0101010101010101) & 0xffffffffffffffff ) >> 56
N = int(input())
X = int(input())

ans = -1
dp = [-1] * 100000000
for i in range(N, 0, -1):
  count = 0
  ans = toggleKthBit((int(str(X), 2)), i)
  while ans != 0:
    if dp[ans] != -1:
      ans = ans % dp[ans]
    else:
      dp[ans] = bitsoncount(ans)
      ans = ans % dp[ans]
    count += 1
  print(count)

Submission status: Runtime Error

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
X = (stdin.readline().rstrip())
cnt = X.count("1")

X = list(X)

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

for i in range(1,N+1):
    tmp = X[:]
    if tmp[i-1] == "0":
        tmp[i-1] = "1"
        cnt_t = cnt + 1
    else:
        tmp[i-1] = "0"
        cnt_t = cnt - 1
    
    amari = int("".join(tmp),2) % cnt_t
    ans = 1
    while amari != 0:
        amari = f[amari]
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def funk(x, temp_count):
    if x in log_dict:
        ans = log_dict[x]
        return ans
    x_temp = x % temp_count
    if x_temp == 0:
        log_dict[x] = 1
        return 1
    temp_count = bin(x_temp).count("1")
    ans = funk(x_temp, temp_count)
    ans += 1
    log_dict[x] = ans
    return ans
n = int(input())
bit = input()
bit_list = list(bit)
count = bit.count("1")
log_dict = {}
# log_dict[1] = 1
# log_dict[2] = 1
for i in range(n):
    temp_count = count
    if bit[i] == "1":
        temp_count -= 1
        bit_list[i] = "0"
        x_bit = ''.join(bit_list)
        bit_list[i] = "1"
    else:
        temp_count += 1
        bit_list[i] = "1"
        x_bit = ''.join(bit_list)
        bit_list[i] = "0"
    x = int(x_bit, 2)
    ans = funk(x, temp_count)
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()[::-1]
cnt = s.count('1')

p1 = sum(pow(2, i, cnt+1) * (s[i] == '1') for i in range(n))
if cnt > 1:
    m1 = sum(pow(2, i, cnt-1) * (s[i] == '1') for i in range(n))

def op(n):
    popcnt = bin(n).count('1')
    return n%popcnt

pre = [0]*100000
for i in range(1,100000):
    pre[i] = pre[op(i)] + 1

def solve(i):
    if s[-i] == '0':
        r = (p1 + pow(2, n-i, cnt+1))%(cnt+1)
    else:
        if cnt == 1:
            return 1
        r = (m1 - pow(2, n-i, cnt-1))%(cnt-1)
    return 1 + pre[r]

for i in range(n):
    print(solve(i+1))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N = int(input())
X = input()
x = int(X, 2)
y = X.count('1')
if y == 0:
    print(*[0]*N, sep='\n')
    exit()
else:
    x2 = x % (y-1)
x1 = x % (y+1)

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

d = [0] * (2*10**5+5)
for i in range(2*10**5+5):
    d[i] = f(i)

for i in range(N):
    if x >>(N - i - 1) & 1:
        # print(f(x-pow(2, N-i-1)))
        print(d[(x2 - pow(2, N - i - 1, y-1)) % (y-1)] + 1)
    else:
        # print(f(x+pow(2, N-i-1)))
        print(d[(x1 + pow(2, N - i - 1, y+1)) % (y+1)] + 1)

Submission status: Runtime Error

Solution code:
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)
    https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266'''

    # 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

N = int(input())
X = input()
Xn = int(X, 2)
F = [-1] * (2**N)
F[0] = 0
F[1] = 1
popcounts = [-1] * (2**N)
for i in range(N):
    if X[i] == "1":
        y = Xn - 2**(N-i-1)
    else:
        y = Xn + 2**(N-i-1)
    cnt = 0
    yy = y
    while True:
        if F[y] == -1:
            if popcounts[y] == -1:
                popcounts[y] = popcount(y)
            y = y % popcounts[y]
            cnt += 1
            continue
        else:
            F[yy] = cnt + F[y]
            print(F[yy])
            break

Submission status: Runtime Error

Solution code:
from math import *
def popcount(x):
    s=0
    y=int(log2(x))+2
    for i in range(y):
        if(x>>i)&1:
            s+=1
    return x%s
n=int(input())
x=input()[::-1]
#1がなんこ出るのか
c=x.count("1")
#c+1とc-1だけ考えれば良い
#c=1の時場合分け
#m[i][j]:2^iまで考えたときのmod(c+j-1)
m=[[1%(c-1),1%(c+1)]]
for i in range(1,n):
    m.append([(2*m[-1][0])%(c-1),(2*m[-1][1])%(c+1)])
#一個だけ変えたいので全体を求める
l=[0,0]
for i in range(n):
    if x[i]=="1":
        l[0]+=m[i][0]
        l[1]+=m[i][1]
        l[0]%=(c-1)
        l[1]%=(c+1)
#最初以外はpopcount使って間に合う
ans=[0]*n
for i in range(n):
    if x[i]=="1":
        if c-1==0:
            ans[i]=0
            continue
        p=(l[0]+(c-1)-m[i][0])%(c-1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
    else:
        p=(l[1]+m[i][1])%(c+1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
ans=ans[::-1]
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
def popcount(n):
    count = 0
    while n > 0:
        count += 1
        n = n % bin(n).count("1")
    return count


n = int(input())

a = input()

x = int(a,2)
nlis = range(n)

c1 = bin(x).count("1")

for i in reversed(nlis):
    check = 2 ** i
    ans = x ^ check

    if a[i] == "0":
        c2 = c1 + 1
    else:
        c2 = c1 - 1

    n = n % c2

    ans = popcount(ans)


    print(ans)

Submission status: Runtime Error

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

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

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

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

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

n = int(input())
s = input()

popcnt = 0
for c in s:
    if c=='1':
        popcnt += 1

num = int(s, 2)
# print(num)
# print(num%(popcnt-1))
# print(num%(popcnt+1))

p_l = num%(popcnt-1)
p_h = num%(popcnt+1)

next = [-1]*n
for i in range(n):
    # print(s[i])
    if s[i]=='0':
        next[i] = (p_h + 2**(n-i-1)%(popcnt+1))%(popcnt+1)
    else:
        next[i] = (p_l - 2**(n-i-1)%(popcnt-1))%(popcnt-1)

# print(next)

d = {0:0}
for number in next:
    if number in d.keys():
        continue
    m = number
    tmp = 0
    while not m in d.keys():
        m = m%popcount(m)
        tmp += 1
    d[number] = d[m]+tmp

for number in next:
    print(d[number]+1)

Submission status: Runtime Error

Solution code:
def m():
    N = int(input())
    X = input()
    R = list(reversed(X))

    def f(n):
        r = 0
        while n != 0:
            x = bin(n)[2:].count('1')
            n = n % x
            r += 1
        return r

    total = 0
    for i in range(N):
        total += int(R[i]) * pow(2, i)

    base = X.count('1')
    for i in range(N):
        ans = 0
        if X[i] == '1':
            tmp = total - pow(2, N - 1 - i)
            tmp %= (base - 1)
            ans = f(tmp) + 1
        else:
            tmp = total + pow(2, N - 1 - i)
            tmp %= (base + 1)
            ans = f(tmp) + 1
        print(ans)


m()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
ans = [0]*(n+1)

for i in range(1,n+1):
    s = format(i, 'b')
    c = s.count('1')
    a = i%c
    ans[i] += 1
    ans[i] += ans[a] 

one_cnt = x.count('1')
numx = int(x,2)
for i in range(n):
    temp = one_cnt
    if x[i]=='0':
        temp += 1
        num = numx + 2**(n-1-i)
    else:
        temp -= 1
        num = numx - 2**(n-1-i)
    print(ans[num%temp]+1)

Submission status: Runtime Error

Solution code:
from collections import Counter

N = int(input())
cnt = Counter(str(X))['1']
cnt = str(bin(cnt))[2:]
X = bin(int(X, 2))

Submission status: Runtime Error

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

V = [1]*250000
for i in range (2, 250001):
    a = i
    b = str(bin(i))
    c = b.count('1')
    d = a%c
    if d ==0:
        V[i-1] = 1
    else:
        V[i-1] = V[d-1]+1

length = len(X)

binaryA = []
for i in range (0, length):
    binaryA.append(2**i)

for i in range (0, length):
    a = int(X, base = 2)^binaryA[length-1-i]
    b = str(bin(a))
    c = b.count('1')
    d = a%c
    if d ==0:
        print(1)
    else:
        print(V[d-1]+1)

Submission status: Runtime Error

Solution code:
n = 100000
ans_count = [-1 for _ in range(n)]
memo = [-1 for _ in range(n)]
for i in range(1,n+1):
    b = bin(i)
    b=list(b)
    a = b.count("1")
    f = i%a
    if f == 0:
        ans_count[i-1]=1
    else:
        ans_count[i-1] = ans_count[f-1]+1

ans_count = [0]+ ans_count

n= int(input())
inp = input()
x = list(inp)
org = int(inp, 2)
l = x.count("1")
for i in range(n):
    a = x[i]
    if a=="0":
        N = org+(2**(n-i-1))
        m= N%(l+1)
#         print("m", m)
        print(ans_count[m]+1)
    else:
        N = org-(2**(n-i-1))
        m=N%(l-1)
#         print("m", m)
        print(ans_count[m]+1)

Submission status: Runtime Error

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

n = int(input())
xs = list(input())[::-1]

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

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

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

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

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

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        return ret

ans = []
for i in range(n):
    ans.append(dfs(x^(1<<i)))
for a in ans[::-1]:
    print(a)

Submission status: Runtime Error

Solution code:
# @author 

import sys

class DAnythingGoesToZero:
    def solve(self, tc=0):
        n = int(input())
        # n = 10 ** 5
        x = input().strip()
        cache = [-1] * (n + 1)
        cache[0] = 0
        for nb in range(n + 1):
            v = 0
            i = nb
            while cache[i] == -1:
                i %= bin(i).count('1')
                v += 1

            cache[nb] = v + cache[i]

        # print(cache[8191])

        def brem(N, D):
            n = len(N)
            R = 0
            for i in range(n - 1, -1, -1):
                R <<= 1
                R |= int(N[n - 1 - i])
                if R >= D:
                    R -= D
            return R

        x = list(x)
        ones = x.count('1')
        r1 = brem(x, ones + 1)
        r2 = brem(x, ones - 1)
        for i in range(n):
            if x[i] == '0':
                # print((r + pow(2, n - 1 - i, ones + 1)) % (ones + 1), '*')
                print(cache[(r1 + pow(2, n - 1 - i, ones + 1)) % (ones + 1)] + 1)
            else:
                print(cache[(r2 - pow(2, n - 1 - i, ones - 1)) % (ones - 1)] + 1)
            # x[i] = str(int(x[i]) ^ 1)
            # print(cache[brem(x, x.count('1'))] + 1)
            # x[i] = str(int(x[i]) ^ 1)

solver = DAnythingGoesToZero()
input = sys.stdin.readline

solver.solve()

Submission status: Runtime Error

Solution code:
for i in range(N):
    X2 = copy.copy(X)
    if X[i] == '0':
        X2[i] = '1'
    elif X[i] == '1':
        X2[i] = '0'
    X3 = "".join(X2)
    X4 = int(X3,2)
    ii = 0
    while X4!=0:
        X4 = X4 % str(bin(X4)).count('1')
        ii+=1
    print(ii)