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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# import random
# N = random.randint(0, 2*100000)
# X = ""
# for i in range(N):
#     if random.random() < 0.5:
#         X += "0"
#     else:
#         X += "1"
# print(N, X)


N = INT()
X = input()

def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        if not bn == 1:
            modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sm
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sp
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

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

Submission status: Accepted

Solution code:
def f(n):
  c=0
  while n>0:
    n%=format(n, 'b').count('1')
    c+=1
  return c

N=int(input())
X=input()
nums=[0]+[f(i) for i in range(1, N+1)] #先にi<=Nについてf(i)を求めておく

a=0 #Xの0の数
b=0 #Xの1の数

for i in range(N):
  if X[i]=='0':
    a+=1
  else:
    b+=1

#s=X%(b+1), t=X%(b-1)にする
s=0
t=0
if b>1:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    t=(t+int(X[i])*pow(2, N-1-i, b-1))%(b-1)
else:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    
"""
(1) X[i]==0の時
Xiは0が(a-1)個、1が(b+1)個となる。ここでXiに対して操作を1度行った後の数tmpは
    tmp={X%(b+1)+2^(N-1-i)%(b+1)}%(b+1)
       ={s+pow(2, N-1, b+1)}%(b+1)
となる。
tmp<(b+1)<Nなので、f(tmp)は冒頭で求めたnums[tmp]が使える。
Xiは1回操作してtmpとなり、nums[tmp]回操作して0になるので、
f(Xi)=1+nums[tmp]
で求められる。

(2) X[i]==1の時
Xiは0が(a+1)個、1が(b-1)個となる。ここでXiに対して操作を1度行った後の数tmpは
    tmp={X%(b-1)+2^(N-1-i)%(b-1)}%(b-1)
       ={t+pow(2, N-1, b-1)}%(b-1)
となる。そのため上記と同様に、
f(Xi)=1+nums[tmp]
で求められる。

ただしb=1の場合には、b-1=0となってしまうため、この場合のみ場合分けする。
具体的にはb=1の場合でX[i]=1の時は、Xi=0なので、問答無用で0を出力する。
"""
if b==1:
  for i in range(N):
    if X[i]=='0':
      tmp=(s+pow(2, N-1-i, b+1))%(b+1)
      print(nums[tmp]+1)
    else:
      print(0)
  exit()

for i in range(N):
  if X[i]=='0':
    tmp=(s+pow(2, N-1-i, b+1))%(b+1)
    print(nums[tmp]+1)
  else:
    tmp=(t-pow(2, N-1-i, b-1))%(b-1)
    print(nums[tmp]+1)

Submission status: Accepted

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()
# t = 1
for i in range(n):
    mod = xc+1
    xu.append(pow(2, i, mod))
    # xu.append(t%mod)
    # t *= 2
    # t %= mod
# t = 1
flag = False
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
        flag = True
    else:
        xd.append(pow(2, i, mod))
        # xd.append(t%mod)
        # t *= 2
        # t %= mod
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]

# print(xu)
# print(xd)

for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        #print(tar)
        while tar != 0:
            b_tar = bin(tar)
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if flag:
            print(0)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            #print(tar)
            while tar != 0:
                b_tar = bin(tar)
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0)
        continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    X = readline().rstrip().decode('utf-8')
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')

    if oc - 1 != 0:
        mx = nx % (oc - 1)
        f = True
    else:
        f = False

    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif f:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0
            continue

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
from functools import lru_cache
@lru_cache(None)
def f(x):
  if x==0: return 0
  return f(x%bin(x).count('1'))+1
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    d=c-1
    if d<1: print(0)
    else: print(f((b-pow(2,n-i-1,d))%d)+1)
  else:
    d=c+1
    print(f((a+pow(2,n-i-1,d))%d)+1)

Submission status: Accepted

Solution code:
def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
memo = [None] * 300000
def do2(x):
    if memo[x] is not None:
        return memo[x]
    cnt = 0
    while x != 0:
        x = x % popcount(x)
        cnt += 1
    memo[x] = cnt
    return cnt

