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:
import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

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

#nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = 0
nXm = 0

pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(N):
    if X[i] == '1':
        nXp += pow1[N-1-i]
nXp %= MOD1

if MOD2 != 0:
    for i in range(N):
        if X[i] == '1':
            nXm += pow2[N-1-i]

    nXm %= MOD2
    

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt
def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

N = int(input())
X = input()
ones = X.count('1')
MOD1 = ones + 1
MOD2 = ones - 1
pow1 = [1] * (len(X) + 1)
pow2 = [1] * (len(X) + 1)
if MOD2 != 0:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1
        pow2[i] = (pow2[i - 1] * 2) % MOD2
else:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1

X1, X2 = 0, 0
for i in range(N):
    if X[i] == '1':
        X1 += pow1[N - i - 1]
        X2 += pow2[N - i - 1]
X1 %= MOD1
if MOD2 != 0:
    X2 %= MOD2

for i in range(N):
    d = N - i - 1
    if X[i] == '0':
        x = (X1 + pow1[d]) % MOD1
        print(f(x) + 1)
    else:
        if MOD2 != 0:
            x = (X2 - pow2[d]) % MOD2
            print(f(x) + 1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt
def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

ones = X.count('1')
MOD1 = ones + 1
MOD2 = ones - 1
pow1 = [1] * (len(X) + 1)
pow2 = [0] * (len(X) + 1)
if MOD2 != 0:
    pow1[0] = 1
    pow2[0] = 1
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1
        pow2[i] = (pow2[i - 1] * 2) % MOD2
else:
    for i in range(1, len(X) + 1):
        pow1[i] = (pow1[i - 1] * 2) % MOD1

X1 = 0
X2 = 0
for i in range(N):
    if X[i] == '1':
        X1 += pow1[N - i - 1]
        X2 += pow2[N - i - 1]
X1 %= MOD1
if MOD2 != 0:
    X2 %= MOD2

for i in range(N):
    d = N - i - 1
    if X[i] == '0':
        x = (X1 + pow1[d]) % MOD1
        print(f(x) + 1)
    else:
        if MOD2 != 0:
            x = (X2 - pow2[d]) % MOD2
            print(f(x) + 1)
        else:
            print(0)

Submission status: Accepted

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

def f(x):
    if x == 0:
        return 1
    return f(x%popcount(x))+1

n=int(input())
x=input()
xx=int(x,2)
p=x.count('1')
s=xx%(p+1)
if p!=1:
    t=xx%(p-1)
for i in range(n):
    if x[i]=='1':
        if p!=1:
            k=t
            k-=pow(2,n-i-1,p-1) 
            k%=p-1
        else:
            print(0)
            continue
    else:
        k=s
        k+=pow(2,n-i-1,p+1)
        k%=p+1
    print(f(k))

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

popcount = lambda x: bin(x).count("1")
bitflip = lambda x, n: x ^ (1 << n)
bitflip2 = lambda x, n: x ^ (1 << (len(bin(x))-2 - (n+1)))
bits = lambda x, n = 0: bin(x)[2:].zfill(n)

N = n1()
X = list(map(int, list(s1())))

rt = [0, 0]
t1 = 1
t2 = 1
p = X.count(1)

for i in range(N-1, -1, -1):    
    if X[i] == 1:
        if p > 1: rt[0] = (rt[0] + t1) % (p - 1)
        rt[1] = (rt[1] + t2) % (p + 1)
    if p > 1: t1 = t1 * 2 % (p - 1)
    t2 = t2 * 2 % (p + 1)

for i in range(N):
    if X[i] == 1 and p == 1:
        print(0)
        continue

    if X[i] == 0:
        t = (rt[1] + pow(2, N-i-1, p+1)) % (p + 1)
    else:
        t = (rt[0] - pow(2, N-i-1, p-1)) % (p - 1)

    ans = 1
    while t > 0:
        t %= popcount(t)
        ans += 1
    
    print(ans)

Submission status: Accepted

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

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    #print(i,"num",num)
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
x=input()
p=x.count('1')

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count+1

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    z=x.index('1')
    t=pow(2,n-z-1,p+1)
    for i in range(n):
        if i==z:
            print(0)
        else:
            tmp=(t+pow(2,n-i-1,p+1))%(p+1)
            print(solve(tmp))
    exit()


#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp))

Submission status: Accepted

Solution code:
N = int(input())
X = input()
X_arr = list(X)
N, X = int(N), int(X, 2)
MAX_N = 2 * 10 ** 5


def popcount(x):
    cnt = 0
    for i in range(x.bit_length()):
        if x & 1 << i:
            cnt += 1
    return cnt


memo = [0] * (MAX_N + 1)
for i, n in enumerate(range(1, MAX_N + 1), start=1):
    cnt = 0
    while n:
        p = popcount(n)
        n = n % p
        cnt += 1
    memo[i] = cnt


x_popcount = popcount(X)
p_upper, p_downer = x_popcount + 1, x_popcount - 1
y_upper = X % p_upper
y_downer = X % p_downer if p_downer else None

for i in range(N):
    if X_arr[i] == '0':
        z = (y_upper + pow(2, (N - i - 1), p_upper)) % p_upper
    else:
        if not p_downer:
            print(0)
            continue
        z = (y_downer - pow(2, (N - i - 1), p_downer)) % p_downer

    print(memo[z] + 1)

Submission status: Accepted

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

num_of_one = x.count("1")

#xの中に1が1つもない時
if num_of_one == 0:
    for i in range(n):
        print(1)
#xの中に1が1つの時(1を取り除くと0個になる)
elif num_of_one == 1:
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            #1が2個なので偶数なら余り0
            if x[-1] == "0" and i != n-1:
                print(1)
            #奇数なら1回1を経由
            else:
                print(2)
else:
    dic = collections.defaultdict(int)
    #0からnまでの回数を予め求めて辞書に格納
    for i in range(n):
        tmp_p = i

        cnt = 0
        while tmp_p:
            tmp_p %= bin(tmp_p).count("1")
            cnt += 1
        dic[i] = cnt


    #2冪を num_of_one ± 1 で割った余りの配列を用意しておく
    bi_mod_p = [1 % (num_of_one+1)]
    bi_mod_m = [1 % (num_of_one-1)]
    for i in range(1,n):
        bi_mod_p.append((bi_mod_p[-1] * 2) % (num_of_one+1))
        bi_mod_m.append((bi_mod_m[-1] * 2) % (num_of_one-1))

    #xと逆順なので合わせる
    bi_mod_p.reverse()
    bi_mod_m.reverse()

    #xの10進表記を num_of_one ± 1 で割った余りを用意する
    sum_p = 0
    sum_m = 0
    for i in range(n):
        if x[i] == "1":
            sum_p += bi_mod_p[i]
            sum_p %= (num_of_one+1)
            sum_m += bi_mod_m[i]
            sum_m %= (num_of_one-1)
    tmp = 0
    for i in range(n):
        # 0 -> 1 の変化。1が増えるのでpの方を使う
        if x[i] == "0":
            tmp = sum_p + bi_mod_p[i]
            tmp %= (num_of_one+1)

        # 1 -> 0 の変化。1が減るのでmの方を使う
        else:
            tmp = sum_m - bi_mod_m[i]
            if tmp < 0:
                tmp += (num_of_one-1)
            tmp %= (num_of_one-1)
        print(dic[tmp]+1)

Submission status: Accepted

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

pcn=x.count('1')
px=int(x,2)%(pcn+1)
mx=int(x,2)%(pcn-1) if pcn>1 else 0
p2=[0]*n
m2=[0]*n

for i in range(n):
    p2[i]=pow(2,n-1-i,pcn+1)
    m2[i]=pow(2,n-1-i,pcn-1) if pcn>1 else 0

for i in range(n):
    p=False if int(x[i])&1 else True
    if pcn==1 and not p:
        print(0)
        continue
    ans=0
    tmp=0
    if(p):
        tmp=(px+p2[i])%(pcn+1)
    else:
        tmp=(mx-m2[i])%(pcn-1)
    ans+=1
    while tmp!=0:
        ipcn=str(bin(tmp)).count('1')
        tmp%=ipcn
        ans+=1
    print(ans)

Submission status: Accepted

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

pop_X = sum(map(int,list(X)))
X_10 = int('0b'+X,2)

r_0 = X_10%(pop_X+1)
diff_0 = 1%(pop_X+1)

zero_flag = False
if pop_X == 1:
    zero_flag = True
else:
    r_1 = X_10%(pop_X-1)
    diff_1 = 1%(pop_X-1)

answer = []


for i in range(N)[::-1]:
    if X[i]=='0':
        r = (r_0+diff_0)%(pop_X+1)
    else:
        if zero_flag:
            answer.append(0)
            diff_0 = (diff_0*2)%(pop_X+1)
            continue
        else:
            r = (r_1-diff_1)%(pop_X-1)
    count = 1
    while True:
        if r == 0:
            break
        pop = sum(map(int,list(bin(r)[2:])))
        r = r % pop
        count += 1
        
    answer.append(count)
    diff_0 = (diff_0*2)%(pop_X+1)
    if zero_flag:
        continue
    diff_1 = (diff_1*2)%(pop_X-1)

for i in answer[::-1]:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())
x = input()[::-1]

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

