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: Accepted

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

n = int(input())
x = input()
one = x.count('1')
num = int(x, 2)

up = num%(one+1)
if one == 1:down = 0
else:down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = (down - pow(2, n-i-1, one-1))%(one-1)
    else:
        s = (up + pow(2, n-i-1, one+1))%(one+1)
    print(solve(s))

Submission status: Accepted

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

n = int(input())
x = input()
one = sum(map(int, list(x)))
num = int(x, 2)

up = num%(one+1)
if one == 1:
    down = 0
else:
    down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = (down - pow(2, n-i-1, one-1))%(one-1)
    else:
        s = (up + pow(2, n-i-1, one+1))%(one+1)
    print(solve(s))

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

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

def Main():
    n = read_int()
    x = read_str()
    x_int = int(x, 2)

    cnt = x.count('1')
    minus_cnt = cnt - 1
    plus_cnt = cnt + 1
    
    minus_mod = x_int % minus_cnt if minus_cnt != 0 else 0
    plus_mod = x_int % plus_cnt

    for i in range(n):
        if x[i] == '0':
            print(popcount((plus_mod + pow(2, n - 1 - i, plus_cnt)) % plus_cnt) + 1)
        elif minus_cnt != 0:
            print(popcount((minus_mod - pow(2, n - 1 - i, minus_cnt)) % minus_cnt) + 1)
        else:
            print(0)

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
if pop_x <= 1:
    mod0 = pop_x + 1
    res0 = num_X % mod0
else:
    mod1 = pop_x - 1
    mod0 = pop_x + 1
    res1 = num_X % (mod1)
    res0 = num_X % (mod0)

# pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        if pop_x == 1:
            print(0)
            continue
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        pop = bin(tmp).count("1")
        tmp %= pop
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし


N = I()
X = LI2()
X.reverse()

if N == 1 and len(X) == 1 and X[0] == 0:
    print(1)
    exit()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res


# 1回の操作で 2*10**5 未満になることに注意

F = [0]*(2*10**5)  # F[i] = f(i)
for i in range(1,2*10**5):
    F[i] = 1 + F[i % popcount(i)]

a = sum(X)
b = a-1
c = a+1
if a == 1:
    C = [1]  # 2冪をcで割った余り
    xc = 0  # Xをcで割った余り
    for i in range(N):
        if X[i] == 1:
            xc += C[-1]
            xc %= c
        C.append((2 * C[-1]) % c)

    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])

    ANS.reverse()
    print(*ANS, sep='\n')
    exit()

B,C = [1],[1]  # 2冪をb,cで割った余り
xb,xc = 0,0  # Xをb,cで割った余り
for i in range(N):
    if X[i] == 1:
        xb += B[-1]
        xc += C[-1]
        xb %= b
        xc %= c
    B.append((2*B[-1])%b)
    C.append((2*C[-1])%c)

ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb-B[i]) % b])
    else:
        ANS.append(1 + F[(xc+C[i]) % c])

ANS.reverse()
print(*ANS,sep='\n')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
X=list(input())

ones=X.count("1")
high=ones+1
low=ones-1

mod_h=[1]
mod_l=[1]
for i in range(N-1):
    mod_h.append((mod_h[-1]*2)%high)
    mod_l.append((mod_l[-1]*2)%low if low!=0 else 0) 

mod_h=mod_h[::-1]
mod_l=mod_l[::-1]

ans_high=0
for i in range(N):
    if X[i] == "1":
        ans_high+=mod_h[i]
ans_high%=high

ans_low=0
for i in range(N):
    if X[i] == "1":
        ans_low+=mod_l[i]
ans_low%=low if low!=0 else 1
        
for i in range(N):
    if X[i]=="0":
        ans=ans_high
        ans+=mod_h[i]
        ans%=high
    else:
        if low==0:
            print(0)
            continue
        ans=ans_low
        ans-=mod_l[i]
        ans%=low
    
    count=1
    while ans!=0:
        ans=ans%(bin(ans).count("1"))
        count+=1
    
    print(count)

Submission status: Accepted

Solution code:
N = int(input())
X = list(input())
X = [int(x) for x in X]
popcnt = 0
for i in range(N):
    if X[i]:
        popcnt += 1

Ys = [0,0]
for i in range(N):
    if X[i]:
        Ys[0] += pow(2,N-1-i,popcnt+1)
        Ys[0] %= popcnt+1

