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:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print("\n".join(map(str, [1]*N)))
        return

    X = int(S, 2)

    def f2():
        cache = [0] * (cnt0 + 1)
        i = 1
        bi = []
        while i <= cnt0:
            bi.append(i)
            i <<= 1
        from collections import deque
        dq = deque([(0, 0, 0)])
        ls = len(bi) -1
        while dq:
            i, x, cnt = dq.popleft()

            cnt += 1
            for j in range(i, ls):
                y = x | bi[j]

                if y > cnt0: break

                cache[y] = cache[y % cnt] + 1

                j += 1
                dq.append((j, y, cnt))
            else:
                y = x | bi[ls]
                if y > cnt0: continue
                cache[y] = cache[y % cnt] + 1
        return cache


    memo = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + memo[n]

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
def main():
    """
    a % d + c % d = (a + c) % dだ
    整数の余りを取るのと，整数の各桁の余りを取るのが同じを使うこともあった　→　Digits Parade
    """
    N = int(input())
    X = input()
    t = X.count("1")
    v1, v2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            # 反転してt+1
            x = v1 + pow(2, N-i-1, t+1)
            x %= t+1
        elif t != 1 and X[i] == "1":
            # 反転してt-1
            x = v2 - pow(2, N-i-1, t-1)
            x %= t-1
        else:
            # t == 1 かつ その"1"を反転するとき
            # 当然X_iは0になる，答えも0
            ans = 0
        while x > 0:
            x %= "{:0b}".format(x).count("1")
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    """
    a % d + c % d = (a + c) % dだ
    整数の余りを取るのと，整数の各桁の余りを取るのが同じこともあった　→　Digits Parade
    """
    N = int(input())
    X = input()
    t = X.count("1")
    v1, v2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            # 反転してt+1
            x = v1 + pow(2, N-i-1, t+1)
            x %= t+1
        elif t != 1 and X[i] == "1":
            # 反転してt-1
            x = v2 - pow(2, N-i-1, t-1)
            x %= t-1
        else:
            # t == 1 かつ その"1"を反転するとき
            # 当然X_iは0になる，答えも0
            ans = 0
        while x > 0:
            x %= "{:0b}".format(x).count("1")
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

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

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Submission status: Accepted

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

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


def f(n):
    if n== 0:
        return 1
    count = 1
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


X_popcount = popcount(X)
X_mod_p = X%(X_popcount+1)
if X_popcount != 1:
    X_mod_m = X%(X_popcount-1)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X_i == 0:
        ans = 0
    elif X>>(N-i-1)&1 == 1:
        if X_popcount == 1:
            ans = 1
        else:
            ans = f((X_mod_m-pow(2, N-i-1, X_popcount-1))%(X_popcount-1))
    else:
        ans = f((X_mod_p+pow(2, N-i-1, X_popcount+1))%(X_popcount+1))
    print(ans)

Submission status: Accepted

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

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x_bin[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        a = (x_m - m[i-1]) % pc_m
        print(rest[a] + 1)
    else:
        a = (x_p + p[i-1]) % pc_p
        print(rest[a] + 1)

Submission status: Accepted

Solution code:
N = int(input())
X = input()
memo = {}
X_int = int(X, 2)


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


pcf = popcount(int(X, 2))
pcm = pcf - 1
pcp = pcf + 1
xm = X_int % pcm if pcm != 0 else 0
xp = X_int % pcp


def f(n: int, ops: int):

    while n != 0:
        n %= popcount(n)
        ops += 1
    return ops


def rev(x: str, i: int):
    if x == "1":
        if pcm == 0:
            return -1
        n = (xm - (pow(2, N-i-1, pcm))) % pcm
    else:
        n = (xp + (pow(2, N-i-1, pcp))) % pcp
    return n


if __name__ == "__main__":
    for i, x in enumerate(X):
        n = rev(x, i)
        if n == -1:
            print(0)
        else:
            print(f(n, 1))

Submission status: Accepted

Solution code:
#2回目以降のあまりを計算
def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

N = int(input())
S = input()

#入力を数値に変換
X = int(S, 2)

#元のbit数をカウント
pcx = S.count("1")
#bit数は-1, +1のみなので予め計算しておく
#カウントが0ならば0にしておく
pc1 = X % (pcx - 1) if pcx > 1 else 0
pc2 = X % (pcx + 1)

for i, y in enumerate(S):
    k = N - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)

