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 collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n):
    if memo[n] >= 0:
        rst = memo[n]
    else:
        tmp = n
        one = 0
        while tmp > 0:
            one += tmp & 1
            tmp >>= 1
        m = n % one
        rst = 1 if m == 0 else 1 + dfs(m)
        memo[n] = rst
    return rst


N = int(input())
# X = input()
X = list(map(int, list(input())))
one = Counter(X)[1]

if one == 0:
    print(0)
    exit()


Sm = 0
mm = one - 1
Sp = 0
mp = one + 1
tp = 1
tm = 1
for i in range(N - 1, -1, -1):
    tm %= mm
    tp %= mp
    if X[i] == 1:
        Sp += tp
        Sm += tm
        Sm %= mm
        Sp %= mp
    tm *= 2
    tp *= 2


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

# x = int(X, 2)
# for i in range(N):
#     ans = dfs(x ^ (1 << ((N - 1) - i)))
#     print(ans)
for i in range(N):
    if X[i] == 0:
        m = (Sp + pow(2, N - 1 - i, mp)) % mp
    else:
        m = (Sm - pow(2, N - 1 - i, mm)) % mm
    
    if m == 0:
        print(1)
    else:
        print(1 + dfs(m))

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n):
    if memo[n] >= 0:
        rst = memo[n]
    else:
        tmp = n
        one = 0
        while tmp > 0:
            one += tmp & 1
            tmp >>= 1
        m = n % one
        rst = 1 if m == 0 else 1 + dfs(m)
        memo[n] = rst
    return rst


N = int(input())
# X = input()
X = list(map(int, list(input())))
one = Counter(X)[1]

Sm = 0
mm = one - 1
Sp = 0
mp = one + 1
tp = 1
tm = 1
for i in range(N - 1, -1, -1):
    tm %= mm
    tp %= mp
    if X[i] == 1:
        Sp += tp
        Sm += tm
        Sm %= mm
        Sp %= mp
    tm *= 2
    tp *= 2


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

# x = int(X, 2)
# for i in range(N):
#     ans = dfs(x ^ (1 << ((N - 1) - i)))
#     print(ans)
for i in range(N):
    if X[i] == 0:
        m = (Sp + pow(2, N - 1 - i, mp)) % mp
    else:
        m = (Sm - pow(2, N - 1 - i, mm)) % mm
    
    if m == 0:
        print(1)
    else:
        print(1 + dfs(m))

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n):
    if memo[n] >= 0:
        rst = memo[n]
    else:
        tmp = n
        one = 0
        while tmp > 0:
            one += tmp & 1
            tmp >>= 1
        m = n % one
        rst = 1 if m == 0 else 1 + dfs(m)
        memo[n] = rst
    return rst


N = int(input())
X = input()
# X = list(map(int, list(input())))
# one = Counter(X)[1]


memo = [-1] * (1 << (N + 1))
memo[0] = 0

x = int(X, 2)
for i in range(N):
    ans = dfs(x ^ (1 << ((N - 1) - i)))
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter


def dfs(n):
    if memo[n] >= 0:
        rst = memo[n]
    else:
        tmp = n
        one = 0
        while tmp > 0:
            one += tmp & 1
            tmp >>= 1
        m = n % one
        rst = 1 if m == 0 else 1 + dfs(m)
        memo[n] = rst
    return rst


N = int(input())
X = input()
# X = list(map(int, list(input())))
# one = Counter(X)[1]


memo = [-1] * (1 << (N + 1))
memo[0] = 0

x = int(X, 2)
for i in range(N):
    ans = dfs(x ^ (1 << ((N - 1) - i)))
    print(ans)

Submission status: Runtime Error

Solution code:
# D - Anything Goes to Zero
def get_fx(n, binary):
	global dic
	
	fn = n
	count = 0
	
	while True:
		if fn in dic.keys():
			dic[n] = dic[fn] + count
			return dic[n]
		else:
			popcount = binary.count('1')
			fn %= popcount
			binary = bin(fn)
			count += 1

			if fn == 0:
				dic[n] = count
				return count


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

dic = dict()

for i in range(N):
	if X[i] == '0':
		s = '1'
	else:
		s = '0'
	
	if i == 0:
		binary = s + X[i+1:]
	else:
		binary = X[:i] + s + X[i+1:]
	
	n = int(binary, 2)
	print(get_fx(n, binary))

