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:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    X = S()
    bit_cnt = X.count('1')
    one_inv_cnt = bit_cnt - 1
    zero_inv_cnt = bit_cnt + 1
    MAX = 2 * 10 ** 5 + 1

    # 大きい数の余り
    # 繰り返し２乗法の発展？
    zero_mod = 0
    one_mod = 0
    # for i in range(len(X)-1, -1, -1):
    for i in range(0, len(X)):
        b = int(X[i])
        if one_inv_cnt != 0:
            one_mod = (one_mod * 2 + b) % one_inv_cnt
        zero_mod = (zero_mod * 2 + b) % zero_inv_cnt

    f = [0] * MAX
    pop_count = [0] * MAX
    for i in range(1, MAX):
        pop_count[i] = pop_count[i//2] + i % 2
        f[i] = f[i % pop_count[i]] + 1

    for i in range(len(X)-1, -1, -1):
        if X[N-1-i] == '1':
            if one_inv_cnt != 0:
                nxt = one_mod
                nxt -= pow(2, i, one_inv_cnt)
                nxt %= one_inv_cnt
                print(f[nxt] + 1)
            else:
                print(0)
        else:
            nxt = zero_mod
            nxt += pow(2, i, zero_inv_cnt)
            nxt %= zero_inv_cnt
            print(f[nxt] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    X = S()
    bit_cnt = X.count('1')
    one_inv_cnt = bit_cnt - 1
    zero_inv_cnt = bit_cnt + 1
    MAX = 2 * 10 ** 5 + 1

    # 大きい数の余り
    # 繰り返し２乗法の発展？
    zero_inv_mod = 0
    one_inv_mod = 0
    # for i in range(len(X)-1, -1, -1):
    for i in range(0, len(X)):
        b = int(X[i])
        if one_inv_cnt != 0:
            one_inv_mod = (one_inv_mod * 2 + b) % one_inv_cnt
        zero_inv_mod = (zero_inv_mod * 2 + b) % zero_inv_cnt

    f = [0] * MAX
    pop_count = [0] * MAX
    for i in range(1, MAX):
        pop_count[i] = pop_count[i//2] + i % 2
        f[i] = f[i % pop_count[i]] + 1


    #pow2 の前計算
    one_pow2 = [1] * 220000
    zero_pow2 = [1] * 220000
    for i in range(1, 220000):
        if one_inv_cnt != 0:
            one_pow2[i] = one_pow2[i-1] * 2 % one_inv_cnt
        zero_pow2[i] = zero_pow2[i-1] * 2 % zero_inv_cnt

    for i in range(len(X)-1, -1, -1):
        if X[N-1-i] == '1':
            if one_inv_cnt != 0:
                nxt = one_inv_mod
                # nxt -= pow(2, i, one_inv_cnt)
                nxt -= one_pow2[i]
                nxt %= one_inv_cnt
                print(f[nxt] + 1)
            else:
                print(0)
        else:
            nxt = zero_inv_mod
            # nxt += pow(2, i, zero_inv_cnt)
            nxt += zero_pow2[i]
            nxt %= zero_inv_cnt
            print(f[nxt] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    X=input()

    x=int(X,2)
    pop_X=bin(x).count("1")

    pm1 = x % (pop_X-1) if pop_X-1 else 0
    pp1 = x % (pop_X+1)
    
    for i in range(N):
        sign = 1
        pop_Xi = pop_X
        if X[i] == "1": 
            sign *= -1
            pop_Xi -= 1
            _x = pm1
        else:
            pop_Xi += 1
            _x = pp1
        
        if pop_Xi == 0:
            print(0)
            continue
        
        
        two = pow(2,N-1-i,pop_Xi)
        X_i = _x + sign * two
        X_i %= pop_Xi
        count = 1
        while X_i:
            pop_Xi = bin(X_i).count("1")
            X_i = X_i % pop_Xi
            count += 1

        print(count)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

J=X.count("1")

Q,R=divmod(Y,J+1)
if J>1:
    S,T=divmod(Y,J-1)
else:
    S=T=0
    
A=[0]*N;A[-1]=1
for i in range(2,N+1):
    A[-i]=(A[-(i-1)]*2)%(J+1)

B=[0]*N
if J>1:
    B[-1]=1
    for j in range(2,N+1):
        B[-j]=(B[-(j-1)]*2)%(J-1)

H=[0]*N

for i in range(N):
    if X[i]=="0":
        U=(R+A[i])%(J+1)
    else:
        if J==1:
            continue
        U=(T-B[i])%(J-1)
        
    I=1
    while U>0:
        U=U%bin(U).count("1")
        I+=1
    H[i]=I

print("\n".join(map(str,H)))

Submission status: Accepted

Solution code:
n = int(input())
x = input()
memo = {0:0}
for i in range(1, n+1):
    j = i
    a = 0
    while True:
        if j in memo:
            memo[i] = memo[j]+a
            break;
        else:
            b = 0
            k = j
            while k > 0:
                if k%2 == 1:
                    b += 1
                k //= 2
            j %= b
            a += 1
n1 = 0
for i in range(n):
    if x[i] == "1":
        n1 += 1
if n1 > 1:
    mup = [1]
    mdown = [1]
    for i in range(1, n):
        mup.append(mup[-1]*2%(n1+1))
        mdown.append(mdown[-1]*2%(n1-1))
    mup.reverse()
    mdown.reverse()
    mmup = 0
    mmdown = 0
    for i in range(n):
        mmup = (mmup+mup[i]*int(x[i]))%(n1+1)
        mmdown = (mmdown+mdown[i]*int(x[i]))%(n1-1)
    for i in range(n):
        if x[i] == "0":
            state = "up"
            n1i = n1+1
        else:
            state = "down"
            n1i = n1-1
        if state == "up":
            mm = (mmup+mup[i])%n1i
        else:
            mm = (mmdown-mdown[i])%n1i
        print(memo[mm]+1)
elif n1 == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            if x[-1] == "0" and i != n-1:
                print(1)
            else:
                print(2)
else:
    for i in range(n):
        print(1)

Submission status: Accepted

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

J=X.count("1")

A=[0]*N
A[-1]=1
for i in range(2,N+1):
    A[-i]=(A[-(i-1)]*2)%(J+1)

B=[0]*N
if J>1:
    B[-1]=1
    for j in range(2,N+1):
        B[-j]=(B[-(j-1)]*2)%(J-1)


H=[0]*N

Q,R=divmod(Y,J+1)
if J>1:
    S,T=divmod(Y,J-1)
else:
    S=T=0

for i in range(N):
    if X[i]=="0":
        U=(R+A[i])%(J+1)
    else:
        if J==1:
            continue
        U=(T-B[i])%(J-1)
        
        
    I=1
    while U>0:
        U=U%bin(U).count("1")
        I+=1
    H[i]=I

print("\n".join(map(str,H)))

Submission status: Accepted

Solution code:
## 最初のmodをどうにか高速にやりたい → modの性質を使う
## xiのpopcount（1の数）はxのpopcount+1または-1
n=int(input())
x_str=input()
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
# x=int(x_str,2)
if x_popcount>1:
    pows_minus=[pow(2,i,(x_popcount-1)) for i in range(n)]
    # x_minus=x%(x_popcount-1)
    x_minus=0
    for i in range(n):
        if x_str[i]=='1':
            x_minus+=pows_minus[n-1-i]
pows_plus=[pow(2,i,(x_popcount+1)) for i in range(n)]
# x_plus=x%(x_popcount+1)
x_plus=0
for i in range(n):
    if x_str[i]=='1':
        x_plus+=pows_plus[n-1-i]

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

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


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

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=max(C-1,1)
C2=max(C+1,1)
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else -fac1[idx])
    #print(value,X[i]=="0",lst,C-1,C+1)
    bit=value
    count=0
    while value and _C:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))

Submission status: Accepted

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

def solve(x): #10進数
    ret=0
    while x>0:
        pop=bin(x).count("1")
        x%=pop
        ret+=1
    return ret

mod=X.count("1") #>0
original_plus=0
original_minus=0
for i in range(N):
    if X[N-1-i]=="1":
        if mod>1:
            original_minus+=pow(2,i,mod-1)
        original_plus+=pow(2,i,mod+1)
for i in range(N):
    if X[i]=="0":
        tmp=original_plus+pow(2,N-1-i,mod+1)
        tmp%=mod+1
        print(solve(tmp)+1)
    else:
        if mod==1:
            print(0)
            continue
        tmp=original_minus-pow(2,N-1-i,mod-1)
        tmp%=mod-1
        print(solve(tmp)+1)

Submission status: Accepted

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 

n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2
if d == -1:
    for i in range(n):
        print(1)
    exit()
elif d == 0:
    p = x.index("1")
    if p == n-1:
        for i in range(n-1):
            print(2)
        print(0)
        exit()
    elif p != n-1:
        for i in range(n):
            if i == n-1:
                print(2)
            elif i != p:
                print(1)
            elif i == p:
                print(0)
        exit()

amaric = [1 % c]
amarid = [1 % d]
for i in range(n-1):
    amaric.append((amaric[-1]*2)%c)
    amarid.append((amarid[-1]*2)%d)

motoc = 0
motod = 0
for i in range(n):
    if x[i] == "1":
        motoc += amaric[n-1-i]
        motod += amarid[n-1-i]

for i in range(n):
    if x[i] == "0":
        op = motoc
        op += amaric[n-1-i]
        op %= c
    elif x[i] == "1":
        op = motod
        op -= amarid[n-1-i]
        op %= d
    cou = 1
    while True:
        if op == 0:
            break
        op = popcount(op)
        cou += 1
    print(cou)

Submission status: Accepted

Solution code:
# coding: utf-8

def popcount(x):
    assert x.bit_length() <= 32
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    x_dec = int(x, 2)
    x_count = x.count('1')

    x_mod_set = x_dec % (x_count+1)
    xor_set = 1 % (x_count+1)
    if 1 < x_count:
        x_mod_reset = x_dec % (x_count-1)
        xor_reset = 1 % (x_count-1)

    A = [0]
    for i in range(1, x_count+2):
        A.append(A[i % popcount(i)]+1)

    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(str(0))
            continue

        m = x_mod_set + xor_set if x[-1-i] == '0' else x_mod_reset - xor_reset
        m %= bitcount

        ret.append(str(1+A[m]))

        xor_set = (xor_set << 1) % (x_count+1)
        if 1 < x_count:
            xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (n == 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))

