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
from io import StringIO
import unittest

sys.setrecursionlimit(20000000)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    x=readline().rstrip()

    #pc=[0]*(10**5+1)
    #for i in range(1,10**5):
    #    pc[i]=count_ones_by_bin(i)
    amr1=[0]*((10**5)*2 + 5)
    amr2=[0]*((10**5)*2 + 5)
    bits=[False]*((10**5)*2 + 5)
    pc=[-1]*((10**5)*2 + 5)
    bcnt=0
    j=0
    for i in x:
        if int(i)==1:
            bcnt += 1
            bits[j]=True
        j+=1

    base1=0
    base2=0
    ni1=1
    ni2=1
    for j in range(n):
        i=n-1-j
        jo=n-i-1
        if j > 0:
            ni1*=2
            ni2*=2
        #amr1[i]=pow(2,jo,bcnt+1)
        ni1=ni1%(bcnt+1)
        amr1[i]=ni1
        if (bcnt-1)==0:
            amr2[i]=0 #pow(2,jo)
        else:
            #amr2[i]=pow(2,jo,bcnt-1)
            ni2=ni2%(bcnt-1)
            amr2[i]=ni2
        if bits[i]==True:
            base1+=amr1[i]
            base2+=amr2[i]
    for i in range(n):
        ans=0
        if bits[i]==True: #1->0
            if (bcnt-1)==0:
                base=0
            else:
                base=(base2-amr2[i])%(bcnt-1)
                ans+=1
        else:
            base=(base1+amr1[i])%(bcnt+1)
            ans+=1
        
        while base > 0:
            if pc[base]==-1:
                pc[base]=count_ones_by_bin(base)
            base=base%pc[base]
            ans+=1
        print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math

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

def num_to_X(num):
    new_X = []
    new_N = int(math.log(num,2))+1
    for i in range(new_N):
        new_X.append(num>>i&1)
    return new_X[::-1]

def X_to_num(X):
    value = 0
    X = X[::-1]
    for i in range(len(X)):
        value += X[i]*pow(2,i)
    return value

def mode(X, mod):
    X = X[::-1]
    next_X = 0
    mod_2_i = 1
    for i in range(len(X)):
        next_X = (next_X+(X[i]*mod_2_i))%mod
        mod_2_i = (mod_2_i*2)%mod
    return next_X

def f(N, X, k):
    mod = sum(X)
    next_X = mode(X,mod)
    if next_X == 0:
        return k+1
    else:
        new_X = num_to_X(next_X)
        return f(len(new_X), new_X, k+1)

base_mod = sum(X)
# base_modが1なら, 操作は0回.
if base_mod == 1:
    for i in range(N):
        # 100 -> 000
        if X[i] == 1:
            print(0)
        # 100 -> 110
        elif i != N-1:
            print(1)
        # 100 -> 101
        else:
            print(2)
    exit(0)

plus_amari = mode(X, base_mod+1)
# print(X_to_num(X), base_mod+1, X_to_num(X)%(base_mod+1), plus_amari)
minus_amari = mode(X, base_mod-1)
# print(X_to_num(X), base_mod-1, X_to_num(X)%(base_mod-1), minus_amari)

results = []
modplus_2_i = 1
modminus_2_i = 1
X_hanten = X[::-1]

# print('----')
# print(X)
# print('----')

for i in range(N):
    # modが増えるパターン
    if X_hanten[i] == 0:
#         now_num = X_to_num(X)+pow(2,i)
#         now_mod = base_mod+1
        amari = (plus_amari+modplus_2_i)%(base_mod+1)
    else:
#         now_num = X_to_num(X)-pow(2,i)
#         now_mod = base_mod-1
        amari = (minus_amari-modminus_2_i)%(base_mod-1)
#     print(now_num, now_mod, now_num%now_mod,amari)

    if amari != 0:
        new_X = num_to_X(amari)
        results.append(f(len(new_X),new_X,1))
    else:
        results.append(1)

    modplus_2_i = (modplus_2_i*2)%(base_mod+1)
    modminus_2_i = (modminus_2_i*2)%(base_mod-1)

# print('---')
for result in results[::-1]:
    print(result)

Submission status: Accepted

Solution code:
N = int(input())
X = list(input())
one = X.count('1')
L1 = [1]
L2 = [1]

for _ in range(N-1):
    if one - 1 == 0:
        L1.append(0)
    else:
        L1.append((L1[-1] * 2) % (one - 1))
    L2.append((L2[-1] * 2) % (one + 1))