Submission status: Runtime Error

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

# D - Anything Goes to Zero
def get_fx(n, binary):
	global dic
	
	fn = n
	count = 0
	
	while True:
		if fn in dic.keys():
			dic[n] = dic[fn] + count
			return dic[n]
		else:
			popcount = binary.count('1')
			fn %= popcount
			binary = bin(fn)
			count += 1

			if fn == 0:
				dic[n] = count
				return count


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

dic = dict()

for i in range(N):
	if X[i] == '0':
		s = '1'
	else:
		s = '0'
	
	if i == 0:
		binary = s + X[i+1:]
	else:
		binary = X[:i] + s + X[i+1:]
	
	n = int(binary, 2)
	print(get_fx(n, binary))

Submission status: Runtime Error

Solution code:
n = int(input())
X = input()
x = int(X,2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+2)
for i in range(1,bitx+2):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = 0
xmm = 0

for i in range(n):
    if X[i] == '1':
        xmp += pow(2, n-(i+1), bitp)
        xmm += pow(2, n-(i+1), bitm)
if bitx != 1:
    for i in range(n):
        if X[i] == '1':
            xm = (xmm - pow(2,n-i-1,bitm)) % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))

else:
    for i in range(n):
        if X[i] == '1':
            l.append(str(0))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))

print('\n'.join(l))

Submission status: Runtime Error

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

dd={}
def get_f(v):
	global dd
	if v == 0:
		return 0
	if v in dd:
		return dd[v]
	
	pn = bin(v).count('1')
	ret = 1+get_f(v % pn)
	dd[v] = ret
	return ret

def main():
	n = int(input())
	#b , c = tin()
	s = input()
	sa=s[::-1]
	n_one=s.count('1')
	#pa(n_one)
	#pa(s)
	amari_p = 0
	amari_n = 0
	for i, c in enumerate(sa):
		if c == '1':
			amari_p += pow(2,i,n_one+1)
			amari_n += pow(2,i,n_one-1)
			amari_p %= n_one+1
			amari_n %= n_one-1
		
	#pa(amari_p)
	#pa(amari_n)
	for i, c in enumerate(s):
		keta = n - i - 1
		if c == '1':
			ta = amari_n
			ta -= pow(2,keta,n_one-1)
			ta %= n_one-1
		else:
			ta = amari_p
			ta += pow(2, keta, n_one+1)
			#pa(('q',ta))
			ta %= n_one+1
		#pa((keta,pow(2,keta),ta))
		print(get_f(ta)+1)
		
		
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

Solution code:
n = int(input())
X = input()
x = int(X,2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+2)
for i in range(1,bitx+2):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = 0
xmm = 0
for i in range(n):
    if X[i] == '1':
        xmp += pow(2, n-(i+1), bitp)
        xmm += pow(2, n-(i+1), bitm)
if bitx != 1:
    for i in range(n):
        if X[i] == '1':
            xm = (xmm - pow(2,n-i-1)) % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = (xmp + pow(2,n-i-1))%bitp
            l.append(str(1+ans[xm]))

else:
    for i in range(n):
        if X[i] == '1':
            l.append(str(0))
        else:
            xm = (xmp + pow(2,n-i-1))%bitp
            l.append(str(1+ans[xm]))

print('\n'.join(l))

Submission status: Runtime Error

Solution code:
import copy

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

plus = bin(int(X, 2)).count('1') + 1
minus = bin(int(X, 2)).count('1') - 1

init_n = [0] * N
init_X = [0] * N
for i in range(N):
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    first = plus
  else:
    X_list[i] = '0'
    first = minus
  X_str = ''.join(X_list)
  init_n[i] = int(X_str, 2)
  init_X[i] = init_n[i] % first

for i in range(N):
  
  fn = 0
  n = init_n[i]
  if n != 0:
    n = init_X[i]
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Submission status: Runtime Error

Solution code:
import copy

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

plus = bin(int(X, 2)).count('1') + 1
minus = bin(int(X, 2)).count('1') - 1

init_n = [0] * N
init_X = [0] * N
for i in range(N):
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    first = plus
  else:
    X_list[i] = '0'
    first = minus
  X_str = ''.join(X_list)
  init_n[i] = int(X_str, 2)
  init_X[i] = init_n[i] % first