Submission status: Accepted

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

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

nxp = nx%(pc+1)
nxm = nx%(pc-1) if pc > 1 else 0
for i in range(n-1, -1, -1):
    if (nx>>i)&1:
        # 2**iを引く
        if pc-1 == 0:
            print(0)
            continue
        p = pow(2, i, pc-1)
        r = (nxm-p)%(pc-1)
    else:
        # 2**iを足す
        r = (nxp+pow(2, i, pc+1))%(pc+1)

    print(f(r) + 1)

Submission status: Accepted

Solution code:
def popcount(u):
    t = bin(u)
    h = t.count("1")
    return u % h 

n = int(input())
x = list(input())
c = x.count("1") + 1
d = c - 2

amaric = [1 % c]
if d >= 1:
    amarid = [1 % d]
for i in range(n-1):
    amaric.append((amaric[-1]*2)%c)
    if d >= 1:
        amarid.append((amarid[-1]*2)%d)

motoc = 0
motod = 0
for i in range(n):
    if x[i] == "1":
        motoc += amaric[n-1-i]
        if d >= 1:
            motod += amarid[n-1-i]

for i in range(n):
    if x[i] == "0":
        op = motoc
        op += amaric[n-1-i]
        op %= c
    elif x[i] == "1":
        if d >= 1:
            op = motod
            op -= amarid[n-1-i]
            op %= d
        elif d == 0:
            print(0)
            continue
    cou = 1
    while True:
        if op == 0:
            break
        op = popcount(op)
        cou += 1
    print(cou)