def do():
    ll = int(input())
    s = input()
    n = int(s, 2)

    x = n
    cnt = 0
    ss = bin(x)[2:]
    cnt += 1
    num1 = ss.count("1")
    num1m = num1 - 1
    num1p = num1 + 1
    rs = ss[::-1]
    res1m = 0
    res1p = 0
    for j in range(len(rs)):
        if rs[j] == "1":
            if num1m != 0 and num1m != -1:
                res1m += pow(2, j, num1m)
                res1m %= num1m
            res1p += pow(2, j, num1p)
            res1p %= num1p

    #print(res1m, res1p, num1m, num1p)
    for i in range(len(s)):
        #print("i", i)
        if s[i] == "1": # 0になるから
            #print("down")
            #print(res1m, pow(2, ll - i -1, num1m))
            if num1m == 0 or num1m == -1:
                print(0)
                continue
            x = res1m - pow(2, ll - i -1, num1m)
            x %= num1m
        elif s[i] == "0": # 1になるから
            #print("up")
            #print(res1p, pow(2, ll - i -1, num1p))
            x = res1p + pow(2, ll - i-1, num1p)
            x %= num1p

        if x == 0:
            print(1)
            continue
        print(do2(x) + 1)
do()

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    x = input()
    k = int(x,2)
    c = x.count('1')
    kp = k%(c+1)
    if c > 1:
        kn = k%(c-1)
    
    for i in range(n):
        cnt = 1
        if x[i] == '1':
            if c == 1:
                print(0)
                continue
            mod = c-1
            tmp = (kn - pow(2,n-i-1,mod))%mod
            while 1:
                if tmp == 0:
                    break
                tmp = tmp%format(tmp, 'b').count('1')
                cnt+=1
        else:
            mod = c+1
            tmp = (kp + pow(2,n-i-1,mod))%mod
            while 1:
                if tmp == 0:
                    break
                tmp = tmp%format(tmp, 'b').count('1')
                cnt+=1
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()
t = 1
for i in range(n):
    mod = xc+1
    xu.append(t%mod)
    t *= 2
    t %= mod
t = 1
flag = False
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
        flag = True
    else:
        xd.append(t%mod)
        t *= 2
        t %= mod
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]

# print(xu)
# print(xd)

for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        #print(tar)
        while tar != 0:
            b_tar = bin(tar)
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if flag:
            print(0)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            #print(tar)
            while tar != 0:
                b_tar = bin(tar)
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)

Submission status: Accepted

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

def popcount(n):
    bin_n = bin(n)[2:]
    count = 0
    for i in bin_n:
        count += int(i)
    return count

cnt = 0
for i in range(n):
    if x[i] == '1':
        cnt += 1

lst = [0 for i in range(n+1)]
for i in range(1, n+1):
    num = i%popcount(i)
    lst[i] = lst[num] + 1

plus = [0 for i in range(n)]
minus = [0 for i in range(n)]
plus[0] = 1
if cnt != 1:
    minus[0] = 1
for i in range(1, n):
    plus[i] = (plus[i-1]*2) % (cnt+1)
    if cnt != 1:
        minus[i] = (minus[i-1]*2) % (cnt-1)

origin = int(''.join(x), base=2)
amariplus = origin % (cnt+1)
if cnt != 1:
    amariminus = origin % (cnt-1)