if popcnt > 1:
    for i in range(N):
        if X[i]:
            Ys[1] += pow(2,N-1-i,popcnt-1)
            Ys[1] %= popcnt-1


for i in range(N):
    if X[i]:#1->0
        mod = popcnt-1
        if mod == 0:
            print(0)
            continue
        Y = Ys[1] - pow(2,N-1-i,mod)
    else:#0->1
        mod = popcnt+1
        Y = Ys[0] + pow(2,N-1-i,mod)
	
    Y %= mod
    ans = 1

    if Y == 0:
        print(ans)
        continue
        
    while Y > 0:
        L = Y.bit_length()
        mod = 0
        for j in range(L):
            if Y>>j&1:
                mod += 1
        Y %= mod
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = str(input())
X = [];Bit = 0;Num = 0
for i in range(N):
  if S[i] == "1":
    Bit += 1
    Num += pow(2,N-1-i)
  X.append(int(S[i]))
#print(X)
#print(Num)
MAX = 2*pow(10,5)+10
small = [-1 for _ in range(MAX)]
small[0] = 0; small[1] = 1; small[2] = 1; small[3] = 2
for i in range(4,MAX):
  ret = 0; target = i*1
  while i > 0:
    cnt = 0
    for j in range(i.bit_length()):
      if (i>>j)&1 == 1:
        cnt += 1
    i = i%cnt
    #print(i,target,cnt)
    ret += 1
    if small[i] != -1:
      ret += small[i]
      break

  small[target] = ret
#print(small)
if Bit -1 != 0:
  Numm = Num%(Bit-1)
Nump = Num%(Bit+1)
#print(Num)
ans = []
for i in range(N):
  keta = N-1-i
  if X[i] == 1:
    btemp = Bit -1
    if btemp == 0:
      ans.append(0)
      continue
    temp = (Numm - pow(2,keta,btemp))%btemp
  else:
    btemp = Bit +1
    temp = (Nump + pow(2,keta,btemp))%btemp
  ret = small[temp] + 1 #最初の一回
  ans.append(ret)
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
X = LI2()
X.reverse()

if N == 1 and len(X) == 1 and X[0] == 0:
    print(1)
    exit()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res


F = [0]*(2*10**5)
for i in range(1,2*10**5):
    F[i] = 1 + F[i % popcount(i)]

a = sum(X)
b = a-1
c = a+1
if a == 1:
    A, C = [1], [1]  # 2冪をa,b,cで割った余り
    xa, xc = 0, 0  # Xをa,b,cで割った余り
    for i in range(N):
        if X[i] == 1:
            xa += A[-1]
            xc += C[-1]
            xa %= a
            xc %= c
        A.append((2 * A[-1]) % a)
        C.append((2 * C[-1]) % c)

    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])

    ANS.reverse()
    print(*ANS, sep='\n')
    exit()

A,B,C = [1],[1],[1]  # 2冪をa,b,cで割った余り
xa,xb,xc = 0,0,0  # Xをa,b,cで割った余り
for i in range(N):
    if X[i] == 1:
        xa += A[-1]
        xb += B[-1]
        xc += C[-1]
        xa %= a
        xb %= b
        xc %= c
    A.append((2*A[-1])%a)
    B.append((2*B[-1])%b)
    C.append((2*C[-1])%c)

ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb-B[i]) % b])
    else:
        ANS.append(1 + F[(xc+C[i]) % c])

ANS.reverse()
print(*ANS,sep='\n')

Submission status: Accepted

Solution code:
n=int(input())
x=input()
pc=[0]
m=2*10**5
for i in range(1,m+2):
  cnt=0
  j=i
  while i:
    cnt+=i%2
    i//=2
  pc+=[j%cnt]
f=[0]*(m+2)
for i in range(1,m+2):
  if pc[i]==0:f[i]=1
  else:f[i]=f[pc[i]]+1
cnt=x.count('1')
ix=int(x,2)
ixp=ix%(cnt+1)
ixm=ix%(cnt-1) if cnt-1 else 0
d=1<<(n-1)
for i in range(n):
  dp=pow(2,n-i-1,cnt+1)
  if cnt-1:dm=pow(2,n-i-1,cnt-1)
  if x[i]=='0':print(f[(ixp+dp)%(cnt+1)]+1)
  else:
    if cnt-1:print(f[(ixm-dm)%(cnt-1)]+1)
    else:print(0)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def popcount(N):
    if N == 0:
        return 0
    one_count = 0
    temp = N
    while temp > 0:
        one_count += temp%2
        temp //= 2
    return 1+popcount(N%one_count)