Submission status: Accepted

Solution code:
n = int(input())
x = list(input())
x=[1 if s=='1' else 0 for s in x]
sumx=sum(x)

neg=0
pos=0

for i in range(n):
    if sumx-1!=0:
        neg+=pow(2,(n-i-1),sumx-1)*x[i]
        neg%=sumx-1
    pos+=pow(2,(n-i-1),sumx+1)*x[i]
    pos%=sumx+1

pops=[]

for i in range(n):
    if x[i]==1:
        if sumx==1:
            pops.append(-1)
        else:
            pops.append((neg-pow(2,(n-i-1),sumx-1)+sumx-1)%(sumx-1))
    elif x[i]==0:
        pops.append((pos+pow(2,(n-i-1),sumx+1))%(sumx+1))

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

for i in range(1,2*10**5+1):
    cnt=0
    tmp=i+0
    while tmp>0:
        cnt+=1
        b=bin(tmp)[2:]
        b=sum([1 if s=='1' else 0 for s in b])
        tmp%=b
    ans[i]=cnt

for p in pops:
    if p!=-1:
        print(ans[p]+1)
    else:
        print(0)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
t = int(x, 2)
c = x.count('1')
a = t % -~c
b = 0 if c < 2 else t % ~-c
for i in range(n):
    if int(x[i]):
        if c < 2:
            print(0)
            continue
        else:
            t = (b-pow(2, n-i-1, c-1)) % ~-c
    else:
        t = (a+pow(2, n-i-1, c+1)) % -~c
    z = 1
    while t:
        d = bin(t).count('1')
        t %= d
        z += 1
    print(z)