Submission status: Accepted

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

N, X = open(0).read().split()
N = int(N)
XS = list(X)
X = int(X, 2)

p = popcount(X)
xi = X % (p + 1)
if p == 1:
    xd = 0
else:
    xd = X % (p - 1)

for i in range(N):
    if XS[i] == "1":
        if p == 1:
            print(0)
            continue
        else:
            k = pow(2, N - 1 - i, p - 1)
            x = (xd - k) % (p - 1)
    else:
        k = pow(2, N - 1 - i, p + 1)
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
def main():
    """
    a % d + c % d = (a + c) % dだよね
    整数の余りを取るのと，整数の各桁の余りを取るのが同じこともあった　→　Digits Parade
    """
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            # 反転してt+1
            p = pow(2, N-i-1, t+1)
            x = x1 + p
            x %= t+1
        elif t != 1 and X[i] == "1":
            p = pow(2, N-i-1, t-1)
            x = x2 - p
            x %= (t-1)
        else:
            # t == 1 かつ その"1"を反転するとき
            # 当然X_iは0になる，答えも0
            ans = 0
        while x > 0:
            x %= "{:0b}".format(x).count("1")
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
x=input()
p=0
for i in x:
    if i=="1":
        p+=1
rp=0
rq=0
for i in range(n):
    if x[i]=="1":
        rp+=pow(2,(n-1-i),p+1)
        rp%=p+1
        if p!=1:
          rq+=pow(2,(n-1-i),p-1)
          rq%=p-1
        else:
          rq=pow(2,(n-1-i))
def popcnt1(n):
    return bin(n).count("1")
res=[0]*n

for i in range(1,n+1):
    res[i-1]=i%popcnt1(i)

for i in range(n):
    ans=0
    if x[i]=="1":
        if p==1:
          print(0)
          continue
        q=rq-pow(2,(n-1-i),p-1)
        q%=p-1
        while True:
            if q==0:
                print(1+ans)
                break
            ans+=1
            q=res[q-1]
    else:
        q=rp+pow(2,(n-1-i),p+1)
        q%=p+1
        while True:
            if q==0:
                print(1+ans)
                break
            ans+=1
            q=res[q-1]

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print("\n".join(map(str, [1]*N)))
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
x = input()
original_pop_cnt = x.count("1")

pop_cnt_add = original_pop_cnt + 1
pop_cnt_sub = original_pop_cnt - 1

n_after_once_popcount_add = 0
n_after_once_popcount_sub = 0

for i in range(n):
    n_after_once_popcount_add = (n_after_once_popcount_add * 2 + int(x[i])) % pop_cnt_add
    if pop_cnt_sub != 0:
        n_after_once_popcount_sub = (n_after_once_popcount_sub * 2 + int(x[i])) % pop_cnt_sub

pow_add = [1] * 250000
pow_sub = [1] * 250000
for i in range(1, n + 100):
    pow_add[i] = (pow_add[i-1]*2) % pop_cnt_add
    if pop_cnt_sub != 0:
        pow_sub[i] = (pow_sub[i-1]*2) % pop_cnt_sub

def f(nex):
    ans = 0
    num = nex
    while num != 0:
        num = num % bin(num).count("1")
        ans += 1
    return ans

for i in range(n-1, -1, -1):
    if x[n - 1 - i] == "0":
        nxt = n_after_once_popcount_add
        nxt = nxt + pow_add[i]
        nxt = nxt % pop_cnt_add
        print(f(nxt) + 1)
    if x[n - 1 - i] == "1":
        if pop_cnt_sub != 0:
            nxt = n_after_once_popcount_sub
            nxt = nxt - pow_sub[i]
            nxt = nxt % pop_cnt_sub
            print(f(nxt) + 1)
        else:
            print(0)

Submission status: Accepted

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

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

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