p = x.count("1")
p1, p2 = p + 1, p - 1

if p == 1:
    ii = x.index("1")
    x1 = pow(2, ii, p1)
    for i in range(n)[::-1]:
        if i == ii:
            print(0)
        else:
            r = (x1 + pow(2, i, p1)) % p1
            print(f[r] + 1)
    exit()

x1 = x2 = 0
for i in range(n):
    if x[i] == "1":
        x1 += pow(2, i, p1); x2 += pow(2, i, p2)
        x1 %= p1; x2 %= p2

for i in range(n)[::-1]:
    if x[i] == "0":
        r = (x1 + pow(2, i, p1)) % p1
    else:
        r = (x2 - pow(2, i, p2)) % p2
    print(f[r] + 1)

Submission status: Accepted

Solution code:
N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-1)

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

for i in range(N):
  if X[i]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))

Submission status: Accepted

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

def pop_cnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c

pop_S = 0
for s in S:
    if s == "1":
        pop_S += 1

p1 = pop_S + 1
p2 = pop_S - 1
#print(p1, p2)

mod_sum1 = 0
mod_sum2 = 0
for i, s in enumerate(S):
    if s == "1":
        mod_sum1 = (mod_sum1 + pow(2, N - i - 1, p1)) % p1
        if p2:
            mod_sum2 = (mod_sum2 + pow(2, N - i - 1, p2)) % p2
