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
input=sys.stdin.readline

def main():
    N=int(input())
    X=input().strip("\n")
    cnt=[0]*N
    for i in range(1,N):
        n=i
        while(n>0):
            pc=0
            for j in range(19):
                if (n>>j)&1==1:
                    pc+=1
            n%=pc
            cnt[i]+=1
    pc=X.count("1")
    if pc==0:
        for i in range(N):
            print(1)
        exit()

    rp=[0]*N
    rn=[0]*N
    for i in range(N):
        rp[i]=pow(2,i,pc+1)
        if pc!=1:
            rn[i]=pow(2,i,pc-1)
    rp=rp[::-1]
    rn=rn[::-1]
            
    Xrp=0
    Xrn=0
    for i in range(N):
        if X[i]=="1":
            Xrp=(Xrp+rp[i])%(pc+1)
            if pc!=1:
                Xrn=(Xrn+rn[i])%(pc-1)
            
    for i in range(N):
        if X[i]=="1":
            if pc==1:
                print(0)
                continue
            r=Xrn-rn[i]
            print(cnt[r%(pc-1)]+1)
        else:
            r=Xrp+rp[i]
            print(cnt[r%(pc+1)]+1)
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    cache={"0":0}
    def get_pc(s):
        pc = sum([c == '1' for c in s])
        return pc

    def modPC(s,pc=None):
        if pc==None:
            pc =get_pc(s)
        return int(s,2)%pc

    def f(s,cur=0):
        if s in cache:
            return cache[s]
        next_s = bin(modPC(s))[2:]
        ret = f(next_s,cur+1)+1
        cache[s]=ret
        return ret
    N=iRaw()
    Xs=sRaw()
    XPC = get_pc(Xs)
    XmodPC=None
    if XPC!=0:
        XmodPC = modPC(Xs,XPC)
    XmodPCP = modPC(Xs,XPC+1)
    XmodPCN = None
    if XPC>1:
        XmodPCN= modPC(Xs,XPC-1)

    for n in range(N):
        if Xs[n]=='1':
            if XPC==1:
                print(0)
            else:
                nxt=(XmodPCN-pow(2,N-n-1,XPC-1))%(XPC-1)
                nxt = bin(nxt)[2:]
                print(f(nxt)+1)
        else:
            nxt = (XmodPCP+pow(2, N-n-1, XPC+1)) % (XPC+1)
            nxt = bin(nxt)[2:]
            print(f(nxt)+1)

main()

Submission status: Accepted

Solution code:
import sys 

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

pc = X.count("1")
# print("pc", pc)

# popcountはpcの+-1にしかならないので計算可能
mod_sum = {pc-1:0, pc+1:0}
# real_v = 0
for i in range(N):
    for this_pc in (pc-1, pc+1):
        if this_pc == 0:
            mod_sum[this_pc] = 0
            break
        if X[i] == "1":
            mod_sum[this_pc] += pow(2, N-i-1, this_pc)
            mod_sum[this_pc] %= this_pc
            # real_v += pow(2, N-i-1)
# print("real_v", real_v, "bin to int", int(X, 2))

for i in range(N):
    tmp_pc = pc
    if X[i] == "0":
        tmp_pc += 1
    else:
        tmp_pc -= 1
    if tmp_pc == 0:
        print(0)
        continue

    if X[i] == "0":
        tmp_mod_sum = mod_sum[tmp_pc] + pow(2, N-i-1, tmp_pc)
        tmp_mod_sum %= tmp_pc
    else:
        tmp_mod_sum = mod_sum[tmp_pc] - pow(2, N-i-1, tmp_pc)
        tmp_mod_sum %= tmp_pc

    count = 1
    tmp_sum = tmp_mod_sum
    # print(bin(tmp_sum))
    # print("tmp_sum", tmp_sum, "tmp_pc", tmp_pc)
    while tmp_sum > 0:
        tmp_x = str(bin(tmp_sum))
        tmp_pc = tmp_x.count("1")
        count += 1
        if tmp_pc == 0:
            break
        tmp_sum = tmp_sum % tmp_pc
        # print("tmp_sum", tmp_sum)
    print(count)

Submission status: Accepted

Solution code:
N = int(input())
X = ["0"] + list(input())


def popcount(x):
    c = 0
    while x > 0:
        if x % 2 == 1:
            c += 1
        x //= 2
    return c


def count(x):
    c = 0
    while x > 0:
        p = popcount(x)
        x %= p
        c += 1
    return c