def solve():
    N = read_int()
    X = input()
    one_count = X.count('1')
    if one_count == 0:
        for _ in range(N):
            print(1)
        return

    new_X = [0]*N
    steps = [0]*N

    base_up = 1
    up_under_modulo = 0

    for i in range(N-1, -1, -1):
        if X[i] == '1':
            up_under_modulo = (up_under_modulo+base_up)%(one_count+1)
        if X[i] == '0':
            new_X[i] += base_up
            steps[i] = 1
        base_up = (base_up*2)%(one_count+1)

    base_down = 1
    down_under_modulo = 0

    if one_count > 1:
        for i in range(N-1, -1, -1):
            if X[i] == '1':
                down_under_modulo = (down_under_modulo+base_down)%(one_count-1)
            if X[i] == '1':
                new_X[i] -= base_down
                steps[i] = 1
            base_down = (base_down*2)%(one_count-1)

    for i in range(N):
        if X[i] == '1':
            if one_count > 1:
                new_X[i] = (new_X[i]+down_under_modulo)%(one_count-1)
        else:
            new_X[i] = (new_X[i]+up_under_modulo)%(one_count+1)

    for i in range(N):
        print(steps[i]+popcount(new_X[i]))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

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

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b - pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
X = input()
x = X[::-1]
one = X.count('1')
up = 0
down = 0
for i in range(N):
    up += (int(x[i]) * pow(2,i,one+1) % (one+1))
    up %= one+1
    if one > 1:
        down += (int(x[i]) * pow(2,i,one-1) % (one-1))
        down %= one-1
# print(up,down)
def f(ud,one):
    cnt = 1
    while ud != 0:
        one = format(ud,'b').count('1')
        ud = ud % one
        cnt += 1
    return cnt



for i in range(len(X)):
    if X[i] == '1':
        if one > 1:
            print(f((down - pow(2,(len(X)-1) - i, one-1)) % (one-1),one-1))
        #print(down - pow(2,(len(X)-1) - i, one-1) % (one-1))
        else:
            print(0)

    else:
        print(f((up + pow(2,(len(X)-1) - i, one+1)) % (one+1),one+1))
        #print(up + pow(2,(len(X)-1) - i, one+1) % (one+1))

Submission status: Accepted

Solution code:
N = int(input())
X = input()
x = X[::-1]
one = X.count('1')
up = 0
down = 0
for i in range(N):
    up += (int(x[i]) * pow(2,i,one+1) % (one+1))
    up %= one+1
    if one > 1:
        down += (int(x[i]) * pow(2,i,one-1) % (one-1))
        down %= one-1
# print(up,down)
def f(ud,one):
    if ud == 0:
        return 1

    cnt = 0
    while ud != 0:
        ud = ud % one
        one = format(ud,'b').count('1')
        cnt += 1
    return cnt



for i in range(len(X)):
    if X[i] == '1':
        if one > 1:
            print(f((down - pow(2,(len(X)-1) - i, one-1)) % (one-1),one-1))
        #print(down - pow(2,(len(X)-1) - i, one-1) % (one-1))
        else:
            print(0)

    else:
        print(f((up + pow(2,(len(X)-1) - i, one+1)) % (one+1),one+1))
        #print(up + pow(2,(len(X)-1) - i, one+1) % (one+1))

Submission status: Accepted

Solution code:
N = int(input())
X = input()
x = X[::-1]
one = X.count('1')
up = 0
down = 0
for i in range(N):
    up += (int(x[i]) * pow(2,i,one+1) % (one+1))
    up %= one+1
    if one > 1:
        down += (int(x[i]) * pow(2,i,one-1) % (one-1))
        down %= one-1
# print(up,down)
def f(ud,one):
    if one <= 0:
        return 0
    else:
        if ud == 0:
            return 1

        cnt = 0
        while ud != 0:
            ud = ud % one
            one = format(ud,'b').count('1')
            cnt += 1
        return cnt



for i in range(len(X)):
    if X[i] == '1':
        if one > 1:
            print(f((down - pow(2,(len(X)-1) - i, one-1)) % (one-1),one-1))
        #print(down - pow(2,(len(X)-1) - i, one-1) % (one-1))
        else:
            print(0)

    else:
        print(f((up + pow(2,(len(X)-1) - i, one+1)) % (one+1),one+1))
        #print(up + pow(2,(len(X)-1) - i, one+1) % (one+1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':