#print(mod_sum1, mod_sum2)

cnt = [0] * (p1 + 2)

for i in range(1, p1 + 1):
    cnt[i] = cnt[i % pop_cnt(i)] + 1
#print(cnt)

for i, s in enumerate(S):
    if s == "0":
        mod_sum = (mod_sum1 + pow(2, N - i - 1, p1)) % p1
        #print(mod_sum)
        print(cnt[mod_sum] + 1)
    else:
        if pop_S == 1:
            print(0)
        else:
            mod_sum = (mod_sum2 - pow(2, N - i - 1, p2)) % p2
            #print(mod_sum)
            print(cnt[mod_sum] + 1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()
    cnt_init = X.count("1")
    x = int(X, 2)
    a = x % (cnt_init + 1)
    if cnt_init - 1 != 0:
        b = x % (cnt_init - 1)

    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            y = (a + pow(2, n - i - 1, cnt)) % cnt
        else:
            cnt = cnt_init - 1
            if cnt == 0:
                print(0)
                continue
            y = (b - pow(2, n - i - 1, cnt)) % cnt

        res = 1
        while y:
            cnt = bin(y).count("1")
            y %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N=int(input())
X=input()
def popcount(n):
    s=str(bin(n))
    return len([i for i in s if i=='1'])
def f(n):
    c=1
    while n!=0:
        n=n%popcount(n)
        c=c+1
    return c
x=int(X,2)
P=popcount(x)
F=list(X)
L=[1,2]# L[i]=2**i%(P+1)
M=[1,2]# M[i]=2**i%(P-1)
if P!=1:
    for i in range(1,N):
        L.append((L[i]*2)%(P+1))
        M.append((M[i]*2)%(P-1))
    s=x%(P+1)
    t=x%(P-1)
    for i in range(N):
        if F[i] == '1':
            q = (t - M[N-i-1])%(P-1)
            print(f(q))
        else:
            Q = P + 1
            q = (s + L[N-i-1])%(P+1)
            print(f(q))
else:
    for i in range(1,N):
        L.append(0)
    s=x%2
    for i in range(N):
        if F[i] == '1':
            print(0)
        else:
            q = (s + L[N - i - 1])%2
            print(f(q))

Submission status: Accepted

Solution code:
def p(x):
  return bin(x).count('1')

def f(x):
  if x == 0:
    return 0
  return f(x%p(x)) + 1

N = int(input())
X = input()
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = (a + pow(2,N-i-1,cnt+1))%(cnt+1)
  else:
    if cnt == 1:
      print(0)
      continue
    k = (b-pow(2,N-i-1,cnt-1))%(cnt-1)
  print(f(k)+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


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


def solve():
    N = Scanner.int()
    S = Scanner.string()
    pc = sum([s == '1' for s in S])
    ans = [0 for _ in range(N)]
    for b in range(2):
        npc = pc
        if b == 0:
            npc += 1
        else:
            npc -= 1
        if npc <= 0:
            continue
        r0 = 0
        for i in range(N):
            r0 = ((r0 * 2) + int(S[i])) % npc
        k = 1
        for i in reversed(range(N)):
            if int(S[i]) == b:
                r = r0
                if b == 0:
                    r = (r + k) % npc
                else:
                    r = (r - k + npc) % npc
                ans[i] = f(r) + 1
            k = (k * 2) % npc
    print(*ans, sep='\n')


def main():
    sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def p(x):
  return bin(x).count('1')

def f(x):
  if x == 0:
    return 0
  return f(x%p(x)) + 1

N = int(input())
X = input()
cnt = X.count('1')
x = int(X,2)
a = x % (cnt + 1)
if cnt != 1:
  b = x % (cnt - 1)

for i in range(N):
  if X[i] == '0':
    k = a
    k += pow(2,N-i-1,cnt+1)
    k %= cnt+1
  else:
    if cnt == 1:
      print(0)
      continue
    k = b
    k -= pow(2,N-i-1,cnt-1) 
    k %= cnt-1  
  print(f(k)+1)

Submission status: Accepted

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

l = [int(i) for i in s2]
p = sum(l)
s10 = int(s2,2)
if p == 1:
    ans1 = s10%(p+1)
    l1 = [0]*(n+1)
    l1[0] = 1
    for i in range(1,n+1):
        l1[i] = (l1[i-1]*2)%(p+1)
    for i in range(n):
        if l[i]:
            print(0)
        else:
            first = (ans1 + l1[n-i-1])%(p+1)
            ans = 1
            while first:
                mod = 0
                for j in range(len(bin(first))-2):
                    mod += first >> j & 1
                first %= mod
                ans += 1
            print(ans)
    quit()
if p == 0:
    for i in range(n):
        print(1)
    quit()

ans1 = s10%(p+1)
ans2 = s10%(p-1)
l1 = [0]*(n+1)
l2 = [0]*(n+1)
l1[0] = 1
l2[0] = 1
for i in range(1,n+1):
    l1[i] = (l1[i-1]*2)%(p+1)
    l2[i] = (l2[i-1]*2)%(p-1)
first = []
for i in range(n):
    if l[i]:
        first.append((ans2-l2[n-i-1])%(p-1))
    else:
        first.append((ans1+l1[n-i-1])%(p+1))


for i in range(n):
    if first[i] == 0:
        print(1)
        continue
    x = first[i]
    ans = 1
    while x:
        mod = 0
        for j in range(len(bin(x))-2):
            mod += x >> j & 1
        x = x%mod
        ans += 1
    print(ans)

Submission status: Accepted

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


n=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

mod1=num%(cnt+1)
mod2=num%(cnt-1) if cnt-1!=0 else 0

for i in range(n):
    if x[i]=="0":
        ans=(mod1+pow(2,n-i-1,cnt+1))%(cnt+1)
    else:
        if cnt-1==0:
            print(0)
            continue
        else:
            ans=(mod2-pow(2,n-i-1,cnt-1))%(cnt-1)
    point=1
    while ans!=0:
        ans %=popcount(ans)
        point +=1
    print(point)

Submission status: Accepted

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

c = x.count('1')
cp = c+1
cn = c-1

rp = [0] * n
if cp > 1:
    rp[0] = 1
rn = [0] * n
if cn > 1:
    rn[0] = 1
for i in range(1, n):
    rp[i] = (rp[i-1] * 2) % cp
    if cn > 0:
        rn[i] = (rn[i-1] * 2) % cn

xp = 0
xn = 0
for i in range(n):
    xx = x[i]
    if xx == '1':
        xp = (xp + rp[n-i-1]) % cp
        if cn > 0:
            xn = (xn + rn[n-i-1]) % cn

for i in range(n):
    o = 1
    if x[i] == '1':
        if cn == 0:
            print(0)
            continue
        xx = (xn-rn[n-i-1]) % cn
    else:
        xx = (xp+rp[n-i-1]) % cp
    while xx > 0:
        cc = bin(xx)[2:].count('1')
        xx = xx % cc
        o += 1
    print(o)

Submission status: Accepted

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

if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()

# xをpopcountで割ったあまりに置き換える
def f(x):
  if x==0: return 0
  return 1 + f(x % bin(x).count("1"))

# 初回のpopcountでの割り方は、(C+1) or (C-1)
Y = val%(C+1)
if C-1 != 0:
  Z = val%(C-1)
else:
  Z = 0

for i in range(N):
  if X[i] == "1":
    if Z - 1 == 0:
      print(0)
      continue
    k = (Z - pow(2,N-i-1,C-1)) % (C-1)
  else:
    k = (Y + pow(2,N-i-1,C+1)) % (C+1)
  print(f(k)+1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    # 0除算よけ。
    if n == 1:
        if x[0] == '1':
            print(0)
        else:
            print(1)
        sys.exit()
    # xの10進数換算と１の数カウント。
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    # 2**i(mod 1の数)をケースごとに用意する。
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1)) # 必ず1になる。xcount1=0はありえない。
    for j1 in range(1, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    if xcount1 > 1:
        mod2minus[0] = 1
        for j1 in range(1, n):
            mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    # x(mod 1の数)をケースごとに用意する。
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = 0
    else:
        modx_minus = x10 % (xcount1 - 1)
    popcount = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    print(1)
                    continue
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                print(1)
                continue
        r = 1
        while x3:
            r += 1
            if popcount[x3] == 0:
                p = bin(x3).count('1')
                popcount[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % popcount[x3]
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# N = 10
# X = '1'*N
N = int(input())
X = input()
popcount_X = X.count('1')
X_ = int(X, 2)

X_mod_minus = X_%(popcount_X-1) if popcount_X > 1 else -1
X_mod_plus = X_%(popcount_X+1)
for i in range(N):
    if X[i] == '0':
        popcount = popcount_X+1
        X_i = (X_mod_plus + pow(2, N-i-1, popcount))%(popcount)
    else:
        if X_mod_minus == -1:
            print(0)
            continue
        popcount = popcount_X-1
        X_i = (X_mod_minus - pow(2, N-i-1, popcount))%(popcount)
    ans = 1
    while X_i > 0:
        X_i %= bin(X_i).count('1')
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
int_s = [int(i) for i in s]
pc = s.count('1')

def f(x):
    bi = bin(x)
    pc = bi.count('1')
    cnt = 1
    while True:
        if x == 0:
            break
        x = x % pc
        bi = bin(x)
        pc = bi.count('1')
        cnt += 1
    return cnt

num_pl = 0
for i in range(n):
    num_pl = (num_pl*2) % (pc+1)
    num_pl += int_s[i]

num_mi = 0
for i in range(n):
    if pc-1 <= 0:
        continue
    num_mi = (num_mi*2) % (pc-1)
    num_mi += int_s[i]

ans = [0]*n
pc_pl, pc_mi = pc+1, pc-1
r_pl, r_mi = 1, 1
for i in range(n-1, -1, -1):
    if int_s[i] == 0:
        num = num_pl
        num = (num+r_pl) % pc_pl
    else:
        num = num_mi
        if pc_mi <= 0:
            continue
        num = (num-r_mi+pc_mi) % pc_mi

    ans[i] = f(num)
    r_pl = (r_pl*2) % pc_pl
    if pc_mi <= 0:
        continue
    r_mi = (r_mi*2) % pc_mi
     
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def popcount(n):
    ret = 0
    while n > 0:
        ret += n & 1
        n >>= 1
    return ret

def f(n):
    ret = 0
    while n > 0:
        n %= popcount(n)
        ret += 1
    return ret

def mod(x, d):
    '''
    x % d where x: string, d: int
    '''
    rem = 0
    for i in range(len(x)):
        divd = (rem << 1) + int(x[i], 2)
        rem = divd % d

    return rem

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

popx = X.count('1')
qp = mod(X, popx + 1)  # X mod (popcount(X) + 1)
if popx - 1 > 0:
    qm = mod(X, popx - 1)   # X mod (popcount(X) - 1)

ans = []
pow2p = pow2m = 1
for i in range(N):
    if X[N - 1 - i] == '1':
        if popx == 1: # X_iが0
            ans.append(0)
        else:
            next = (qm - pow2m) % (popx - 1)
            ans.append(1 + f(next))
    else:  #  X[N - 1 - i] == '0'
        next = (qp + pow2p) % (popx + 1)
        ans.append(1 + f(next))

    pow2p = pow2p * 2 % (popx + 1)
    if popx > 1:
        pow2m = pow2m * 2 % (popx - 1)

for i in range(N - 1, -1, -1):
    print(ans[i])

Submission status: Accepted

Solution code:
def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1) if (bit_count - 1) != 0 else 0

    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)

Submission status: Accepted

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

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) # 0->1に変化した際の、X0を割った余り
if count1 > 1:
  X0mod1to0 = X0 % (count1 - 1) # 1->0に変化した際の、X0を割った余り