intx_mod_pp1 = intx %(popcount0+1)
if popcount0!=1:
    intx_mod_pm1 = intx %(popcount0-1)
    
jisho = ["yet"]*n
for i in range(n):
    if x[i]=="1" and popcount0==1:
        print(0)
        continue
    
    pow2ip = pow(2,n-i-1,popcount0+1)
    if popcount0!=1:   pow2im = pow(2,n-i-1,popcount0-1)
    
    intxi=1
    c=0
    while intxi!=0:
        if c==0:
            if x[i]=="0":
                pop = popcount0+1
                intxi = (intx_mod_pp1 + pow2ip%pop )%pop
            else:
                pop = popcount0-1
                intxi = (intx_mod_pm1 - pow2im%pop )%pop        
        else:
            if jisho[intxi]=="yet":
                togo = intxi%popcount(intxi)
                jisho[intxi]= togo
                intxi = togo
            else:
                intxi =jisho[intxi]
        c+=1
    print(c)

Submission status: Accepted

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

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

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

intx_mod_pp1 = intx %(popcount0+1)
if popcount0!=1:
    intx_mod_pm1 = intx %(popcount0-1)
    

jisho = ["yet"]*n
# pow2ip = .5
# pow2im = .5

for i in range(n):
    if x[i]=="1" and popcount0==1:
        print(0)
        continue
    
    pow2ip = pow(2,n-i-1,popcount0+1)
    if popcount0!=1:
        pow2im = pow(2,n-i-1,popcount0-1)

    if False:
        pass
    
    
    else:
        intxi=1
        c=0
        while intxi!=0:
            if c==0:
                if x[i]=="0":
                    pop = popcount0+1
                    intxi = (intx_mod_pp1 + pow2ip%pop )%pop
                else:
                    pop = popcount0-1
                    intxi = (intx_mod_pm1 - pow2im%pop )%pop        
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            #print(intxi)
            c+=1
        print(c)
        #print()
    
#        print("f(n)=",c)

Submission status: Accepted

Solution code:
table = [0 for i in range(2*10**5+5)]
for i in range(2*10**5+5):
    table[i] = "{:0b}".format(i).count("1")


def main():
    """
    a % d + c % d = (a + c) % dだよね
    整数の余りを取るのと，整数の各桁の余りを取るのが同じこともあった　→　Digits Parade
    """
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            # 反転してt+1
            p = pow(2, N-i-1, t+1)
            x = x1 + p
            x %= t+1
        elif t != 1 and X[i] == "1":
            p = pow(2, N-i-1, t-1)
            x = x2 - p
            x %= (t-1)
        else:
            # t == 1 かつ その"1"を反転するとき
            # 当然X_iは0になる，答えも0
            ans = 0
        while x > 0:
            x %= table[x]
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
X = int(S, 2)
pcx = S.count('1')
# ビット反転で1が0になる場合
pc1 = X % (pcx - 1) if pcx > 1 else 0
# ビット反転で0が1になる場合
pc2 = X % (pcx + 1)


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


for i, y in enumerate(S):
    k = N - i - 1
    if y == "0":  # modを分配するときは、分配してからもう１回modを作用させれば良い
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)

Submission status: Accepted

Solution code:
N = int(input())
X = str(input())
F = [0] * N

def calc_f(n:int)->int:
    global F
    x = n
    res = 0
    while 0 < x:
        if F[x] != 0:
            res += F[x]
            break
        pop = bin(n).count('1')
        x %= pop
        res += 1
    F[n] = res

# 前処理 N以下のF値テーブル
for i in range(1, N):
    calc_f(i)

# ビット反転すると初期の1の個数に対して+1または-1どちらか
pop_ini = X.count('1')
pp = pop_ini + 1  # pop_plus
pm = pop_ini - 1  # pop_minus

# 2進の各桁をppとpmで割った値のテーブル
ap = [0] * N  # arr_plus
am = [0] * N  # arr_minus
for i in range(N):
    ap[i] = pow(2, N-1-i, pp)
    if 0 < pm:
        am[i] = pow(2, N-1-i, pm)