#    n = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
    n = (f_plus + pow(2, j, popcount_X_plus)) % popcount_X_plus
  else:
    if popcount_X_minus == 0:
      print(0)
      continue
    else:
#      n = (f_minus - (2**j % popcount_X_minus) + popcount_X_minus) % popcount_X_minus
      n = (f_minus - pow(2, j, popcount_X_minus) + popcount_X_minus) % popcount_X_minus
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)

Submission status: Accepted

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


def f(n):
    if n == 0:
        return 0
    return f(n % pop_count(n)) + 1


N = int(input())
X = list(map(int, input()))
X_m = 0
X_p = 0
pop_X = X.count(1)
for i in range(N):
    if X[i] == 0:
        continue
    X_p += pow(2, N - i - 1, pop_X + 1)
    X_p %= pop_X + 1
    if pop_X > 1:
        X_m += pow(2, N - i - 1, pop_X - 1)
        X_m %= pop_X - 1

for i in range(N):
    ans = 1
    if X[i] == 0:
        ans += f((X_p + pow(2, N - i - 1, pop_X + 1)) % (pop_X + 1))
    elif pop_X > 1:
        ans += f((X_m - pow(2, N - i - 1, pop_X - 1)) % (pop_X - 1))
    else:
        ans = 0
    print(ans)

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i,bl+1)
    bitp %= bl+1
  bitm = 0
  if bl>1:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i,bl-1)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
      bit1 = bitm - pow(2,N-1-i,bl1)
    else:
      bl1 = bl+1
      bit1 = bitp + pow(2,N-1-i,bl1)
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
n = int(input())
xs = input()
x = int(xs, 2)

ansl = [0]*n
for i in range(1,n):
    ans = 0
    num = i
    while True:
        pc = bin(num).count("1")
        num %= pc
        ans += 1
        if num == 0: break
    ansl[i] = ans

pc = bin(x).count("1")
if pc == 0:
    for i in range(n):
        print(1)
        exit()


next_num = x%pc
next_num_p1 = x%(pc+1)
if pc != 1:
    next_num_m1 = x%(pc-1)
else:
    next_num_m1 = None

for i in range(n):
    bit = (1<<(n-1-i))
    if xs[i] == '0':
        num = (next_num_p1 + pow(2,n-1-i,pc+1)) % (pc+1)
        ans = ansl[num] + 1
    else:
        if pc != 1:
            num = (next_num_m1 - pow(2,n-1-i,pc-1)) % (pc-1)
            ans = ansl[num] + 1
        else:
            ans = 0
    print(ans)

Submission status: Accepted

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


def power(a, n, mod):
    bi=str(format(n,"b")) #2進数
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

p = x.count('1')

if p == 0:
    ans = [1]*n
    for i in range(n):
        print(ans[i])
    exit()

if p == 1:
    if x[-1] != '1':
        ans = [1]*n
        for i in range(n):
            if x[i] == '1':
                ans[i] = 0
        ans[-1] = 2
    else:
        ans = [2]*n
        ans[-1] = 0
    for i in range(n):
        print(ans[i])
    exit()

x = list(x)
x.reverse()
temp1 = 0
for i in range(len(x)):
    temp1 += int(x[i])*power(2, i, p+1)
temp1 %= (p+1)

temp2 = 0
for i in range(len(x)):
    temp2 += int(x[i])*power(2, i, p-1)
temp2 %= (p-1)

ans = [0]*n

for i in range(n):
    if x[n-1-i] == '1':
        temp = temp2-power(2, n-1-i, p-1)
        c = p-1
    else:
        temp = temp1+power(2, n-1-i, p+1)
        c = p+1
    temp %= c
    #print(i, temp, c)
    cnt = 1
    while temp != 0:
        x_ = format(temp, 'b')
        c = x_.count('1')
        x_ = list(x_)
        x_.reverse()
        temp = 0
        for j in range(len(x_)):
            temp += int(x_[j])*power(2, j, c)
        temp %= c
        cnt += 1
    #print(i, cnt)
    ans[i] = cnt

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

Submission status: Accepted

Solution code:

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

mod0 = X.count("1") + 1
mod1 = X.count("1") - 1

full0 = 0
full1 = 0
for i in range(N):
    if X[i] == "1":
        full0 = (full0 + pow(2, N - i - 1, mod0)) % mod0
        if mod1 > 0:
            full1 = (full1 + pow(2, N - i - 1, mod1)) % mod1