for i in range(N):
  
  fn = 0
  if init_n[i] != 0:
    n = init_X[i]
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
def calc(n,count):
    if n==0:
        return count
    popcount=bin(n).count("1")
    next_n=n%popcount
    #print(next_n)
    if next_n==0:
        return count+1
    else:
        return calc(next_n, count+1)

popcount=X.count("1")
plus=0
minus=0
for i in range(N):
    x=X[i]
    if x=="1":
        plus+=pow(2,N-i-1,popcount+1)
        minus+=pow(2,N-i-1,popcount-1)
        plus%=(popcount+1)
        minus%=(popcount-1)

for i in range(N):
    x=X[i]
    if x=="1":
        ans=minus-pow(2,N-i-1,popcount-1)
        ans%=(popcount-1)
        print(calc(ans,1))

    else:
        ans=plus+pow(2,N-i-1,popcount+1)
        ans%=(popcount+1)
        print(calc(ans,1))

Submission status: Runtime Error

Solution code:
n = int(input())
x = int(input(),2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+1)
for i in range(1,bitx+1):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = x % bitp
xmm = x % bitm
if bitx != 1:
    for i in range(n):
        if x>>(n-i-1)&1:
            xm = (xmm - pow(2,n-i-1)) % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = (xmp + pow(2,n-i-1))%bitp
            l.append(str(1+ans[xm]))

else:
    for i in range(n):
        if x>>(n-i-1)&1:
            l.append(str(0))
        else:
            xm = (xmp + pow(2,n-i-1))%bitp
            l.append(str(1+ans[xm]))

print('\n'.join(l))

Submission status: Runtime Error

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


def main():
    N = readint()
    X = readstr()
    s = sum(tuple(map(int, X)))
    m1 = int(X, 2) % (s + 1)
    m2 = int(X, 2) % (s - 1)
    for i in range(N):
        l = ['0'] * N
        l[i] = '1'
        ans = 1
        if X[i] == '0':
            x = (m1 + 2 ** (N - i - 1) % (s + 1)) % (s + 1)
        else:
            x = (m2 - 2 ** (N - i - 1) % (s - 1)) % (s - 1)
        d = sum(tuple(map(int, bin(x)[2:])))
        while x:
            x %= d
            d = sum(tuple(map(int, bin(x)[2:])))
            ans += 1
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
s=input()
p=0
c=0
for i in range(n):
    if s[i]=='1':
        p+=2**(n-i-1)
        c+=1


e=p%(c+1)
f=p%(c-1)
for i in range(n):
    z=c
    b=e
    a=f
    if s[i]=='0':
        b+=2**(n-i-1)
        z+=1
        b%=z
    else:
        a-=2**(n-i-1)
        z-=1
        a%=z
        
    l=1
        
    if z==c-1:
        while a>0 and z>0:
            if a%z>0:
                a%=z
                z=bin(a).count('1')
                l+=1
            else:
                break
    else:
        while b>0 and z>0:
            if b%z>0:
                b%=z
                z=bin(b).count('1')
                l+=1
            else:
                break
            
    print(l)

Submission status: Runtime Error

Solution code:
n = int(input())
s=input()
p=0
c=0
for i in range(n):
    if s[i]=='1':
        p+=2**(n-i-1)
        c+=1

if c>1:
    e=p%(c+1)
    f=p%(c-1)
for i in range(n):
    z=c
    b=e
    a=f
    if s[i]=='0':
        b+=2**(n-i-1)
        z+=1
        b%=z
    else:
        a-=2**(n-i-1)
        z-=1
        a%=z
        
    l=1
        
    if z==c-1:
        while a>0 and z>0:
            if a%z>0:
                a%=z
                z=bin(a).count('1')
                l+=1
            else:
                break
    else:
        while b>0 and z>0:
            if b%z>0:
                b%=z
                z=bin(b).count('1')
                l+=1
            else:
                break
            
    print(l)

Submission status: Runtime Error

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

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

for i in range(N):
  
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
  else:
    X_list[i] = '0'
  
  X_str = ''.join(X_list)
  n = int(X_str, 2)
  fn = 0
  while n != 0:
    n = n % popcount(n)
    fn += 1
  
  print(fn)