for i in range(n):
    if x[i] == '0':
        amari = (amariplus + plus[n-i-1]) % (cnt+1)
        print(lst[amari] + 1)
    else:
        if cnt != 1:
            amari = (amariminus - minus[n-i-1]) % (cnt-1)
            print(lst[amari] + 1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    s = input()
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    @lru_cache(None)
    def r(n):
        if n==0:
            return 0
        bc=0
        for i in range(n.bit_length()):
            if n>>i&1:
                bc+=1
        return r(n%bc)+1

    mod=s.count("1")
    c1=0
    c2=0
    cur1=1%(mod+1)
    
    if mod>1:
        cur2=1%(mod-1)
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
                c2+=cur2
                c2%=(mod-1)

            cur1=cur1*2%(mod+1)
            cur2=cur2*2%(mod-1)
    else:
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
            cur1=cur1*2%(mod+1)



    for i in range(N):
        if s[i]=="1":
            f=-1
            cmod=mod-1
        else:
            f=1
            cmod=mod+1

        if cmod==0:
            print(0)
            continue
        
        if f==1:
            n=c1+pow(2,N-1-i,cmod)
            n%=cmod
        else:
            n=c2-pow(2,N-1-i,cmod)
            n%=cmod

        print(1+r(n))
    #printe(c1,c2)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    s = input()
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    def bin(x): return format(x, 'b')
    def bitcount(x): return bin(x).count("1")
    
    @lru_cache(None)
    def r(n):
        if n==0:
            return 0
        bc=bitcount(n)
        return r(n%bc)+1

    mod=s.count("1")
    c1=0
    c2=0
    cur1=1%(mod+1)
    
    if mod>1:
        cur2=1%(mod-1)
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
                c2+=cur2
                c2%=(mod-1)

            cur1=cur1*2%(mod+1)
            cur2=cur2*2%(mod-1)
    else:
        for i in range(N):
            if s[-1-i]=="1":
                c1+=cur1
                c1%=(mod+1)
            cur1=cur1*2%(mod+1)



    for i in range(N):
        if s[i]=="1":
            f=-1
            cmod=mod-1
        else:
            f=1
            cmod=mod+1

        if cmod==0:
            print(0)
            continue
        
        if f==1:
            n=c1+pow(2,N-1-i,cmod)
            n%=cmod
        else:
            n=c2-pow(2,N-1-i,cmod)
            n%=cmod

        print(1+r(n))
    #printe(c1,c2)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
X = input()
bin_X = int(X, 2)
cnt = 0
for i in X:
    if i == '1':
        cnt += 1


def bit_count(bits):
    cnt = 0
    while bits:
        bits = bits & (bits - 1)
        bits >> 1
        cnt += 1
    return cnt


def pop_counter(n):
    return n % bit_count(n)


ans = 0
xp = bin_X % (cnt + 1)
if cnt != 1:
    xm = bin_X % (cnt - 1)
else:
    xm = 0
for n, i in enumerate(X):
    if i == '0':
        tmp = xp + pow(2, N - n - 1, cnt + 1)
        tmp %= cnt + 1
    elif cnt != 1:
        tmp = xm - pow(2,N-n-1,cnt-1)
        tmp %= cnt -1
    else:
        print(0)
        continue
    ans = 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    dp = [INF] * (200005)
    dp[0] = 0
    for i in range(1, 200005):
        dp[i] = 1 + dp[i % bin(i).count('1')]

    n = int(input())
    X = input()
    p = X.count('1')

    if p == 0:
        ans = [1] * n
        print(*ans, sep = '\n')
        return

    if p == 1:
        idx = X.index('1')
        if idx < n - 1:
            ans = [1] * n
            ans[idx] = 0
            ans[n - 1] = 2
        else:
            ans = [2] * n
            ans[idx] = 0
        print(*ans, sep = '\n')
        return

    minus1, plus1 = 0, 0
    for c in X:
        minus1 = (minus1 * 2 + int(c)) % (p - 1)
        plus1 = (plus1 * 2 + int(c)) % (p + 1)

    ans = [None] * n
    for i, c in enumerate(X):
        if c == '0':
            ans[i] = 1 + dp[(plus1 + pow(2, n - 1 - i, p + 1)) % (p + 1)]
        else:
            ans[i] = 1 + dp[(minus1 - pow(2, n - 1 - i, p - 1)) % (p - 1)]
    print(*ans, sep = '\n')
resolve()

Submission status: Accepted

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

memo = [-1] * (n+10)
def calc(x):
    if(memo[x] != -1):
        return memo[x]
    if(x==0):
        return 0
    cnt = 0
    x2 = x
    while(x2 > 0):
        cnt += (x2&1)
        x2 //= 2
    next = x%cnt
    memo[x] = 1 + calc(next)
    return memo[x]

cnt0 = x.count('1')
if(cnt0 == 0):
    ans = [1] * n
    print('\n'.join(map(str,ans)))
    exit()
if(cnt0==1):
    ans = [0] * n
    for i in range(n):
        ans1 = 1 + ( x[-1] == '1')
        if(x[i]=='0'):
            if(i==n-1):
                ans[i] = 2
            else:
                ans[i] = ans1
        else:
            ans[i] = 0
    print('\n'.join(map(str,ans)))
    exit()

rem_p = [0] * n
rem_m = [0] * n
rem_p[0] = 1
rem_m[0] = 1%(cnt0-1)

for i in range(1,n):
    rem_p[i] = (2*rem_p[i-1])%(cnt0+1)
    rem_m[i] = (2*rem_m[i-1])%(cnt0-1)

x_p = 0
x_m = 0
for i in range(n):
    if(x[n-1-i] == '1'):
        x_p += rem_p[i]
        x_m += rem_m[i]
x_p %= (cnt0+1)
x_m %= (cnt0-1)

ans = [0] * n
for i in range(n):
    if(x[i]=='1'):
        first = (x_m - rem_m[n-1-i])%(cnt0-1)
        ans[i] = calc(first) + 1
    else:
        first = (x_p + rem_p[n-1-i])%(cnt0+1)
        ans[i] = calc(first) + 1

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

Submission status: Accepted

Solution code:
def f(n):
  c=0
  while n>0:
    n%=format(n, 'b').count('1')
    c+=1
  return c

N=int(input())
X=input()
nums=[0]+[f(i) for i in range(1, N+1)]

a=0
b=0
for i in range(N):
  if X[i]=='0':
    a+=1
  else:
    b+=1

s=0
t=0
if b>1:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    t=(t+int(X[i])*pow(2, N-1-i, b-1))%(b-1)
else:
  for i in range(N):
    s=(s+int(X[i])*pow(2, N-1-i, b+1))%(b+1)
    
if b==1:
  for i in range(N):
    if X[i]=='0':
      tmp=(s+pow(2, N-1-i, b+1))%(b+1)
      print(nums[tmp]+1)
    else:
      print(0)
  exit()

for i in range(N):
  if X[i]=='0':
    tmp=(s+pow(2, N-1-i, b+1))%(b+1)
    print(nums[tmp]+1)
  else:
    tmp=(t-pow(2, N-1-i, b-1))%(b-1)
    print(nums[tmp]+1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = sum(map(lambda x: x == '1',X))
    lowNumber = []
    for i in range(MOD + 1):
        anscur = i
        cnt = 1
        while anscur != 0:
            oneCount = bin(anscur).count('1')
            anscur %= oneCount
            cnt += 1
        lowNumber.append(cnt)
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            elif i != N-1:
                ans += '1'
            else:
                ans += '2'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * 200001
    POWEROFTWOM1 = [0] * 200001
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODP1 %= MODP1
            xMODM1 += POWEROFTWOM1[N - i - 1]
            xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        ans += str(lowNumber[anscur])
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Accepted

Solution code:
n = int(input())
x = input()
k = x.count("1")
s = int(x, 2)

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

if k != 1:
	k1 = s%(k-1)
	k2 = s%(k+1)
	for i in range(n):
		if x[i] == "0":
			print(ev((k2+pow(2, n-i-1, k+1)) % (k+1))+1)
		else:
			print(ev((k1-pow(2, n-i-1, k-1)) % (k-1))+1)
else:
	k2 = s%(k+1)
	for i in range(n):
		if x[i] == "0":
			print(ev((k2+pow(2, n-i-1, k+1)) % (k+1))+1)
		else:
			print(0)

Submission status: Accepted

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

def f(x):
    cnt=0
    while(x>0):
        x%=popcount(x)
        cnt+=1
    return cnt

n=int(input())
s=input()
d=s.count("1")
if d==0:
    for i in range(n):
        print(1)
elif d==1:
    if s[-1]=="1":
        for i in range(n-1):
            print(2)
        else:
            print(0)
    else:
        for i in range(n-1):
            if s[i]=="1":
                print(0)
            else:
                print(1)
        print(2)
else:
    ints=int(s,2)
    m=ints%(d-1)
    M=ints%(d+1)
    s=s[::-1]
    toaddm=-1
    toaddM=1
    res=[None for i in range(n)]
    for i in range(n):
        if s[i]=="1":
            res[i]=f((m+toaddm)%(d-1))+1
        else:
            res[i]=f((M+toaddM)%(d+1))+1
        toaddm*=2
        toaddm%=d-1
        toaddM*=2
        toaddM%=d+1
    for i in res[::-1]:
        print(i)

Submission status: Accepted

Solution code:
# n = 2*10**5
# X = "10"*10**5
n = int(input())
X = input()
c = 0
cnt = 0
for i,x in enumerate(X):
    c += (1<<(n-i-1))*int(x)
    cnt += int(x)

amari_cnt_p = c % (cnt+1)
if cnt != 1:
    amari_cnt_m = c % (cnt-1)

dp = []
for d in range(n):
    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (amari_cnt_m - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = -1
    dp.append(amari)

memo = [-1]*(2*10**5+10)
memo[0] = 1
def calc(n):
    if n == -1:
        return 0
    if n == 0:
        return 1
    if memo[n] != -1:
        return memo[n]
    cnt = 1
    while n > 0:
        c = bin(n).count("1")
        n %= c
        cnt += 1
    memo[n] = cnt
    return cnt

for d in dp:
    ans = calc(d)
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    # for i in range(1,20):
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = list(input())
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b_p*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m*=2
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b_p*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m*=2
            curr_2b_m%=(one_cnt-1)
 
 
    # print(ansl)
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n_ansl = [0]*(2*(10**5))
    for i in range(1,2*(10**5)):
    # for i in range(1,20):
        cnt = 0
        one_cnt = bin(i).count("1")
        rem = i
        while rem != 0:
            one_cnt = bin(rem).count("1")
            rem = rem%one_cnt   
            cnt += 1
        n_ansl[i] = cnt
 
    n = int(input())
    x = list(input())
    one_cnt = x.count('1')

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    curr_2b_p = 1
    curr_2b_m = 1
    curr_sum_p1 = 0
    curr_sum_m1 = 0
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            curr_sum_p1 += curr_2b_p
            curr_sum_m1 += curr_2b_m
            curr_sum_p1%=(one_cnt+1)
            if one_cnt > 1:
                curr_sum_m1%=(one_cnt-1)
        curr_2b_p*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m*=2
            curr_2b_m%=(one_cnt-1)
 
        
 
    curr_2b_p = 1
    curr_2b_m = 1
    ansl = [0]*(n)
    for i in range(n-1, -1, -1):
        if x[i] == '1':
            diff = (-1)*curr_2b_m
            if one_cnt > 1:
                ans = (curr_sum_m1 + diff)%(one_cnt-1)
                ansl[i] = n_ansl[ans]+1
            else:
                ansl[i] = 0
        else:
            diff = curr_2b_p
            ans = (curr_sum_p1 + diff)%(one_cnt+1)
            ansl[i] = (n_ansl[ans]+1)
        curr_2b_p*=2
        curr_2b_m*=2
        curr_2b_p%=(one_cnt+1)
        if one_cnt > 1:
            curr_2b_m%=(one_cnt-1)
 
 
    # print(ansl)
    for a in ansl:
        print(a)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = input()
pop = x.count("1")
lst1 = [1]
for i in range(n-1):
    lst1.append(lst1[-1] * 2 % (pop + 1))
lst1.reverse()
num1 = 0
for i in range(n):
    if x[i] == "1":
        num1 += lst1[i]
        num1 %= (pop + 1)
if pop == 1 or pop == 2:
    lst2 = [0] * n
else:
    lst2 = [1]
    for i in range(n-1):
        lst2.append(lst2[-1] * 2 % (pop - 1))
    lst2.reverse()
    num2 = 0
    for i in range(n):
        if x[i] == "1":
            num2 += lst2[i]
            num2 %= (pop - 1)
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        if pop == 1:
            print(0)
            continue
        elif pop == 2:
            print(1)
            continue
        else:
            num = num2 - lst2[i]
            num %= (pop - 1)
    else:
        num = num1 + lst1[i]
        num %= (pop + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)