# 所与のXで計算、ベースになる値
fp = 0  # f_plus
fm = 0  # f_minus
for i in range(N):
    if X[i] == '1':
        fp = (fp + ap[i]) % pp
        if 0 < pm:
            fm = (fm + am[i]) % pm

# 各桁を反転した場合では差分更新のみ
for i in range(N):
    ans = 1
    if X[i] == '1':
        if 0 < pm:
            v = (fm + pm - am[i]) % pm
        else:
            ans = 0
            v = 0
    else:
        v = (fp + ap[i]) % pp
    if 0 < v:
        ans += F[v]
    print(ans)

Submission status: Accepted

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

def p_count(n):
    return bin(n)[2:].count('1')


n = int(input())
x = input().rstrip()
x_dec = int(x,base = 2)

pop_cnt = x.count('1')
pop_cnt_0 = (pop_cnt + 1)
pop_cnt_1 = (pop_cnt - 1)
x_0 = pow(x_dec,1,pop_cnt_0)
x_1 = pow(x_dec,1,pop_cnt_1) if pop_cnt_1 > 0 else 0

x_bit = [0]*n

for i in range(n-1,-1,-1):
    if x[i] == '0':
        x_bit[i] = (x_0 + pow(2,n-1-i,pop_cnt_0))%pop_cnt_0
        #x_bit[i] = (x_dec + pow(2,n-1-i))%pop_cnt_0
        
    else:
        if pop_cnt_1 > 0:
            x_bit[i] = (x_1 - pow(2,n-1-i,pop_cnt_1))
            x_bit[i] = x_bit[i] if x_bit[i] >= 0 else x_bit[i] + pop_cnt_1
        else:
            x_bit[i] = -1

anslist = []
for i in range(n):
    if x_bit[i] == -1:
        anslist.append(0)
        continue
    ans = 1 
    now = x_bit[i]
    while True:
        if now == 0:
            break
        now = now%p_count(now)
        
        ans += 1
    anslist.append(ans)


for ans in anslist:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
 
# 元のpopcount
original_pop_count = x.count('1')
# 反転して-1count
one_pop_count = original_pop_count - 1
# 反転して+1count
zero_pop_count = original_pop_count + 1
 
# ±1それぞれにおける余り
if one_pop_count == 0:
  one_mod = 0
else:
  one_mod = int(x, 2) % one_pop_count
zero_mod = int(x, 2) % zero_pop_count
 
# f の前計算 
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    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_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            # - 2^i % 2
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        # + 2^i % 2
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Submission status: Accepted

Solution code:
N = int(input())
X_2 = input()
X_10 = int(X_2, 2)

y = X_2.count('1')

a = X_10%(y+1)
if y==1:
    b = 0
else:
    b = X_10%(y-1)

for i in range(N):
    if X_2[i] == '1' and y == 1:
        print(0)
        continue
    elif X_2[i] == '1':
        x = (b-pow(2, N-1-i, y-1))%(y-1)
    else:
        x = (a+pow(2, N-1-i, y+1))%(y+1)
    count = 1
    while x!=0:
        x %= bin(x)[2:].count('1')
        count += 1
    print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

pc_memo = defaultdict(int)
memo = defaultdict(int)


def to_next(x):
    if x not in pc_memo.keys():
        pc_memo[x] = x % "{:b}".format(x).count('1')
    return pc_memo[x]


def f(x):
    if x == 0:
        return 0
    if x not in memo.keys():
        memo[x] = f(to_next(x))+1
    return memo[x]


for i in range(2*10**5):
    f(i)

n = int(input())
x = input().rstrip()
one_cnt = x.count('1')

mod_minus = 0
mod_plus = 0
for i, a in enumerate(reversed(x)):
    if a == '1':
        if 0 < one_cnt-1:
            mod_minus += pow(2, i, one_cnt-1)
            mod_minus %= one_cnt-1
        mod_plus += pow(2, i, one_cnt+1)
        mod_plus %= one_cnt+1