p0 = X.count("1")
Xp, Xm = 0, 0  # X mod p0+1, X mod p0-1
for i in range(1, N + 1):
    if X[i] == "1":
        Xp += pow(2, N - i, p0 + 1)
Xp %= p0 + 1
if p0 > 1:
    for i in range(1, N + 1):
        if X[i] == "1":
            Xm += pow(2, N - i, p0 - 1)
    Xm %= p0 - 1
else:
    Xm = 0

for i in range(1, N+1):
    if X[i] == "1":
        p1 = p0 - 1
        if p1 == 0:
            print(0)
        else:
            x = (Xm + p1 - pow(2, N-i, p1)) % p1
            print(count(x)+1)
    else:
        p1 = p0 + 1
        x = (Xp + pow(2, N-i, p1)) % p1
        print(count(x)+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    N = int(input())
    S = input()
    D = defaultdict(bool)
    cnt = 0
    all1 = 0
    all2 = 0
    for i in range(N):
        if S[i] == "1":
            D[i] = True
            cnt += 1
        else:
            D[i] == False

    for i in range(N):
        if S[i] == "1":
            all1 += pow(2, N-1-i, cnt+1)
            if cnt != 1:
                all2 += pow(2, N-1-i, cnt-1)

    for i in range(N):
        P = 0
        if S[i] == "1":
            if cnt == 1:
                print(0)
                continue
            else:
                P += all2-pow(2, N-1-i, cnt-1)
            ans = 1
            P = P % (cnt-1)
            while P:
                c = P
                mod = 0
                while c:
                    mod += c & 1
                    c = c >> 1
                P = P % mod
                ans += 1
            print(ans)
            continue
        else:
            P += all1+pow(2, N-1-i, cnt+1)
            ans = 1
            P = P % (cnt+1)
            while P:
                c = P
                mod = 0
                while c:
                    mod += c & 1
                    c = c >> 1
                P = P % mod
                ans += 1
            print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    *X, = map(int, input())

    popcount = X.count(1)

    if popcount == 1:
        ans = []
        for i, d in enumerate(X):
            if d:  # 1 -> 0
                ans.append(0)  # 元々1つしかbitが立っておらず,そのbitを反転させる
                continue
            else:  # 0 -> 1
                if i == N - 1 or X[N - 1]:
                    ans.append(2)  # 奇数 -> 1 -> 0
                else:
                    ans.append(1)  # 偶数 -> 0

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

    def get_total(off: bool):
        """bit反転操作前のXを
        bit反転操作後のpopcountで割った剰余
        各桁のbit反転した整数は
        ここで求めたsに差分を加減すれば求まる
        """
        if off:  # 1 -> 0
            mod = popcount - 1
        else:  # 0 -> 1
            mod = popcount + 1

        s = 0
        for d in X:
            s = (s * 2 + d) % mod
        return s

    tot_off = get_total(off=True)
    tot_on = get_total(off=False)

    ans = []
    for i, d in enumerate(X):
        # popcount>1より少なくとも1回の操作が必要
        # %modが1回目の操作に対応
        if d:  # 1 -> 0
            mod = popcount - 1
            tot = (tot_off - pow(2, N - 1 - i, mod)) % mod
        else:  # 0 -> 1
            mod = popcount + 1
            tot = (tot_on + pow(2, N - 1 - i, mod)) % mod

        cnt = 1
        while tot:  # tot<=2*10**5, popcount(tot)<=18
            tot %= bin(tot)[2:].count('1')
            cnt += 1

        ans.append(cnt)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

num_of_1 = x.count("1")

x_num = int(x, 2)

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

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

a = x_num % (num_of_1 + 1)
b = x_num % (num_of_1 - 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((a + pow(2, n-i-1, num_of_1 + 1)) % (num_of_1 + 1)))
    else:
        print(1 + f((b - pow(2, n-i-1, num_of_1 - 1)) % (num_of_1 - 1)))

Submission status: Accepted

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

num_of_1 = x.count("1")

first = int(x, 2)

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

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((first_zero + pow(2, n-i-1, num_of_1 + 1)) % (num_of_1 + 1)))
    else:
        print(1 + f((first_one - pow(2, n-i-1, num_of_1 - 1)) % (num_of_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

N = INT()
X = input()

def bitcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)
    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def popcount(n):
    cnt = 0
    while n:
        n %= bitcount(n)
        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:
n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")
xc0 = x10 % (maxbit + 1)
xc1 = x10 % (maxbit - 1) if maxbit > 1 else 0

def f(ii):
  cnt = 0
  while ii > 0:
    ii %= bin(ii).count("1")
    cnt += 1
  return cnt

for i in range(lenx):
  if x[i] == "0":
    t = xc0 + pow(2, (lenx - 1 - i), maxbit + 1)
    ans = f(t % (maxbit + 1)) + 1
  else:
    if maxbit - 1 == 0:
      ans = 0
    else:
      t = xc1 - pow(2, (lenx - 1 - i), maxbit - 1)
      ans = f(t % (maxbit - 1)) + 1
  print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

pc = X.count("1")

# X == 0 の時
if pc == 0:
    for i in range(N):
        print(1)
    exit()

sml = pc - 1
big = pc + 1

b = 0
mod_s = 0
mod_b = 0
for x in X[::-1]:
    if x == "1":
        if sml:
            mod_s += pow(2, b, sml)
            mod_s %= sml

        mod_b += pow(2, b, big)
        mod_b %= big

    b += 1

# print(mod_s, mod_b, sml, big)


ELE = []

b = 0
for x in X[::-1]:
    if x == "0":
        t = (mod_b + pow(2, b, big)) % big
        ELE.append((t, 1))
    else:
        t = (mod_s - pow(2, b, sml)) % sml if sml else 0

        if sml:
            ELE.append((t, 1))
        else:
            ELE.append((0, 0))
    b += 1


def solve(x, c):
    if x == 0:
        return c

    b = 0
    nx = x
    while nx > 0:
        b += nx & 1
        nx >>= 1

    ret = solve(x % b, c + 1)
    return ret


ANS = []
for x, pc in ELE:
    ANS.append(solve(x, pc))

print("\n".join(map(str, ANS[::-1])))

Submission status: Accepted

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


def main():
    N = int(input())
    X = input()
    bit_num = X.count("1")

    X_minus = [0] * N # X_minus[i] = 2^i mod (bit_num - 1)
    X_plus = [0] * N # X_plus[i] = 2^i mod (bit_num + 1)
    X_minus[0], X_plus[0] = 1, 1
    for i in range(1, N):
        if bit_num != 1: X_minus[i] = (X_minus[i - 1] * 2) % (bit_num - 1)
        X_plus[i] = (X_plus[i - 1] * 2) % (bit_num + 1)
    #print("X_minus={}".format(X_minus))
    #print("X_plus={}".format(X_plus))

    rem_minus = 0
    rem_plus = 0
    for i in range(N):
        if X[N-i-1] == '1':
            if bit_num != 1: rem_minus = (rem_minus + X_minus[i]) % (bit_num - 1)
            rem_plus = (rem_plus + X_plus[i]) % (bit_num + 1)
    #print(rem_minus, rem_plus)

    for i in range(N):
        if X[i] == '0':
            bit = bit_num + 1
            n = (rem_plus + X_plus[-i-1]) % bit
        if X[i] == '1':
            bit = bit_num - 1
            if bit != 0: n = (rem_minus - X_minus[-i-1]) % bit
        if bit == 0 or bit == 1:
            print(bit)
            continue

        cnt = 1
        while n != 0:
            bit = bin(n).count("1")
            n %= bit
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp = [0] * (n+1)

for i in range(1,n+1):
    tmp = bin(i).count("1")
    dp[i] = dp[i%tmp] + 1

t = x.count('1')
po = []

for i in range(n):
    t1 = t
    if x[i] == '1':
        t1 -= 1
    else:
        t1 += 1
    po.append(t1)

t21 = 0
t22 = 0

for i in range(n):
    if x[i] == '1':
        if t > 1:
            t21 += pow(2, (n-i-1), t-1)
            t22 += pow(2, (n-i-1), t+1)
            t21 %= t-1
            t22 %= t+1
        else:
            t22 += pow(2, (n-i-1), t+1)
            t22 %= t+1

for i in range(n):
    if x[i] == '1':
        t3 = t21
    else:
        t3 = t22
    if po[i] == 0:
        print(0)
    else:
        if x[i] == '1':

            t3 -= pow(2, (n-i-1), po[i])
        else:
            t3 += pow(2,(n-i-1), po[i])
        print(dp[t3%po[i]]+1)

Submission status: Accepted

Solution code:
"""
NTC here
"""


#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

profile = 0
pypy = 1


def iin(): return int(input())


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



def main():
    T = 1
    while T:
        T -= 1
        n = iin()
        a = list(map(int, list(input())))
        ans = []
        def calc(a, md):
            ch = len(a)-1
            rm = 0
            for i in a:
                if i:
                    rm = (rm+ pow(2, ch, md))%md
                ch -= 1
            return rm%md
        
        def bin_calc(a):
            ans = []
            while a:
                ans.append(a&1)
                a >>= 1
            return ans[::-1]
        sm = sum(a)
        dc = {}
        if sm:
            dc[sm] = calc(a, sm)
        if sm-1>0:
            dc[sm-1] = calc(a, sm-1)
        dc[sm+1] = calc(a, sm+1)
        # count = 0
        for i in range(n):
            sol = 0
            s1 = sm - a[i]
            a[i] = + (not a[i])
            s1 += a[i]
            if s1:
                r1 = dc[s1]
                if a[i]:
                    r1 = (r1 + pow(2, n-i-1, s1))%s1
                else:
                    r1 = (r1 - pow(2, n-i-1, s1))%s1
                sol += 1
                a1 = bin_calc(r1)
                s1 = sum(a1)
                while s1:
                    # count += 1
                    # print(a1, s1)
                    sol += 1
                    rm = calc(a1, s1)
                    
                    if rm:
                        a1 = bin_calc(rm)
                        s1 = sum(a1)
                    else:
                        break
            a[i] = + (not a[i])
            ans.append(sol)
        print(*ans, sep='\n')





    
        










    




                

        

 
 
 
 
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
if pypy:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    if profile:
        import cProfile
        cProfile.run('main()')
    else:
        main()

Submission status: Accepted

Solution code:
#%%timeit
N = int(input())
X_str = input()

X = int(X_str, 2)

popcount_cache = [0, 1] + [-1] * 3 * 10 ** 5
for x in range(2, 200000+2):
  popcount_cache[x] =  popcount_cache[x // 2] + x % 2

# def popcount(x):
#   global popcount_cache
#   if popcount_cache[x] < 0:
#     # tmp = x
#     # p = 0
#     # while tmp not in popcount_cache:
#     #   p += tmp % 2
#     #   tmp //= 2
#     popcount_cache[x] = popcount(x // 2) + x % 2
#   return popcount_cache[x]

count_cache = [0, 1] + [-1] * 3 * 10 ** 5
for x in range(2, 200000+2):
  count_cache[x] = 1 + count_cache[x % popcount_cache[x]]


# def count(x):
#   #print('count', x)
#   global count_cache
#   if count_cache[x] < 0:
#     #print('count', x, popcount(x), x % popcount(x))
#     count_cache[x] = 1 + count(x % popcount[x])
#   return count_cache[x]
  
popcount_N = 0
for s in X_str:
  if s == '1':
    popcount_N += 1

def safemod(x, n):
  if n <= 0:
    return 0
  return x % n

Xmodpp = safemod(X, (popcount_N + 1))
Xmodpn = safemod(X, (popcount_N - 1))

ans = []
for i in range(N):
  if i == 0:
    modpp = 1
    modpn = 1
  else:
    modpp = safemod((modpp * 2) , (popcount_N+1))
    modpn = safemod((modpn * 2) , (popcount_N-1))
  if X_str[N - 1 - i] == '0':
    ans.append(count_cache[  safemod((Xmodpp + modpp), (popcount_N + 1))] + 1)
  else:
    if popcount_N == 1:
      ans.append(0)
    else:
      ans.append(count_cache[  safemod((Xmodpn - modpn), (popcount_N - 1))] + 1)

ans.reverse()
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
N = int(input())
X = input()
tmp = bin(int(X, 2)).count("1")
big = int(X, 2) % (tmp + 1)
small = int(X, 2) % (tmp - 1) if tmp - 1 else 0

for i in range(N):
    ans = 0
    if X[i] == '1':
        if not tmp - 1:
            print(ans)
            continue

        c = small - pow(2, (N - i - 1), tmp - 1)
        c = c % (tmp - 1)
    else:
        c = big + pow(2, (N - i - 1), tmp + 1)
        c = c % (tmp + 1)
    ans += 1
    while c:
        MOD = bin(int(c)).count("1")
        c %= MOD
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import math
# from collections import defaultdict
import time
def steps(n,p):
  c = 0
  while n:
    c += 1
    n = n%p
    p = bin(n).count('1')
  return c

# n = 200000
# x = "1"*n
n = int(input())
x = input()
p = x.count('1')
ans = []
num = int(x,2)
if p==1:
  for i in range(n-1,-1,-1):
    if x[i]=='1':
      ans.append(0)
    else:
      if i==n-1 or x[n-1]=='1':
        ans.append(2)
      else:
        ans.append(1)
else:
  incs = 1
  decs = 1
  inc = num%(p+1)
  dec = num%(p-1)
  start = time.time()
  k = -1
  for i in range(n-1,-1,-1):
    cp = p
    if x[i] == '0':
      cp += 1
      new = (inc+incs)%cp
    else:
      cp -= 1
      new = (dec-decs)%cp
    k -= 1
    incs = (incs*2)%(p+1)
    decs = (decs*2)%(p-1)
    sol = steps(new,cp)
    if sol==0:
      sol=1
    ans.append(sol)
    # steps(new,cp)
  # print(time.time()-start)
ans = ans[::-1]
for x in ans:
  print(x)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import itertools
import array
import textwrap
import math

N = int(input())
X = input()
temp = X.count("1")
t = [0, 0, 0]

t[0] = int(X, 2) % (temp-1) if temp != 1 else 0
t[2] = int(X, 2) % (temp+1)
cnt = 0
for i in range(N):
    if X[i] == "1" and temp == 1:
        print(0)
        continue
    if X[i] == "1":
        # p = (1 << (N-i-1)) % (temp-1)
        p = pow(2, N-1-i, temp-1)
        a = (t[0]-p) % (temp-1)
    elif X[i] == "0":
        # m = (1 << (N-i-1)) % (temp+1)
        m = pow(2, N-1-i, temp+1)
        a = (t[2]+m) % (temp+1)
    cnt = 1
    while a > 0:
        a = a % format(a, 'b').count("1")
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
X = input()
temp = X.count("1")
t = [0, 0, 0]

t[0] = int(X, 2) % (temp-1) if temp != 1 else 0
t[2] = int(X, 2) % (temp+1)
cnt = 0
for i in range(N):
    if X[i] == "1" and temp == 1:
        print(0)
        continue
    if X[i] == "1":
        # p = (1 << (N-i-1)) % (temp-1)
        p = pow(2, N-1-i, temp-1)
        a = (t[0]-p) % (temp-1)
    elif X[i] == "0":
        # m = (1 << (N-i-1)) % (temp+1)
        m = pow(2, N-1-i, temp+1)
        a = (t[2]+m) % (temp+1)
    cnt = 1
    while a > 0:
        a = a % format(a, 'b').count("1")
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
from typing import List, Tuple

N = int(input())
X = list(map(int, input()))


def binary_mod(bits: List[int], div: int) -> int:
    if div == 0:
        return 0

    val = 0
    for b in bits:
        val = (val * 2 + b) % div
    return val


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


popcount = sum(X)
div1 = popcount + 1
div2 = popcount - 1

if popcount == 0:
    print('\n'.join(map(str, [1] * N)))
else:
    rem1 = binary_mod(X, div1)
    rem2 = binary_mod(X, div2)

    for i in range(N):
        if X[i] == 0:
            r = (rem1 + pow(2, N - 1 - i, div1)) % div1
            print(f(r) + 1)
        else:
            if div2 > 0:
                r = (rem2 - pow(2, N - 1 - i, div2) + div2) % div2
                print(f(r) + 1)
            else:
                print(0)

Submission status: Accepted

Solution code:
def modpow(a, n, p):
  if n == 0:
    return 1
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p

l = [-1]*(2*10**5+1)
l[0] = 0
def f(n):
  if l[n] != -1:
    return l[n]
  else:
    b = bin(n)
    k = b.count("1")
    l[n] = f(n%k)+1
    return l[n]

 
  
  
n = int(input())
x = input()
#x = "1000101010"*20000
k = x.count("1")
x_mod_1 = int(x, 2) % (k+1)
x_mod_0 = int(x, 2) % (k-1) if k > 2 else 0
for i in range(n):
  if x[i] == "0":
    print(f((x_mod_1 + modpow(2, n-1-i, k+1))%(k+1))+1)

  else:
    if k > 2:
      print(f((x_mod_0 - modpow(2, n-1-i, k-1))%(k-1))+1)
    elif k > 1:
      print(1)
    else:
      print(0)

Submission status: Accepted

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

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

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

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

    print(lst[tmp]+1)

Submission status: Accepted

Solution code:
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

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):
  cnt = 0
  while n:
      cnt += 1
      n = n % bin(n).count('1')

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1) if base_cnt > 1 else 0

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

    if s == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()