Submission status: Accepted

Solution code:
def fun(n):
    ops = 0
    while n:
        pc = format(n, 'b').count('1')
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = input()

sm = int(xs, 2)
pc = xs.count('1')

mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i, x in enumerate(xs, 1):
    df = 1 if x == '0' else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    rest = pow(2, n - i, pci)

    if x == '0':
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
X = input()
cnt = X.count('1')
memo = [0]*(N+1)
memo2 = [[0]*(N+1) for _ in range(2)]
memo2[0][1] = memo2[1][1] = 1

if cnt == 0:
  for _ in range(N):
    print(1)
  exit()

for i in range(1,N+1):
  if i == 1:
    if cnt > 1:
      memo2[0][i] = 1 % (cnt-1)
    memo2[1][i] = 1 % (cnt+1)
  else:
    if cnt > 1:
      memo2[0][i] = memo2[0][i-1]*2 % (cnt-1)
    memo2[1][i] = memo2[1][i-1]*2 % (cnt+1)
  t = 0
  a = i
  while a > 0:
    b = bin(a).count('1')
    a %= b
    t += 1
  memo[i] = t
  
X1 = 0
X_1 = 0
for i in range(1,N+1):
  if X[N-i] == '1':
    X1 += memo2[1][i]
    X_1 += memo2[0][i]
    X1 %= cnt+1
    if cnt > 1:
      X_1 %= cnt-1
    
for i in range(N,0,-1):
  Y = 0
  if X[N-i] == '1':
    if cnt == 1:
      print(0)
      continue
    Y = X_1 - memo2[0][i]
    if Y < 0:
      Y += cnt - 1
    print(memo[Y]+1)
  else:
    Y = X1 + memo2[1][i]
    Y %= cnt + 1
    print(memo[Y]+1)

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import defaultdict, deque


def popcount(x):
    assert x.bit_length() <= 32
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    dp = defaultdict(int)
    x_count = x.count('1')
    x_dec = int(x, 2)

    x_mod_set = x_dec % (x_count+1)
    xor_set = 1 % (x_count+1)
    if 1 < x_count:
        x_mod_reset = x_dec % (x_count-1)
        xor_reset = 1 % (x_count-1)

    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(str(0))
            continue

        m = (x_mod_set + xor_set
             if x[-1-i] == '0' else
             x_mod_reset - xor_reset) % bitcount
        deq = deque([m])

        count = 1
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1

        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

        xor_set = (xor_set << 1) % (x_count+1)
        if 1 < x_count:
            xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