Submission status: Runtime Error

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for i in range(N):
    if(one_r_count != 0):
        one_mod = (one_mod * 2) + int(sX[i]) % one_r_count
    zero_mod = (zero_mod * 2 ) + int(sX[i]) % zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if(one_r_count != '0'):
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if(sX[i-1] == '1'):
        if(one_r_count != 0):
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
x = int(input(),2)
bitx = bin(x).count('1')

ans = [0]*(bitx+1)
for i in range(1,bitx+1):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
if bitx != 1:
    for i in range(n):
        y = x^(1<<(n-i-1))
        if y>>(n-i-1)&1:
            l.append(str(1+ans[y % bitx+1]))
        else:
            l.append(str(1+ans[y % bitx-1]))
else:
    for i in range(n):
        y = x^(1<<(n-i-1))
        if y>>(n-i-1)&1:
            l.append(str(1+ans[y % bitx+1]))
        else:
            l.append(str(0))
    #print(1+ans[t])
print('\n'.join(l))

Submission status: Runtime Error

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for i in range(N):
    if(one_r_count != '0'):
        one_mod = (one_mod * 2) + int(sX[i]) % one_r_count
    zero_mod = (zero_mod * 2 ) + int(sX[i]) % zero_r_count

Submission status: Runtime Error

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for i in range(N):
    if(one_r_count != '0'):
        one_mod = (one_mod << 1) + int(sX[i]) % one_r_count
    zero_mod = (zero_mod << 1) + int(sX[i]) % zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if(one_r_count != '0'):
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if(sX[i-1] == '1'):
        if(one_r_count != 0):
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

for i in range(1,N+1):
    # 上からi桁目
    Xi = X ^ (1 << (N - i))
    cnt = 0
    n = Xi
    while True:
        cnt += 1
        r = n % bin(n).count("1")
        if r == 0:
            break
        n = r
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
import math
from functools import reduce

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


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

for i in range(1,N+1):
    # 上からi桁目
    Xi = X ^ (1 << (N - i))
    cnt = 0
    n = Xi
    while True:
        cnt += 1
        r = n % bin(n).count("1")
        if r == 0:
            break
        n = r
    print(cnt)

Submission status: Runtime Error

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for i in range(N):
    if(one_r_count != '0'):
        one_mod = (one_mod << 1) + int(sX[i]) % one_r_count
    zero_mod = (zero_mod << 1) + int(sX[i]) % zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1

for i in range(1,N+1):
    if(sX[i-1] == '1'):
        if(one_r_count != 0):
            Xi_n = one_mod - pow(2,N-i)
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + pow(2,N-i)
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Runtime Error

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

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for i in range(N):
    if(one_r_count != '0'):
        one_mod = (one_mod << 1) + int(sX[i]) % one_r_count
    zero_mod = (zero_mod << 1) + int(sX[i]) % zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,22000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1

for i in range(1,N+1):
    if(sX[i-1] == '1'):
        if(one_r_count != 0):
            Xi_n = one_mod - pow(2,N-i)
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + pow(2,N-i)
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

Submission status: Runtime Error

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


def read():
    N = int(input().strip())
    X = input().strip()
    return N, X


def bitdiv(N:int, X:str, d:int):
    q = 0
    for i in range(N):
        q <<= 1
        q |= int(X[i])
        p, q = divmod(q, d)
    return q


def solve(N, X):
    BP = [0 for i in range(N)]
    BM = [0 for i in range(N)]

    c = X.count("1")
    

    # 2^k mod (c+1) を高速に求める
    qp = bitdiv(N, X, c+1)
    BP[N-1] = 1 % (c+1)
    for i in range(N-2, -1, -1):
        BP[i] = (BP[i+1] * 2) % (c+1)
    
    # 2^k mod (c-1) を高速に求める
    qm = bitdiv(N, X, c-1)
    if c > 1:
        BM[N-1] = 1 % (c-1)
        for i in range(N-2, -1, -1):
            BM[i] = (BM[i+1] * 2) % (c-1)

    for i in range(N):
        q = 0
        ans = 0
        if X[i] == "0":
            # X_i \equiv (X + 2^i)
            q = (qp + BP[i]) % (c+1)
            ans += 1
        elif X[i] == "1" and c > 1:
            # X_i \equiv (X - 2^i)
            q = (qm - BM[i]) % (c-1)
            ans += 1
        else:
            q = 0
            ans = 0
        while q > 0:
            q %= (bin(q).count("1"))
            ans += 1
        print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