x1 = 0
x2 = 0
power1 = 1
power2 = 1

for i in range(N):
    if X[N-i-1] == '1':
        if one - 1 != 0:
            x1 += power1
        x2 += power2
    power1 *= 2
    power2 *= 2
    if one - 1 != 0:
        power1 %= one - 1
    power2 %= one + 1

def solve(X, cnt):
    if X == 0:
        return cnt
    
    X %= bin(X).count('1')
    return solve(X, cnt+1)

for i in range(N):
    if X[i] == '0':
        tmp = (x2 + L2[N-i-1]) % (one + 1)
        ans = solve(tmp, 0) + 1
    else:
        if one - 1 == 0:
            ans = 0
        else:
            tmp = (x1 - L1[N-i-1]) % (one - 1)
            ans = solve(tmp, 0) + 1
    print(ans)

Submission status: Accepted

Solution code:
def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


def calc(val, my_dict, cnt):
    num_one = bin(val).count('1')
    if val in my_dict:
        return cnt + my_dict[val]
    else:
        if num_one == 0:
            return cnt
        nex = val % num_one
        ret = calc(nex, my_dict, cnt+1)
        my_dict[val] = ret - cnt
        return ret


n = int(input())
x = input()
tmp = list(x)
my_dict = dict()

num_one = tmp.count('1')
num_one_plus = num_one + 1
num_one_minus = num_one - 1

modsum_plus = 0
modsum_minus = 0
for i in range(1, n+1):
    if tmp[-i] == '1':
        modsum_plus += modpow(2, i-1, num_one_plus) % num_one_plus
        if num_one_minus != 0:
            modsum_minus += modpow(2, i-1, num_one_minus) % num_one_minus

for i in range(n):
    if num_one == 1 and tmp[i] == '1':
        print(0)
        continue
    if tmp[i] == '0':
        val = (modsum_plus + modpow(2, n-i-1, num_one_plus)) % num_one_plus
    else:
        if num_one_minus != 0:
            val = (modsum_minus - modpow(2, n-i-1, num_one_minus)) % num_one_minus
        else:
            val = 0
    if val != 0:
        print(calc(val, my_dict, 1))
    else:
        print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
X = list(input())
d = defaultdict(int)

for i in range(1, N):
    c = 0
    t = 0
    k = format(i, "b")
    for j in k:
        if j == "1":
            c += 1
    d[i] = d[i%c] + 1


n = 0
for i in X:
    if i == "1":
        n += 1

p1 = 1
p2 = 1
total1 = 0
total2 = 0
for i in X[::-1]:
    if i == "1":
        total1 += p1 % (n+1)
        if n-1 > 0:
            total2 += p2 % (n-1)
    p1 *= 2
    p1 %= n+1
    if n-1 > 0:
        p2 *= 2
        p2 %= n-1

total1 %= (n+1)
if n-1 > 0:
    total2 %= (n-1)
Ans = []
p1 = 1
p2 = 1
for i in X[::-1]:
    c = 1
    if n - 1 <= 0 and i == "1":
        Ans.append(0)
    else:
        if i == "0":
            start = total1
            start += p1
            start %= (n+1)
        else:
            start = total2
            start -= p2
            start += n - 1
            start %= (n-1)
        Ans.append(c+d[start])
    p1 *= 2
    p1 %= n+1
    if n-1 > 0:
        p2 *= 2
        p2 %= n-1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache

import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    @lru_cache(maxsize=None)
    def f(y):
        c = bin(y).count('1')
        if c == 0:
            return 0
        r = y % c

        return 1 + f(r)

    C = X.count('1')
    cmr = 0
    cpr = 0
    for b in X:
        cmr *= 2
        cmr += int(b)
        if C-1 == 0:
            cmr = 0
        else:
            cmr %= C - 1
        cpr *= 2
        cpr += int(b)
        cpr %= C + 1

    bp = 1
    bm = 1

    ans = []
    for i in range(N-1, -1, -1):
        t = 1
        if X[i] == '0':
            x = (cpr + bp) % (C+1)
        else:
            if C-1 == 0:
                x = 0
                t = 0
            else:
                x = (cmr - bm) % (C-1)
        while True:
            c = bin(x).count('1')
            # print(x, c)
            if c == 0:
                break
            x = x % c
            t += 1
        ans.append(t)

        bp *= 2
        bp %= (C+1)
        if C - 1 != 0:
            bm *= 2
            bm %= (C-1)

    for a in reversed(ans):
        print(a)