ans = [0] * N
for i in range(N):
    if X[i] == "0":
        cur = (full0 + pow(2, N - i - 1, mod0)) % mod0
        res = 1
    else:
        if mod1 > 0:
            cur = (full1 - pow(2, N - i - 1, mod1)) % mod1
            res = 1
        else:
            cur = 0
            res = 0

    while cur > 0:
        cur %= bin(cur).count("1")
        res += 1
    ans[i] = res

print(*ans, sep="\n")

Submission status: Accepted

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

cnt1 = X.count("1")
p_cnt = cnt1+1
m_cnt = cnt1-1
p_amari = val%(cnt1+1)
if cnt1-1 != 0:
  m_amari = val%(cnt1-1)
else:
  m_amari = 0

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

for i in range(N):
  ans = 0
  if X[i] == "0":
    amari = p_amari + pow(2,N-i-1,p_cnt)
    amari %= p_cnt
    ans += 1
  else:
    if cnt1-1==0:
      print(0)
      continue
    amari = m_amari - pow(2,N-i-1,m_cnt)
    amari %= m_cnt
    ans += 1

  ans += f(amari)
  print(ans)

Submission status: Accepted

Solution code:
def solve(n,m):
  if not n:return 1
  n%=m
  return-~solve(n,bin(n).count('1'))
n=int(input())
s=input()
a=int(s,2)
*x,=map(int,s)
h=sum(x)
try:a,b=a%(h-1),a%(h+1)
except:b=a%(h+1)
for i in range(n):
  if x[i]:
    if not h-1:
      print(0)
      continue
    x[i]=0
    t=(a-pow(2,~i+n,h-1))%(h-1)
  else:
    x[i]=1
    t=(b+pow(2,~i+n,h+1))%(h+1)
  r=solve(t,bin(t).count('1'))
  x[i]^=1
  print(r)

Submission status: Accepted

Solution code:
from functools import*
@lru_cache(None)
def solve(n,m):
  if not n:return 1
  n%=m
  return-~solve(n,bin(n).count('1'))
n=int(input())
s=input()
a=int(s,2)
*x,=map(int,s)
h=sum(x)
try:a,b=a%(h-1),a%(h+1)
except:b=a%(h+1)
for i in range(n):
  if x[i]:
    if not h-1:
      print(0)
      continue
    x[i]=0
    t=(a-pow(2,~i+n,h-1))%(h-1)
  else:
    x[i]=1
    t=(b+pow(2,~i+n,h+1))%(h+1)
  r=solve(t,bin(t).count('1'))
  x[i]^=1
  print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = list(map(int, list(x)))
x = int(x, 2)

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

mmod = cnt - 1
pmod = cnt + 1

if mmod:
    mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

ans = []
while digits:
    digit = digits.pop()
    
    if digit and not mmod:
        ans.append(0)
    else:
        if digit:
            nx = (mx - mbase)%mmod
        else:
            nx = (px + pbase)%pmod
        ans.append(calc(nx) + 1)

    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())

Submission status: Accepted

Solution code:
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = list(map(int, list(x)))
x = int(x, 2)

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

mmod = cnt - 1
pmod = cnt + 1

if mmod > 0:
    mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

ans = []
while digits:
    digit = digits.pop()
    
    if digit and mmod <= 0:
        ans.append(0)
    else:
        if digit:
            nx = (mx - mbase)%mmod
        else:
            nx = (px + pbase)%pmod
        ans.append(calc(nx) + 1)

    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())

Submission status: Accepted

Solution code:
from sys import exit
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = list(map(int, list(x)))
x = int(x, 2)

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

if n == 1:
    print(calc(x^1))
    exit()

mmod = cnt - 1
pmod = cnt + 1

if mmod > 0:
    mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

ans = []
while digits:
    digit = digits.pop()
    
    if digit and mmod <= 0:
        ans.append(0)
    else:
        if digit:
            nx = (mx - mbase)%mmod
        else:
            nx = (px + pbase)%pmod
        ans.append(calc(nx) + 1)

    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())

Submission status: Accepted

Solution code:
def count1(c):
  cnt = 0
  while c != 0:
    if c % 2 == 1:
      cnt += 1
    c //= 2
  return cnt
n = int(input())
x = input()
y = int(x, 2)
z = list(x).count('1')
l = []
a = y % (z + 1)
if z > 1:
  l2 = []
  b = y % (z - 1)