max_n = int(("1" * N), 2)
dp = [0] * (max_n + 1)
print(1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
 
def popcount(n):
  return bin(n).count("1")
 
max_n = int(("1" * N), 2)
dp = [0] * (max_n + 1)
 
def re(n):
  if n == 0:
    return 0
  elif dp[n] > 0:
    return dp[n]
  else:
    a = re(n % popcount(n)) + 1
    dp[n] = a
    return a

for i in range(1, N+1):
  print(re(X ^ 2**(N-i)))

Submission status: Runtime Error

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

init_pop_cnt = x.count('1')
init_pop_cnt_less = init_pop_cnt - 1
init_pop_cnt_more = init_pop_cnt + 1

# x's state after f
init_res_less = 0
init_res_more = 0
seed_more = 1
seed_less = 1
for i in range(1, n+1):
  xp = x[-1 * i]
  if xp == '1':
    init_res_less += seed_less % init_pop_cnt_less
    init_res_more += seed_more % init_pop_cnt_more
  seed_less = (seed_less * 2) % init_pop_cnt_less
  seed_more = (seed_more * 2) % init_pop_cnt_more


dif_less = [0] * (2 * 10**5 + 100)
dif_more = [0] * (2 * 10**5 + 100)
dif_less[0] = 1 % init_pop_cnt_less
dif_more[0] = 1 % init_pop_cnt_more
for i in range(1, n+1):
  dif_less[i] = (dif_less[i-1] * 2) % init_pop_cnt_less
  dif_more[i] = (dif_more[i-1] * 2) % init_pop_cnt_more


def get_pc(dec):
  out = 0
  while dec > 0:
    if dec % 2 == 1:
      out+=1
    dec = dec // 2
  return out

def f(dec):
  pc = get_pc(dec)
  return dec % pc

cnt = [0] * (2 * 10**5 + 200)

for i in range(1, 2 * 10**5 + 100):
  c = 0
  cur = i
  while cur > 0:
    c += 1
    cur = f(cur)
  cnt[i] = c


for i in range(n):
  xi = x[i]

  if xi == '1':
    lx = init_res_less
    lx -= dif_less[n-i-1]
    lx %= init_pop_cnt_less
    print((cnt[lx] % init_pop_cnt_less) + 1)
  else:
    lx = init_res_more
    lx += dif_more[n-i-1]
    lx %= init_pop_cnt_more
    print((cnt[lx] % init_pop_cnt_more) + 1)

Submission status: Runtime Error

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

n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

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

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

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

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

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%popcount(xi)
            print(icnt)

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
 
def popcount(n):
  return bin(n).count("1")
 
max_n = int(("1" * N), 2)
dp = [0] * (max_n + 1)
 
def re(n):
  if n == 0:
    return 0
  elif dp[n] > 0:
    return dp[n]
  else:
    a = re(n % popcount(n)) + 1
    dp[n] = a
  return a
 
for i in range(1, N+1):
  print(re(X ^ 2**(N-i)))

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
 
def popcount(n):
  return bin(n).count("1")
 
max_n = int(("1" * N), 2)
dp = [0] * (max_n + 1)
 
def re(n):
  if n == 0:
    return 0
  elif dp[n] != 0:
    return dp[n]
  else:
    a = re(n % popcount(n)) + 1
    dp[n] = a
  return a
 
for i in range(1, N+1):
  print(re(X ^ 2**(N-i)))

Submission status: Runtime Error

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

#N = 23
#X = '00110111001011011001110'

mem_func = [-1 for i in range(2**N)]

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

def func(n, l):
    # mem_func定義済み
    if mem_func[n] != -1: return mem_func[n] + l
    # mem_func未定義
    if n == 0: return l
    n = n % popcount(n)
    return func(n, l+1)

list_X = list(X)
standard = popcount(int(X, 2))

for i in range(N):
    x = copy.copy(list_X)
    if x[i] == '0':
        x[i] = '1'
        z = int(''.join(x), 2)
        mem_func[z] = func(z%(standard+1), 1)
        print(mem_func[z])
    else:
        x[i] = '0'
        z = int(''.join(x), 2)
        mem_func[z] = func(z%(standard-1), 1)
        print(mem_func[z])

Submission status: Runtime Error

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

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

max_n = int(("1" * N), 2)
dp = [0] * (max_n + 1)

def re(n):
  if n == 0:
    return 0
  elif dp[n] != 0:
    return dp[n]
  else:
    a = re(n % popcount(n)) + 1
    dp[n] = a
  return a

for i in range(1, N+1):
  print(re(X ^ 2**(N-i)))

Submission status: Runtime Error

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

dp=[-1]*(200001)

dp[0]=0
dp[1]=1

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

for i in range(2,200001):
    fun(i,1)

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input(), 2)
def popcount(n):
  return bin(n).count("1")