def f(n,cnt):
    if n==0:
        return cnt
    popcnt = bin(n).count('1')
    return f(n%popcnt,cnt+1)

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

m = int(x,2)
m_cnt = x.count('1')

mp = m%(m_cnt+1)
mm = m%(m_cnt-1) if m_cnt > 1 else 0

for i,s in enumerate(x):
    i = n-1-i
    num = None

    if s == '0':
        mod = m_cnt+1
        num = (mp+pow(2,i,mod))%mod
    elif m_cnt > 1:
        mod = m_cnt-1
        num = (mm-pow(2,i,mod))%mod
    else:
        print(0)
        continue

    print(1+f(num,0))

Submission status: Accepted

Solution code:
from numba import njit

@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n != 0:
        a += n & 1
        n >>= 1
    return a

@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        pc = popcount(n)
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

# pcの差分を出した後の剰余計算を速くするため、事前にmod pc+1, mod pc-1を計算しておく
mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i in range(n):
    df = 1 if xs[i] == 0 else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    rest = pow(2, n - i - 1, pci)

    if xs[i] == 0:
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
X = input()[::-1]
mod = X.count('1')
listX = np.array(list(X), int)

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

if mod == 1:
    coefP = np.array([pow(2,i,mod+1) for i in range(N)])
    posi = np.dot(coefP, listX) % (mod+1)

    ans = []
    for i,x in enumerate(X):
        if x == '0':
            num = (posi + coefP[i]) % (mod+1)
            ans.append(simulate(num) + 1)
        else:
            ans.append(0)
    print(*ans[::-1], sep='\n')

else:
    coefP = np.array([pow(2,i,mod+1) for i in range(N)])
    coefN = np.array([pow(2,i,mod-1) for i in range(N)])
    posi = np.dot(coefP, listX) % (mod+1)
    nega = np.dot(coefN, listX) % (mod-1)

    ans = []
    for i,x in enumerate(X):
        if x == '0':
            num = (posi + coefP[i]) % (mod+1)
            ans.append(simulate(num) + 1)
        else:
            num = (nega - coefN[i]) % (mod-1)
            ans.append(simulate(num) + 1)
    print(*ans[::-1], sep='\n')

Submission status: Accepted

Solution code:
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    if c<2: print(0); continue
    else: t=(b-pow(2,n-i-1,c-1))%~-c
  else: t=(a+pow(2,n-i-1,c+1))%-~c
  z=1
  while t:
    d=bin(t).count('1')
    t%=d
    z+=1
  print(z)

Submission status: Accepted

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

N = I()

A = [0]  # A[i] = f(i) (0<=i<=N-1)
for i in range(1,N):
    a = 0  # iの2進表記に現れる1の個数
    for j in range(18):
        a += (i >> j) & 1
    A.append(1 + A[i % a])

X = LS2()

b = 0  # Xの2進表記に現れる1の個数
for i in range(N):
    if X[i] == '1':
        b += 1
if b >= 2:
    c1,c2 = b-1,b+1

    amari1 = [1]
    amari2 = [1]
    for i in range(1,N):
        amari1.append((amari1[-1]*2) % c1)
        amari2.append((amari2[-1]*2) % c2)
    amari1.reverse()
    amari2.reverse()

    # amari1[i] = 2**(N-i-1) mod c1
    # amari2[i] = 2**(N-i-1) mod c2

    r1,r2 = 0,0  # ri = X mod ci
    for i in range(N):
        if X[i] == '1':
            r1 += amari1[i]
            r1 %= c1
            r2 += amari2[i]
            r2 %= c2
    ANS = []
    for i in range(N):
        if X[i] == '1':
            ANS.append(A[(r1-amari1[i]) % c1]+1)
        else:
            ANS.append(A[(r2+amari2[i]) % c2]+1)