for i in range(n):
  l.append(pow(2, n - i - 1, z + 1))
  if z > 1:
    l2.append(pow(2, n - i - 1, z - 1))
for i in range(n):
  if x[i] == '0':
    c = a + l[i]
    c %= z + 1
  elif z == 1 and x[i] == '1':
    print(0)
    continue
  else:
    c = b - l2[i]
    c %= z - 1
  cnt = 1
  while c != 0:
    d = count1(c)
    c %= d
    cnt += 1
  print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = input()
pc = X.count('1')


if pc == 0:
    print(*[1]*N, sep='\n')
    exit()
elif pc == 1:
    if int(X, 2) == 1:
        for i in range(N-1):
            print(2)
        print(0)
        exit()
    else:
        for i in range(N):
            if i == N-1:
                print(2)
            elif X[i] == '0':
                print(1)
            else:
                print(0)
        exit()

mod_plus_1, mod_minus_1 = 0, 0
for i in range(N):
    mod_plus_1 = (mod_plus_1*2+int(X[i])) % (pc+1)
    mod_minus_1 = (mod_minus_1*2+int(X[i])) % (pc-1)


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


mods_p1, mods_m1 = [1 % (pc+1)], [1 % (pc-1)]
for i in range(N-1):
    mods_p1.append(mods_p1[-1]*2 % (pc+1))
    mods_m1.append(mods_m1[-1]*2 % (pc-1))
mods_p1 = mods_p1[::-1]
mods_m1 = mods_m1[::-1]


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1 + mods_p1[i]
        x %= (pc+1)
    else:
        x = mod_minus_1 - mods_m1[i]
        x %= (pc-1)

    if x == 0:
        print(1)
    else:
        print(f(x)+1)

Submission status: Accepted

Solution code:
N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += pow(2, i, pc + 1)
        m01 %= pc + 1
        m10 += pow(2, i, pc - 1)
        m10 %= pc - 1


memo = [-1] * 200005


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


def F(n):
    if memo[n] != -1:
        return memo[n]
    if n == 0:
        return 0
    memo[n] = F(n % pop_count(n)) + 1
    return memo[n]


ans = [0] * N
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += pow(2, i, pc+1)
        m %= pc + 1
    else:
        m = m10
        m -= pow(2, i, pc-1)
        m %= pc - 1
    ans[i] = F(m) + 1

print(*ans[::-1], sep="\n")

Submission status: Accepted

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

N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += b01
        m01 %= pc + 1
        m10 += b10
        m10 %= pc - 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


memo = [0] * (N + 10)
for i in range(1, N + 10):
    p = pop_count(i)
    memo[i] = memo[i % p] + 1


ans = [0] * N
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += b01
        m %= pc + 1
    else:
        m = m10
        m -= b10
        m %= pc - 1
    ans[i] = memo[m] + 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1

print(*ans[::-1], sep="\n")

Submission status: Accepted

Solution code:
def g(x):
  S=format(x,"22b")
  cnt=0
  for i in range(20):
    if S[-1-i]=="1":
      cnt=cnt+1
  return x%cnt

n=int(input())
X=input()
a=0
for i in range(n):
  if X[i]=="1":
    a=a+1
#最初に割るのは a-1 or a+1 -> a==0,1 に注意
if a==0:
  for i in range(n):
    print(1)
  exit()
if a==1:
  if X[-1]=="1":
    for i in range(n-1):
      print(2)
    print(0)
    exit()
  else:
    for i in range(n-1):
      if X[i]=="1":
        print(0)
      else:
        print(1)
    print(2)
    exit()
D=[0]*n
E=[0]*n
D[0]=1%(a-1)
E[0]=1%(a+1)
b=int(X[-1])%(a-1)
c=int(X[-1])%(a+1)
for i in range(n-1):
  D[i+1]=(D[i]*2)%(a-1)
  E[i+1]=(E[i]*2)%(a+1)
  if X[-2-i]=="1":
    b=(b+D[i+1])%(a-1)
    c=(c+E[i+1])%(a+1)
for i in range(n):
  if X[i]=="1":
    x=(b+a-1-D[-1-i])%(a-1)
    ans=1
    while x!=0:
      x=g(x)
      ans=ans+1
    print(ans)
  else:
    x=(c+E[-1-i])%(a+1)
    ans=1
    while x!=0:
      x=g(x)
      ans=ans+1
    print(ans)