max_n = int(("1" * N), 2)
dp = [0] * (max_n + 1)

def re(n):
  if n==0:
    return 0
  elif dp[n] != 0:
    return dp[n]
  else:
    a = re(n % popcount(n)) + 1
    dp[n] = a
  return a

for i in range(1, N+1):
  print(re(X ^ 2**(N-i)))

Submission status: Runtime Error

Solution code:
input = raw_input

def popcount(n):
    ret = bin(n)[2:].count("1")
    return ret

def ff(n):
    d = popcount(n)
    q = n % d
    return q

def f(n):
    count = 0
    while True:
        if n == 0:
            return count
        count += 1
        n = ff(n)

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

xpop = x_str.count("1")
xpop_p1 = xpop + 1
x1_p1 = x % xpop_p1

if xpop >= 1:
    xpop_m1 = xpop - 1
    x1_m1 = x % xpop_m1
else:
    x1_m1 = None

#print("x", x)
#print("xpop", xpop)
#print(x1_p1, x1_m1)
#print(xpop_p1, xpop_m1)

for i, c in enumerate(x_str):
    shisuu = n - i -1

    atai = 2 ** shisuu
    if c == "1":
        atai = atai % xpop_m1
        xx = x1_m1
        xx = (x1_m1 - atai) % xpop_m1
    else:
        atai = atai % xpop_p1
        #print("atai", atai)
        xx = (x1_p1 + atai) % xpop_p1
    #print("xx", xx)
    count = f(xx)
    out = 1 + count
    print(out)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    x = input().strip()

    _x = list(x)
    pre_count = [1, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 4]
    count_1 = x.count("1")

    pre_mod0 = int(x, 2) % (count_1 + 1)
    if not count_1 - 1 == 0:
        pre_mod1 = int(x, 2) % (count_1 - 1)

    for i in range(n):
        _count_1 = count_1 - 1 if _x[i] == "1" else count_1 + 1
        if _count_1 == 0:
            print(0)
        else:
            pre_mod = pre_mod1 if _x[i] == "1" else pre_mod0
            mod = (2 ** (n - i - 1))
            mod %= _count_1
            if _x[i] == "0":
                mod += pre_mod
            else:
                mod = mod - pre_mod + _count_1
            print(pre_count[int((mod) % _count_1)])

Submission status: Runtime Error

Solution code:
N=int(input())
X=input()
Xnum=int(X,2)
popcount=X.count('1')
if popcount != 1:
    Xnum1=Xnum%(popcount-1)
Xnum0=Xnum%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
    if X[i]=='1':
        Xi = (Xnum1 - (2**(N-i-1)%(popcount-1)))%(popcount-1)
    else:
        Xi = (Xnum0 + (2**(N-i-1)%(popcount+1)))%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    x = input().strip()

    _x = list(x)
    pre_count = [1, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 4]
    count_1 = x.count("1")

    pre_mod0 = int(x, 2) % (count_1 + 1)
    pre_mod1 = int(x, 2) % (count_1 - 1)

    for i in range(n):
        _count_1 = count_1 - 1 if _x[i] == "1" else count_1 + 1
        if _count_1 == 0:
            print(0)
        else:
            pre_mod = pre_mod1 if _x[i] == "1" else pre_mod0
            mod = (2 ** (n - i - 1))
            mod %= _count_1
            if _x[i] == "0":
                mod += pre_mod
            else:
                mod = mod - pre_mod + _count_1
            print(pre_count[int((mod) % _count_1)])

Submission status: Runtime Error

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

dp=[-1]*(200001)

dp[0]=0
dp[1]=1

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

for i in range(2,200001):
    fun(i,1)

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

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