else:
  X0mod1to0 = 0

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): # 愚直にf(x)を求める式
  if x in dp:
    return dp[x]
  pc = bin(x).count("1")
  val = f(x % pc) + 1
  dp[x] = val
  return val
  
val0to1 = 1
val1to0 = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): # 下の桁から順に、f(Xi)の値を求める
  if X[i] == "0": # 0を1に変える場合
    pat = (X0mod0to1 + val0to1 % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": # 1を0に変える場合
    if count1 > 1:
      pat = (X0mod1to0 - val1to0 % (count1 - 1)) % (count1 - 1)
      ans[i] = f(pat) + 1
    else:
      ans[i] = 0
  val0to1 = val0to1 * 2 % (count1 + 1)
  if count1 != 1:
    val1to0 = val1to0 * 2 % (count1 - 1)

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

Submission status: Accepted

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

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

num = int(s, 2) # 元の2進数を数字に
opc = s.count('1') # 元の2進数のpopcount

# ±1したpopcountで余りを求めておく
if opc > 1:
    num1 = num % (opc - 1)
else:
    num1 = 0
num0 = num % (opc + 1)

for i in range(n):
    if s[i] == '1':
        if opc == 1:
            print(0)
            continue
        tmp = (num1 - pow(2, n - 1 - i, opc - 1)) % (opc - 1)
    else:
        tmp = (num0 + pow(2, n - 1 - i, opc + 1)) % (opc + 1)

    # binで2進数にしてpopcount求める
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count('1')
        ans += 1
    print(ans)