def main():
    N = read_int()
    X = read_str()
    slv(N, X)

    # import random
    # N = 10**5
    # N *= 2
    # X = ''.join(random.choices('01', k=N))
    # print(slv(N, X))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    if p > 1:
        kp0 = k % (p - 1)
    kp1 = k % (p + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(kp0 - pow(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp1 + pow(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def powmod(x, n, k):
    if k == 0:
        return 1

    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x
            ans %= k
        x = x*x
        x %= k
        n = n >> 1
    return ans % k

def popcnt(n):
    return bin(n).count("1")

def main():
    N = I()
    X = S()
    cnt = 0
    for i in range(len(X)):
        if int(X[i]) & 1  == 1:
            cnt += 1
    a = cnt + 1
    b = cnt - 1

    pow2a = [0] * (N+2)
    pow2b = [0] * (N+2) # 2 ^ i mod b

    suma = 0
    sumb = 0
    dX = X[::-1]
    for i in range(N+1):
        pow2a[i] = powmod(2, i, a)
        pow2b[i] = powmod(2, i, b)
        if i >= len(dX):
            continue
        if b == 0:
            sumb = 0
            continue
        if int(dX[i]) == 1:
            suma += pow2a[i]
            sumb += pow2b[i]
            suma %= a
            sumb %= b
    # rev
    X = X[::-1]
    # i=0 -> 2^(len(X) - i)
    # 0 ... len(X) - 1
    subx = []
    ans = [1] * N
    for i in range(len(X)):
        cp_suma = suma
        cp_sumb = sumb
        if int(X[i]) == 0:
            # 1にするので、加算してからaでわる
            # i = 0なら2^0 = 1のくらい
            cp_suma += pow2a[i]
            cp_suma %= a
            res = cp_suma
        else:
            # 0 にするので引き算してからbでわる
            if b == 0:
                ans[N-1-i] -= 1
                subx.append(0)
                continue
            cp_sumb -= pow2b[i]
            cp_sumb %= b
            res = cp_sumb
        subx.append(res)

    subx = subx[::-1]
    for i, a in enumerate(subx):
        while a > 0:
            a %= popcnt(a)
            ans[i] += 1
    for a in ans:
        print(a)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3

def ans(X):
    if X == 0: return 0
    X = X % (bin(X).count('1'))
    return 1+ans(X)

# test case injection
if False:
    import random
    X = ''.join(random.choice("1") for _ in range(2*10**5))
    N = len(X)
    # print(N, X)
    # exit(0)
else:
    N = int(input())
    X = input()

N = N-1

popcount = X.count('1')
X_int = int(X, 2)

import array

two_pow_mod_pc_plus = array.array('i', [0]*(N+1))
two_pow_mod_pc_minus = array.array('i', [0]*(N+1))

two_pow_mod_pc_plus[0] = 1 % (popcount+1)
if popcount <= 1:
    two_pow_mod_pc_minus[0] = 0
else:
    two_pow_mod_pc_minus[0] = 1 % (popcount-1)

for i in range(1, len(two_pow_mod_pc_plus)):
    two_pow_mod_pc_plus[i] = (2*two_pow_mod_pc_plus[i-1]) % (popcount+1)

for i in range(1, len(two_pow_mod_pc_minus)):
    if popcount <= 1:
        two_pow_mod_pc_minus[i] == 1
    else:
        two_pow_mod_pc_minus[i] = (2*two_pow_mod_pc_minus[i-1]) % (popcount-1)

X_mod_pc_plus = X_int % (popcount+1)
if popcount <= 1:
    X_mod_pc_minus = 0
else:
    X_mod_pc_minus = X_int % (popcount-1)

for i, x in enumerate(X):
    # if i % 1000 == 0: print(i)
    if x == '0':
        r = 1 + ans((X_mod_pc_plus + two_pow_mod_pc_plus[N-i]) % (popcount+1))
    else:
        if popcount == 1:
            print(0)
            continue
        else:
            r = 1 + ans((X_mod_pc_minus - two_pow_mod_pc_minus[N-i]) % (popcount-1))
    print(r)

Submission status: Accepted

Solution code:
from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    n1 = sum([int(i) for i in list(x)])
    if n1 > 1:
        sums = [n1 - 1, n1 + 1]
    else:
        sums = [None, n1 + 1]
    ns = len(sums)
    remainders = [[0] * n for _ in range(len(sums))]
    total_remainder = [0] * ns
    for i in range(ns):
        if sums[i] != None:
            remainders[i][0] = 1 % sums[i]
            if x[-1] == "1":
                total_remainder[i] = remainders[i][0]
            for j in range(1, n):
                remainders[i][j] = remainders[i][j-1] * 2 % sums[i]
                if x[-1-j] == "1":
                    total_remainder[i] = (total_remainder[i] +  remainders[i][j]) % sums[i]
                    #print("tr", i, total_remainder[1])
    for i in reversed(range(n)):
        if n1 == 1 and x[-1 -i] == "1":
            print(0)
            continue
        if x[-1 -i] == "1":
            rm = (total_remainder[0] - remainders[0][i]) % sums[0]
        else:
            rm = (total_remainder[1] + remainders[1][i]) % sums[1]
        if rm == 0:
            print(1)
            continue
        ans = 1
        while rm != 0:
            #print("rm", rm)
            rm = rm % countbin(rm)
            ans += 1
        print(ans)



    return

def countbin(num):
    return sum([int(i) for i in list(bin(num)[2:])])



n = RN()
x = RS()
solve()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

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


@njit((i8, ), cache=True)
def f(n):
    t = 0
    while n:
        t += 1
        n %= popcount(n)
    return t

@njit((i8[:], ), cache=True)
def main(X):
    N = len(X)
    popX = X.sum()
    MOD1 = popX + 1
    MOD2 = popX - 1
    if popX == 1:
        MOD2 = 1
    pow1 = np.ones_like(X)
    pow2 = np.ones_like(X)
    for n in range(1, N):
        pow1[n] = 2 * pow1[n - 1] % MOD1
        pow2[n] = 2 * pow2[n - 1] % MOD2

    X1, X2 = 0, 0
    for x in X:
        X1 = (2 * X1 + x) % MOD1
        X2 = (2 * X2 + x) % MOD2

    ans = np.empty(N, np.int64)
    for i in range(N):
        x = X[N - 1 - i]
        if x == 0:
            nxt = (X1 + pow1[i]) % (popX + 1)
            ans[i] = 1 + f(nxt)
        elif x == 1:
            if popX == 1:
                ans[i] = 0
            else:
                nxt = (X2 - pow2[i]) % (popX - 1)
                ans[i] = 1 + f(nxt)
    return ans[::-1]

N = int(readline())
X = np.array(list(read().rstrip()), np.int64) - ord('0')
ans = main(X)
print('\n'.join(map(str, ans.tolist())))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
Xs = list(map(int, list(input())))
rXs = Xs[::-1]

num = sum(Xs)
pos = 0
neg = 0

pow_pos = [0]*N
pow_neg = [0]*N
dic = {0: 0, 1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 2, 8: 1}

for m in range(1, num+2):
    c = bin(m)[2:].count('1')
    dic[m] = dic[m%c]+1
    
for i in range(N):
    pow_pos[i] = pow(2, i, num+1)
    if not num==1:
        pow_neg[i] = pow(2, i, num-1)

for i, x in enumerate(rXs):
    if x==0:
        continue
    pos += pow_pos[i]
    if not num==1:
        neg += pow_neg[i]

anss = []
for i, x in enumerate(rXs):
    if num==1 and x==1:
        anss.append(0)
        continue
    if x==0:
        mod = num+1
        tmp = (pos+pow_pos[i])%mod
    else:
        mod = num-1
        tmp = (neg-pow_neg[i])%mod
    ans = dic[tmp]+1
    anss.append(ans)

for ans in anss[::-1]:
    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
ST = input()
ST = ST[::-1]

# NUM1 =
# NUM2 =
popcnt = 0

for i in range(N):
    popcnt += ST[i] == '1'

NUM1 = 0
NUM2 = 0
pop_1 = popcnt-1
pop_2 = popcnt+1
for i in range(N):
    if ST[i] == '1':
        if pop_1 > 0:
            NUM1 += pow(2, i, pop_1)
            NUM1 %= pop_1
        if pop_2 <= N:
            NUM2 += pow(2, i, pop_2)
            NUM2 %= pop_2

# print(pop_1, pop_2)
# print(NUM1, NUM2)

for i in range(N):
    cnt = 1
    i = N-i-1
    if ST[i] == '1':
        # print("A")
        if pop_1 != 0:
            value = NUM1 - pow(2, i, pop_1)
            value %= pop_1
            while value:
                value %= bin(value).count("1")
                cnt += 1
            print(cnt)
        else:
            print(0)
    else:
        # print("B")
        value = NUM2 + pow(2, i, pop_2)
        value %= pop_2
        while value:
            value %= bin(value).count("1")
            cnt += 1
        print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
x = [int(x) for x in list(input())]

x_cnt = 0
for i, y in enumerate(x):
    if y == 1:
        x_cnt += 1

aa = x_cnt + 1
bb = x_cnt - 1

a = [1 % aa]
if bb > 0:
    b = [1 % bb]
else:
    bb = 1
    b = [0]

for _ in range(n-1):
    a.append(a[-1]*2 % aa)
    b.append(b[-1]*2 % bb)

a = a[::-1]
b = b[::-1]

x_ps = 0
x_ng = 0
for i, val in enumerate(x):
    if val == 1:
        x_ps += a[i]
        x_ng += b[i]

for i in range(n):
    ans = 0
    if x[i] == 0:
        cnt = x_cnt + 1
        val = (x_ps + a[i]) % cnt
    else:
        cnt = x_cnt - 1
        if cnt == 0:
            print(ans)
            continue
        val = (x_ng - b[i]) % cnt
    ans += 1

    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1) // 2
        else:
            tmp = tmp // 2

    if cnt == 0:
        print(ans)
        continue

    while val > 0:
        ans += 1
        val = val % cnt
        tmp = val % cnt
        cnt = 0
        while tmp > 0:
            if tmp & 1:
                cnt += 1
                tmp = (tmp-1) // 2
            else:
                tmp = tmp // 2
    print(ans)

Submission status: Accepted

Solution code:
memo = {}
def f(x):
    if x==0:
        return 0
    if x==1:
        return 1
    if x in memo:
        return memo[x]
    k = sum(list(map(int,list(bin(x)[2:]))))
    memo[x] = 1+f(x%k)
    return memo[x]
    
N = int(input())
X = input().strip()
n = sum(list(map(int,list(X))))
if n==0:
    for i in range(N):
        print(1)
elif n==1:
    D = {i:0 for i in range(N)} # mod n+1
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            print(0)
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))
else:
    C = {i:0 for i in range(N)}  # mod n-1
    C[0] = 1
    for i in range(1,N):
        C[i] = (C[i-1]*2)%(n-1)
    D = {i:0 for i in range(N)} # mod n+1
    D[0] = 1
    for i in range(1,N):
        D[i] = (D[i-1]*2)%(n+1)
    cnt0 = 0
    cnt1 = 0
    for i in range(N):
        if X[i]=="1":
            cnt0 = (cnt0+C[N-1-i])%(n-1)
            cnt1 = (cnt1+D[N-1-i])%(n+1)
    for i in range(N):
        if X[i]=="1":
            a = (cnt0-C[N-1-i])%(n-1)
            print(1+f(a))
        else:
            a = (cnt1+D[N-1-i])%(n+1)
            print(1+f(a))

Submission status: Accepted

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def l(): return list(sp())
def sp(): return map(int, data().split())


def calculate(string):
    result = 0
    while string:
        c = bin(string)[2:].count('1')
        string = string % c
        result += 1
    return result


n = int(data())
s = list(data())
ones = []
powers = []
for i in range(n):
    if s[i] == '1':
        ones.append(i)
length = len(ones)
powers = [[0, 0] for i in range(n)]
for i in range(n):
    if length - 1 > 0:
        powers[i][0] = pow(2, i, length-1)
    powers[i][1] = pow(2, i, length + 1)
powers = powers[::-1]
s1, s2 = 0, 0
for i in ones:
    if length - 1 > 0:
        s1 = (s1 + powers[i][0])
    s2 = (s2 + powers[i][1])
for i in range(n):
    if s[i] == '1':
        if length - 1 <= 0:
            out("0\n")
            continue
        temp = s1
        temp = (temp - powers[i][0] + length - 1) % (length - 1)
    else:
        temp = s2
        temp = (temp + powers[i][1]) % (length + 1)
    out(str(calculate(temp)+1)+"\n")

Submission status: Accepted

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

n = int(input())
x = input()
px = x.count("1")
a = px + 1
b = px - 1
tmpa = 0
tmpb = 0

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

    for i in range(1, n + 1):
        count = 1
        if x[i - 1] == "1":  # x[i] == "1" -> "0"
            print(0)
            continue

        else:  # x[i] == "0" -> "1"
            y = tmpa + pow(2, n - i, a)
            y %= a
        while y:
            y %= popcount(y)
            count += 1
        print(count)

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

    for i in range(1, n + 1):
        count = 1
        if x[i - 1] == "1":  # x[i] == "1" -> "0"
            y = tmpb - pow(2, n - i, b)
            y %= b
        else:  # x[i] == "0" -> "1"
            y = tmpa + pow(2, n - i, a)
            y %= a
        while y:
            y %= popcount(y)
            count += 1
        print(count)

Submission status: Accepted

Solution code:
n = int(input())
s = input()[::-1]
cnt = s.count('1')

p1 = sum(pow(2, i, cnt+1) * (s[i] == '1') for i in range(n))
if cnt > 1:
    m1 = sum(pow(2, i, cnt-1) * (s[i] == '1') for i in range(n))

def op(n):
    popcnt = bin(n).count('1')
    return n%popcnt

pre = [0]*1000000
for i in range(1,1000000):
    pre[i] = pre[op(i)] + 1

def solve(i):
    if s[-i] == '0':
        r = (p1 + pow(2, n-i, cnt+1))%(cnt+1)
    else:
        if cnt == 1:
            return 0
        r = (m1 - pow(2, n-i, cnt-1))%(cnt-1)
    return 1 + pre[r]

for i in range(n):
    print(solve(i+1))

Submission status: Accepted

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

def popcount(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

a = X.count("1")
ap, am = a+1, a-1
Flag = True

if am == 0:
  Flag = False
  am += 1

Ap = [1]
Am = [1]

for i in range(N-1):
  Ap.append(Ap[-1]*2%ap)
  Am.append(Am[-1]*2%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am 

for i in range(N):
  cnt = 1
  if X[i] == "1":
    if Flag:
      p = Ams - Am[-1-i]
      p %= am
    else:
      cnt -= 1
      p = 0
  else:
    p = Aps + Ap[-1-i]
    p %= ap
  temp = p
  while temp > 0:
    temp %= popcount(temp)
    cnt += 1
  print(cnt)

Submission status: Accepted

Solution code:

def resolve():
    import copy
    n = int(input())
    x = input()
    ones = x.count("1")
    dones = ones - 1
    iones = ones + 1

    def counter(n):
        ans = 0
        while n > 0:
            n = n % bin(n).count("1")
            ans  += 1
        return(ans)

    modd = 0

    modi = 0
    for i in reversed(range(n)):
        if x[i] == "1":
            if dones != 0:
                modd += pow(2,n-i-1,dones)
            modi += pow(2,n-i-1,iones)

    for i in range(n):
        ans = 0
        if x[i] == "0":
            w = (modi + pow(2,n-i-1, iones))%iones
            ans += 1
            print(ans + counter(w))

        else:
            if dones == 0:
                print(0)
                continue
            else:
                w = (modd-pow(2,n-i-1, dones) + dones)%dones
                ans += 1
                print(ans + counter(w))
resolve()

Submission status: Accepted

Solution code:
import collections
memo = collections.defaultdict(int)
memo[0] = 0
memo[1] = 1


def f(x):
    if x in memo:
        return memo[x]
    else:
        y = x % bin(x).count('1')
        ret = 1 + f(y)
        memo[x] = ret
        return ret


N = int(input())
sX = input()
modX = sX.count('1')
if modX == 0:
    for _ in range(N):
        print(1)
elif modX == 1:
    sX = sX[::-1]
    for i, b in enumerate(sX):
        if b == '1':
            break
    #print(i)
    if i == 0:
        ans = [0] + [2] * (N - 1)
        ans = ans[::-1]
    else:
        ans = [1] * N
        ans[-1] = 2
        ans[-i - 1] = 0
    print('\n'.join(map(str, ans)))
else:
    modp = modX + 1
    modm = modX - 1
    sX = sX[::-1]
    Xmodp = 0
    Xmodm = 0
    for i, b in enumerate(sX):
        if b == '1':
            Xmodp += pow(2, i, modp)
            Xmodp %= modp
            Xmodm += pow(2, i, modm)
            Xmodm %= modm
    s = []
    for i, b in enumerate(sX):
        if b == '1':
            s += [(Xmodm - pow(2, i, modm)) % modm]
        else:
            s += [(Xmodp + pow(2, i, modp)) % modp]
    ans = []
    for k in s[::-1]:
        ans += [1 + f(k)]
    print('\n'.join(map(str, ans)))