else:
    c2 = b+1

    amari2 = [1]
    for i in range(1, N):
        amari2.append((amari2[-1]*2) % c2)
    amari2.reverse()

    # amari2[i] = 2**(N-i-1) mod c2

    r2 = 0  # X mod c2
    for i in range(N):
        if X[i] == '1':
            r2 += amari2[i]
            r2 %= c2
    ANS = []
    for i in range(N):
        if X[i] == '1':
            ANS.append(0)
        else:
            ANS.append(A[(r2+amari2[i]) % c2] + 1)

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    #nagasa = 5
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            #t_m = bin(t_v).count("1")
        d_li[i] = ans
    
    #print(d_li)
    #exit()
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    #print(val)
    #exit()
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    
    t_v_p = val % (mod+1)
    if mod == 1:
        t_v_m = 0
    else:
        t_v_m = val % (mod-1)
        
    for i in range(n):
        ans = 0
        #t_v = val
        #t_m = mod
        if int(x[i]) == 1:
            if mod == 1:
                t_v = 0
            else:
                t_v = t_v_m
                t_v -= pow(2,(n-1-i),mod-1)
                #t_v -= rui % (mod-1)
                t_v %= (mod-1)
                ans += 1
                #t_m -= 1
        else:
            t_v = t_v_p
            t_v += pow(2,(n-1-i),mod+1)
            #print(t_v,rui)
            #t_v += rui % (mod+1)
            t_v %= (mod+1)
            ans += 1
            #t_m += 1
        rui //= 2
        #print(t_v,mod)
        #while t_v != 0:
        """
        if t_v != 0:
            if int(x[i]) == 1:
                if mod == 1:
                    t_v = 0
                else:
                    t_v %= mod-1
            else:
                t_v %= mod + 1
            #t_v %= t_m
            ans += 1
        """
        ans += d_li[t_v]
        #t_m = bin(t_v).count("1")
        #ans_li.append(ans)
        print(ans)
        #print(ans_li)
        
if __name__ == '__main__':
    main()
"""
#print(ans_li)
for i in range(n):
    print(ans_li[n-1-i])
"""

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from sys import flags
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
x=list(input())
cnt=Counter(x)
x2=int("".join(x),2)
one=cnt["1"]
# print(x)
# print(math.log2(2*10**5))
# print(cnt)
# print(x2,one)
lst=[0]*(2*10**5+10)
# lst[0]=-1
flaglst=[0,0]
if one-1!=0:
    flaglst[0]=x2%(one-1)
flaglst[1]=x2%(one+1)
# print(flaglst)

for i in range(2*10**5):
    now=i+1
    ans=0
    while now:
        cnt2=0
        m=0
        while now>=pow(2,m):
            if now&1<<m:
                cnt2+=1
            m+=1
        now%=cnt2
        ans+=1
    lst[i+1]=ans
# # print(lst[:100])

for i in range(n):
    tmp=0
    if x[i]=="1":
        tmp=flaglst[0]
        if one-1!=0:
            tmp-=pow(2,n-1-i,one-1)
            tmp%=one-1
        else:
            print(0)
            continue
    else:
        tmp=x2%(one+1)
        tmp+=pow(2,n-1-i,one+1)
        tmp%=one+1
    # print(tmp,pow(2,n-1-i),one)

    print(lst[tmp]+1)

Submission status: Accepted

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

cnt = X.count("1")
res0 = 0
res1 = 0
for i in range(N):
    if X[i] == "1":
        res0 = (res0 + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)

        if cnt - 1 > 0:
            res1 = (res1 + pow(2, N - i - 1, cnt - 1)) % (cnt - 1)

for i in range(N):
    ans = 0
    if X[i] == "0":
        div = cnt + 1
        tmp = (res0 + pow(2, N - i - 1, div)) % div
        ans += 1
    else:
        if cnt - 1 > 0:
            div = cnt - 1
            tmp = (res1 + div - pow(2, N - i - 1, div)) % div
            ans += 1
        else:
            tmp = 0

    while tmp > 0:
        ans += 1
        div = bin(tmp).count("1")
        tmp %= div
        
    print(ans)