for i in range(n):
    if x[i] == '0':
        nx = mod_plus+pow(2, n-i-1, one_cnt+1)
        nx %= one_cnt+1
        print(f(nx)+1)
    else:
        if 0 < one_cnt-1:
            nx = mod_minus-pow(2, n-i-1, one_cnt-1)
            nx %= one_cnt-1
            print(f(nx)+1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
X = input()
if X == '0':
    for _ in range(N):
        print(1)
        exit()

mem = [None] * (200005)
mem[0] = 0
def f(n):
    if mem[n] is not None: return mem[n]
    c = bin(n).count('1')
    r = 1 + f(n%c)
    mem[n] = r
    return r

for i in range(200005):
    f(i)

cnt = X.count('1')
a,b = cnt+1, cnt-1

ans = [None] * N
x = int(X,2)

n = x % a
for i,c in reversed(list(enumerate(X))):
    if c=='1': continue
    ans[i] = mem[(n+pow(2,N-i-1,a))%a] + 1

if b:
    n = x % b
    for i,c in reversed(list(enumerate(X))):
        if c=='0': continue
        ans[i] = mem[(n-pow(2,N-i-1,b))%b] + 1
else:
    for i in range(N):
        if ans[i] is None:
            ans[i] = 0

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

Submission status: Accepted

Solution code:
n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in enumerate(x):
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(2)

else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])

Submission status: Accepted

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

a = int(X, 2)
b = X.count("1")

if b > 1:
    a1 = a % (b-1)
else:
    a1 = 0
a0 = a % (b+1)

for i in range(N):
    if X[i] == "1":
        if b == 1:
            print(0)
            continue
        t = (a1 - pow(2, N-1-i, b-1)) % (b-1)
    else:
        t = (a0 + pow(2, N-1-i, b+1)) % (b+1)
    
    ans = 1
    while t > 0:
        t %= bin(t).count("1")
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


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


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


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


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

Submission status: Accepted

Solution code:
n=int(input())
x=list(input())
def str2int(z):
  flag=1
  a=0
  for i in reversed(x):
    if i=='1':a+=flag
    flag*=2
  return a
 
popc=x.count('1')
z=str2int(x)
if popc-1!=0:
  fl_1=z%(popc-1)
fl_0=z%(popc+1)

for i in range(n):
  if x[i]=='1':
    if popc-1==0:
      print(0)
      continue
    mod=(fl_1-pow(2,n-1-i,popc-1))%(popc-1)
  else:mod=(fl_0+pow(2,n-1-i,popc+1))%(popc+1)
  #print('mod : %s'%mod)
  cnt=1
  while mod!=0:
    pp=bin(mod).count("1")
    mod%=pp
    cnt+=1
  print(cnt)

Submission status: Accepted

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

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

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


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


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


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


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

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(3): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                #hit[x] += 1
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        ni = N - i - 1
        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0] = m2; m1[1] = i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def mpow(a,b,m):
    ans=1
    while b >0 :
        if b&1:
            ans = (ans*a)%m
        a=(a*a)%m
        b=b>>1

    return ans

def calcmod(X,m,N):
    mod=0
    X=X[::-1]
    # print(X)
    for i in range(N):
        if X[i] == '1':
        # if X & (1<<i) >0:
            mod += mpow(2,i,m)
            mod%=m
    return mod

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


def findsteps(mm):
    cnt=0
    while mm !=0:
        cnt+=1
        mm=mm%popcount(mm)
    return cnt
N=int(input())
x=input()
X=int(x,2)

##we need to find X%(m-1) and X%(m+1)
m=popcount(X)
m1=m+1
m2=m-1
firstmod=calcmod(x,m1,N)
if m2 !=0:
    secondmod=calcmod(x,m2,N)
fans=[0 for i in range(N)]
k=0
for i in range(N-1,-1,-1):
    if X & (1<<i) >0:
        ##the bit was set
        ##we need to find X%(m-1) - (2^i)%(m-1)
        if m2 == 0:
            ans=0
        else:
            mm=secondmod - mpow(2,i,m2)
            if mm < 0:
                mm+=m2
            mm=mm%m2
            ans=1+findsteps(mm)
    else:
        mm = firstmod + mpow(2,i,m1)
        mm=mm%m1
        ans=1+findsteps(mm)
    fans[k] = ans
    k+=1
        ##the bit was not set
for i in fans:
    print(i)