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

def f(n):
    if n == 0:
        return 0
    pc = 0
    k = n
    while k:
        pc += k & 1
        k >>= 1
    
    return 1 + f(n % pc)

def solve():
    N = int(readline())
    X = readline().rstrip()
    X = list(map(int, X))

    N1 = sum(X) - 1
    N0 = N1 + 2

#    if N1 == 0:
#        a = 0
#        for i in range(N):
#            a = (a * 2) % N0
#        
#        anses = [0] * N
#        b = 1
#        for i in range(N):
#
#        exit(0)

    a0 = 0
    a1 = 0
    for i in range(N):
        a0 = (a0 * 2 + X[i]) % N0
        a1 = (a1 * 2 + X[i]) % N1 if N1 != 0 else 0
    
    anses = [0] * N
    b0 = 1
    b1 = 1
    for i in range(N):
        if X[N - 1 - i] == 0:
            k = (a0 + b0) % N0
        else:
            k = (a1 - b1) % N1 if N1 != 0 else 0
        
        if N1 == 0 and X[N - 1 - i] == 1:
            anses[N - 1 - i] = 0
        else:
            anses[N - 1 - i] = 1 + f(k)

        b0 = b0 * 2 % N0
        b1 = b1 * 2 % N1 if N1 != 0 else 0

    for a in anses:
        print(a)

solve()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from collections import Counter
def func(x):
    cnt = 0
    y = x
    while x > 0:
        if x%2 == 1:
            cnt += 1
        x //= 2
    return y%cnt
        
def main():
    N = int( input())
    X = list( map( int, list( input())))
    base_plus = 0
    base_minus = 0
    r = 1
    one = Counter(X)[1]
    for x in X[::-1]:
        base_plus += r*x
        base_plus %= one+1
        r *= 2
        r %= one+1
    r = 1
    if one > 1:
        for x in X[::-1]:
            base_minus += r*x
            base_minus %= one-1
            r *= 2
            r %= one-1

    ANS = [0]*N
    # print(base)
    # print(bin(base))
    for i in range(N):
        if one == 1:
            if X[i] == 1:
                ANS[i] = 0
                continue
        if X[i] == 1:
            xi = (base_minus -  pow(2,N-1-i,one-1))%(one-1)
            # print(i, bin(base -  pow(2,N-1-i)), one-1)
        else:
            xi = (base_plus +  pow(2,N-1-i,one+1))%(one+1)
            # print(i, bin(base +  pow(2,N-1-i)), one+1)
        # print(i,xi)
        if xi == 0:
            ANS[i] = 1
            continue
        ans = 1
        while xi > 0:
            ans += 1
            xi = func(xi)
        ANS[i] = ans
    print("\n".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def bit_count(x):
    count = 0
    while x > 0:
        if x & 1:
            count += 1
        x = x >> 1
    return count


def get_ans(i):
    ans = 1
    if x[i] == '0':
        p_first = (sum_plus + p_plus[i]) % (p_origin+1)
    else:
        if p_origin-1 == 0:
            return 0
        p_first = (sum_minus - p_minus[i]) % (p_origin-1)
    while p_first != 0:
        p_first = p_first % bit_count(p_first)
        ans += 1
    return ans

p_minus = [0]*n # x%(p-1)
p_plus = [0]*n # x%(p+1)

t1 = 1
t2 = 1
for i in range(n):
    p_minus[n-1-i] = t1
    p_plus[n-1-i] = t2
    t1 *= 2
    t2 *= 2
    if p_origin == 1:
        t1 = 0
    else:
        t1 %= p_origin-1
    t2 %= p_origin+1

sum_plus = 0
sum_minus = 0
for i in range(n):
    if x[i] == '1':
        sum_plus += p_plus[i]
        sum_minus += p_minus[i]

for i in range(n):
    print(get_ans(i))

Submission status: Accepted

Solution code:
def count(n):
    k = n.bit_length()
    res = 0
    for i in range(k):
        if (n >> i) & 1:
            res += 1
    return res

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

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

#Xをp+1で割ったあまり
r1 = 0
for i in range(N):
    if X[~i] == '1':
        r1 += pow(2, i, p + 1)
        r1 %= p + 1

if p > 1:
    #Xをp-1で割ったあまり
    r2 = 0
    for i in range(N):
        if X[~i] == '1':
            r2 += pow(2, i, p - 1)
            r2 %= p - 1
else:
    r2 = -1

rem = [0 for _ in range(N)]

for i in range(N):
    if X[i] == '1': #p-1
        if r2 == -1:
            r = -1
        else:
            r = r2 - pow(2, N - 1 - i, p - 1)
            r %= p - 1
    else:
        r = r1 + pow(2, N - 1 - i, p + 1)
        r %= p + 1
    rem[i] = r

res = [0 for _ in range(N)]

for i in range(N):
    k = rem[i]
    if k == -1:
        res[i] = 0
    else:
        j = 1
        while k:
            k %= count(k)
            j += 1
        res[i] = j

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

Submission status: Accepted

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

n = int(input())
x = input()
mod = x.count("1")
U = 2**20
C = [0]*U
for i in range(1, U):
  q = popcount(i)
  C[i] = C[i%q] + 1
t_1 = 0
t_2 = 0
for j, s in enumerate(x):
  if s == "1":
    if mod > 1:
      t_1 += pow(2, n-1-j, mod-1)
      t_1 %= mod-1
    t_2 += pow(2, n-1-j, mod+1)
    t_2 %= mod+1
for i in range(n):
  if x[i] == "1":
    if mod == 1:
      print(0)
      continue
    temp = t_1
    temp -= pow(2, n-1-i, mod-1)
    temp %= mod-1
  else:
    temp = t_2
    temp += pow(2, n-1-i, mod+1)
    temp %= mod+1
  res = C[temp] + 1
  print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

n = n_in()
x = s_in()

popcnt = sum(i == '1' for i in x)

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

memo = {}

MOD = popcnt+1
memo[MOD] = []
for i in range(n):
    memo[MOD].append(mod_pow(2, i))
    

if popcnt-1 > 0:
    MOD = popcnt-1
    memo[MOD] = []
    for i in range(n):
        memo[MOD].append(mod_pow(2, i))

base_1 = 0
base_2 = 0
for i in range(n):
    if x[i] == '1':
        MOD = popcnt+1
        base_1 = mod_add(base_1, memo[MOD][n-i-1])

    
        if popcnt-1 > 0:
            MOD = popcnt-1
            base_2 = mod_add(base_2, memo[MOD][n-i-1])


for i in range(n):
    cnt = 0
    if x[i] == '0':        
        MOD = popcnt + 1
        current = mod_add(base_1, memo[MOD][n-i-1])
        cnt += 1
        while current > 0:
            MOD = sum(c=='1' for c in bin(current)[2:])
            current = current%MOD
            cnt += 1
    else:
        MOD = popcnt - 1
        if MOD == 0:
            print(0)
            continue
        current = mod_sub(base_2, memo[MOD][n-i-1])
        cnt += 1
        while current > 0:
            MOD = sum(c=='1' for c in bin(current)[2:])
            current = current%MOD
            cnt += 1

    print(cnt)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(readline())
X = readline().rstrip()
X = X[::-1]

C = X.count("1")

if C == 0:
    for i in range(N):
        print(1)
    exit()

if C == 1:
    # modC+1を求める
    Cp = [0]*(N+1)

    Cp[0] = 1
    for i in range(N):
        Cp[i+1] = Cp[i]*2%(C+1)
    sumcp = 0

    for i in range(N):
        if X[i] == "1":
            sumcp = (sumcp+Cp[i])%(C+1)


    # 1回操作を行うとmodC+1のときC以下、modC-1のときC-2以下になるのでそこまで前計算する

    List = [0]*(N+1)

    for i in range(1,N+1):
        # 立ってるbit数を数える
        cnt = 0
        for j in range(20):
            if i>>j&1:
                cnt += 1
        List[i] = List[i%cnt]+1

    ans = [0]*N

    for i in range(N):
        if X[i] == "1":# 0にするのでmodC-1
            ans[N-1-i] = 0
        else:# 0->1にするのでmodC+1
            a = (sumcp + Cp[i])%(C+1)
            ans[N-1-i] = List[a]+1
    for anss in ans:
        print(anss)

    exit()




# modC+1とmodC-1を求める
Cp = [0]*(N+1)
Cm = [0]*(N+1)

Cp[0] = 1
Cm[0] = 1

if C == 2:
    Cm[0] = 0

for i in range(N):
    Cp[i+1] = Cp[i]*2%(C+1)
    Cm[i+1] = Cm[i]*2%(C-1)
sumcp = 0
sumcm = 0

for i in range(N):
    if X[i] == "1":
        sumcp = (sumcp+Cp[i])%(C+1)
        sumcm = (sumcm+Cm[i])%(C-1)


# 1回操作を行うとmodC+1のときC以下、modC-1のときC-2以下になるのでそこまで前計算する

List = [0]*(N+1)

for i in range(1,N+1):
    # 立ってるbit数を数える
    cnt = 0
    for j in range(20):
        if i>>j&1:
            cnt += 1
    List[i] = List[i%cnt]+1

ans = [0]*N

for i in range(N):
    if X[i] == "1":# 0にするのでmodC-1
        a = (sumcm - Cm[i])%(C-1)
        ans[N-1-i] = List[a]+1
    else:# 0->1にするのでmodC+1
        a = (sumcp + Cp[i])%(C+1)
        ans[N-1-i] = List[a]+1
for anss in ans:
    print(anss)

Submission status: Accepted

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

l = [0] * (2*10**5+1)
ans = [0] * (2*10**5+1)
for i in range(2*10**5+1):
  l[i] = bin(i).count('1')
  
for i in range(2*10**5+1):
  x = i
  y = 0
  while x!=0:
    y += 1
    x %= l[x]
    
  ans[i] = y
  
X_count = X.count('1')
plu = X_count + 1
mi = X_count - 1
plu_res = 0
mi_res = 0
X_int = int(X,2)

for i in range(N):
  if X[i]=='0':
    continue
  else:
    plu_res += pow(2,N-i-1,plu)
    plu_res %= plu
    if mi>0:
      mi_res += pow(2,N-i-1,mi)
      mi_res %= mi
      
for i in range(N):
  if X[i]=='0':
    x = (plu_res + pow(2,N-i-1,plu)) % plu
    print(1 + ans[x])
  else:
    if mi!=0:
      x = (mi_res - pow(2,N-i-1,mi)) % mi
      print(1 + ans[x])
    else:
      print(0)

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int, input().strip()))

count_j = X.count(1)

def calc_table(m):
	if m == 1:
		return [0] * N
	elif m == 0:
		return None
	table = []
	x = 1
	for i in range(N):
		table.append(x)
		x = (x * 2) % m
	table.reverse()
	return table

count_m = count_j - 1
count_p = count_j + 1

mod_m = calc_table(count_m)
mod_j = calc_table(count_j)
mod_p = calc_table(count_p)

original_j = 0
original_m = 0
original_p = 0
if count_m > 0:
	for i, b in enumerate(X):
		if b == 1:
			original_j = (original_j + mod_j[i]) % count_j
			original_m = (original_m + mod_m[i]) % count_m
			original_p = (original_p + mod_p[i]) % count_p
else:
	for i, b in enumerate(X):
		if b == 1:
			original_j = (original_j + mod_j[i]) % count_j
			original_p = (original_p + mod_p[i]) % count_p
#print(mod_p)
#print(original_m, original_j, original_p)

f_cache = [None] * N
def calc_f(x):
	if x == 0:
		return 0
	f = f_cache[x]
	if f != None:
		return f
	count = 0
	i = x
	while i > 0:
		if i % 2 == 1:
			count += 1
		i //= 2
	f = calc_f(x % count) + 1
	f_cache[x] = f
	return f

for i, b in enumerate(X):
	if b == 0:
		x = (original_p + mod_p[i]) % count_p
		print(calc_f(x) + 1)
	else:
		if count_m > 0:
			x = (original_m - mod_m[i]) % count_m
			print(calc_f(x) + 1)
		else:
			print(0)

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:
N = int(input())
ans_list = [0] * (N+1)
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
for i in range(N):
    if i == 0:
        continue
    else:
        if i %popcnt(i) == 0 :
            ans_list[i] = 1
        else:
            ans_list[i] = ans_list[i%popcnt(i)] + 1
S = input()
count = 0
for i in range(N):
    if S[i] == "1":
        count += 1
if count == 1:
    high_total = 0
    low_total = 0
    for i in range(N):
        if S[i] == "1":
            high_total += pow(2,N-1-i,count+1)
            high_total %= (count+1)
    for i in range(N):
        if S[i] == "1":
            print(0)
        if S[i] == "0":
            total = (high_total + pow(2,N-1-i,count+1)) % (count+1)
            print(ans_list[total]+1)
else:
    high_total = 0
    low_total = 0
    for i in range(N):
        if S[i] == "1":
            high_total += pow(2,N-1-i,count+1)
            high_total %= (count+1)
            low_total +=  pow(2,N-1-i,count-1)
            low_total %= (count-1)
    for i in range(N):
        if S[i] == "1":
            total = (low_total - pow(2,N-1-i,count-1)) % (count-1)
            print(ans_list[total]+1)
        if S[i] == "0":
            total = (high_total + pow(2,N-1-i,count+1)) % (count+1)
            print(ans_list[total]+1)

Submission status: Accepted

Solution code:
import math

mod = 1000000007
dp = [0, 1]
num = [0, 1]
for i in range(2, 200000):
    if i % 2 == 0:
        num.append(num[i//2])
    else:
        num.append(num[i//2]+1)
    dp.append(dp[i % num[i]]+1)
N = int(input())
x = input()
ones = 0
for c in x:
    if c == '1':
        ones += 1
powlow = [1]
powhigh = [1]
modlow = ones - 1
modhigh = ones + 1
for i in range(200000):
    if modlow != 0:
        powlow.append((powlow[i]*2) % modlow)
    powhigh.append((powhigh[i]*2) % modhigh)
reslow = 0
reshigh = 0
for i in range(N):
    if x[i] == '1':
        if modlow != 0:
            reslow = (reslow + powlow[N - i - 1]) % modlow
        reshigh = (reshigh + powhigh[N - i - 1]) % modhigh
for i in range(N):
    if x[i] == '1':
        if modlow != 0:
            temp = (modlow + reslow - powlow[N - i - 1]) % modlow
            print(dp[temp] + 1)
        else:
            print(0)
    if x[i] == '0':
        temp = (reshigh + powhigh[N - i - 1]) % modhigh
        print(dp[temp] + 1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


n = int(input())
x = input()
nx = int(x, 2)
c = x.count("1")

numa = 0
numb = 0
p = 0
for i in reversed(range(len(x))):
    if x[i] == "1":
        if c > 1:
            numa += pow(2, p, c - 1)
        numb += pow(2, p, c + 1)
    p += 1

# print(c-1, c+1, numa, numb)

for i in range(n):
    if x[i] == "0":
        val = (numb + pow(2, n-i-1, c + 1)) % (c+1)
        # print(i, val)
        if val == 0:
            print(1)
            continue
        count = 1
        while val > 0:
            val = val % bin(val).count("1")
            count += 1
        print(count)
    else:
        if c == 1:
            print(0)
            continue
        val = (numa - pow(2, n - i - 1, c - 1)) % (c - 1)
        # print(i, val)
        if val == 0:
            print(1)
            continue
        count = 1
        while val > 0:
            val = val % bin(val).count("1")
            count += 1
        print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def divide(X, s):
    ans = 0
    for i in X:
        ans *= 2
        i = int(i)
        ans += i
        ans = ans % s
    return ans


def popcount(n):
    ans = 0
    while(n > 0):
        ans += n & 1
        n = n >> 1
    return ans


def count(n):
    cnt = 1
    while(n > 0):
        n = n % popcount(n)
        cnt += 1
    return cnt


N = ni()
X = ns()

cnt = X.count("1")

if cnt == 0:
    for i in range(N):
        print(1)
    exit()


cnt_plus = cnt + 1
cnt_minus = cnt - 1
p = 1
m = 1
p_array = []
if cnt_minus > 0:
    m_array = []
for i in range(N):
    p_array.append(p)
    p = p * 2 % cnt_plus
    if cnt_minus > 0:
        m_array.append(m)
        m = m * 2 % cnt_minus

plus_first = divide(X, cnt_plus)
if cnt_minus > 0:
    minus_first = divide(X, cnt_minus)


for i, x in enumerate(X):
    if x == "0":
        first = (plus_first + p_array[-(i+1)]) % cnt_plus
        print(count(first))
    else:
        if cnt_minus == 0:
            print(0)
        else:
            first = (minus_first - m_array[-(i+1)]) % cnt_minus
            print(count(first))

Submission status: Accepted

Solution code:
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def popcnt0(n):
        c = 0
        for i in range(20):
            c += (n >> i) & 1
        return c
    def cnt(num):
        c = 0
        while(num>0):
            #num %= bin(num).count("1")
            num %= popcnt0(num)
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        else:
            ans[-1] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(1)
        return
    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)
    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i] + 2*(bit -1)) % (bit-1)
            ans[i] = cnt(cur)+1
        #print(cur)

    for v in ans:
        print(v)
    return

def examE():
    T = I()
    ans = [0]*T

    for t in range(T):
        pass


    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  X = input()
  x = sum(map(int,list(X)))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = dp[i%sum(map(int,list(bin(i)[2:])))]+1
  cnt1 = 0
  if x>1:
    for i in range(N):
      cnt1 += int(X[-i-1])*pow(2,i,x-1)
      cnt1 %= x-1
  cnt2 = 0
  for i in range(N):
    cnt2 += int(X[-i-1])*pow(2,i,x+1)
    cnt2 %= x+1
  
  ans = [0]*N
  for i in range(N):
    if X[i]=='1':
      if x==1:
        ans[i] = 0
      else:
        num = (cnt1-pow(2,N-i-1,x-1))%(x-1)
        ans[i] = dp[num]+1
    else:
      num = (cnt2+pow(2,N-i-1,x+1))%(x+1)
      ans[i] = dp[num]+1
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    X = SI()
    X_pop = X.count("1")
    X_plus = X_pop + 1
    X_minus = X_pop - 1

    RP = [pow(2, i, X_plus) for i in range(N+1)]
    if X_minus > 0:
        RM = [pow(2, i, X_minus) for i in range(N+1)]
    else:
        RM = [0] * (N+1)

    X = X[::-1]
    rem_p = 0
    rem_m = 0
    for i in range(N):
        if X[i] == "1":
            rem_p += RP[i]
            rem_m += RM[i]

    for i in range(N-1, -1, -1):
        if X[i] == "0":
            tmp = (rem_p + RP[i]) % X_plus
        elif X_minus >= 1:
            tmp = (rem_m - RM[i]) % X_minus
        else:
            print(0)
            continue
        ans = 1
        while tmp > 0:
            tmp = tmp % bin(tmp).count("1")
            ans += 1
        print(ans)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()

A = [0]
for i in range(1,2*10**5):
    a = 0
    r = i
    for j in range(18):
        a += (i>>j)&1
    r %= a
    if r == 0:
        A.append(1)
    else:
        A.append(1+A[r])

X = LS2()

b = 0
for i in range(N):
    if X[i] == '1':
        b += 1
if b >= 2:
    c = b-1
    d = b+1

    r1 = 0
    r2 = 0

    amari1 = [1]
    amari2 = [1]
    for i in range(1,N):
        amari1.append((amari1[-1]*2) % c)
        amari2.append((amari2[-1]*2) % d)
    amari1.reverse()
    amari2.reverse()
    for i in range(N):
        if X[i] == '1':
            r1 += amari1[i]
            r1 %= c
            r2 += amari2[i]
            r2 %= d
    ANS = []
    for i in range(N):
        if X[i] == '1':
            e = r1
            e -= amari1[i]
            e %= c
            ANS.append(A[e]+1)
        else:
            f = r2
            f += amari2[i]
            f %= d
            ANS.append(A[f]+1)
else:
    d = b + 1
    r2 = 0


    amari2 = [1]
    for i in range(1, N):
        amari2.append((amari2[-1] * 2) % d)
    amari2.reverse()

    for i in range(N):
        if X[i] == '1':

            r2 += amari2[i]
            r2 %= d
    ANS = []
    for i in range(N):
        if X[i] == '1':

            ANS.append(0)
        else:
            f = r2
            f += amari2[i]
            f %= d
            ANS.append(A[f] + 1)


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

Submission status: Accepted

Solution code:
def popcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  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
n = int(input())
x = str(input())
ans = [1 for _ in range(n)]
c = 0
for i in range(n):
  if x[i] == "1":
    c += 1
m1 = c-1
m2 = c+1
a1 = 0
a2 = 0
rl1 = [0 for _ in range(n)]
rl2 = [0 for _ in range(n)]
r1 = 1
r2 = 1
if m1 == 0:
  rl2 = [0 for _ in range(n)]
  ans = [1 for _ in range(n)]
  for i in range(n):
    if x[n-i-1] == "1":
      a2 = (a2+r2)%m2
    rl2[i] = r2
    r2 = (r2*2)%m2
  b = [0 for _ in range(n)]
  for i in range(n):
    if x[i] == "1":
      ans[i] = 0
      b[i] = 0
    else:
      bi = (a2 + (rl2[n-i-1]))%m2
      b[i] = bi
  while sum(b) != 0:
    for i in range(n):
      if b[i] !=0:
        b[i] = b[i]%(popcount(b[i]))
        ans[i] += 1
  for ai in ans:
    print(ai)
  exit()
for i in range(n):
  if x[n-i-1] == "1":
    a1 = (a1+r1)%m1
    a2 = (a2+r2)%m2
  rl1[i] = r1
  rl2[i] = r2
  r1 = (r1*2)%m1
  r2 = (r2*2)%m2
b = [0 for _ in range(n)]
for i in range(n):
  if x[i] == "1":
    bi = (a1 - (rl1[n-i-1]))%m1
    b[i] = bi
  else:
    bi = (a2 + (rl2[n-i-1]))%m2
    b[i] = bi
ans = [1 for _ in range(n)]
while sum(b) != 0:
  for i in range(n):
    if b[i] !=0:
      b[i] = b[i]%(popcount(b[i]))
      ans[i] += 1
for ai in ans:
  print(ai)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def f(i):
    if C==1:
        if i==mark:
            return 0
        else:
            if X[i]=='0':
                nex = (d[p+1]+pow(2, N-1-i, p+1))%(p+1)
            else:
                nex = (d[p-1]-pow(2, N-1-i, p-1))%(p-1)
    
            res = 1
    
            while nex>0:
                pc = 0
        
                for i in range(20):
                    if (nex>>i)&1:
                        pc += 1
        
                nex %= pc
                res += 1
    
            return res
        
            
    if X[i]=='0':
        nex = (d[p+1]+pow(2, N-1-i, p+1))%(p+1)
    else:
        nex = (d[p-1]-pow(2, N-1-i, p-1))%(p-1)
    
    res = 1
    
    while nex>0:
        pc = 0
        
        for i in range(20):
            if (nex>>i)&1:
                pc += 1
        
        nex %= pc
        res += 1
    
    return res

N = int(input())
X = list(input()[:-1])

if X=='0'*N:
    for i in range(N):
        print(1)
    exit()

C = X.count('1')

for i in range(N):
    if X[i]=='1':
        mark = i
    
p = 0

for Xi in X:
    if Xi=='1':
        p += 1

d = defaultdict(int)

if C==1:
    for i in [p, p+1]:
        for j in range(N):
            if X[j]=='1':
                d[i] += pow(2, N-1-j, i)
else:
    for i in [p-1, p, p+1]:
        for j in range(N):
            if X[j]=='1':
                d[i] += pow(2, N-1-j, i)

for i in range(N):
    print(f(i))

Submission status: Accepted

Solution code:
def popcount(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 g(num_in):
    num = num_in
    cnt = 0
    if num == 0:
        return 0

    while True:
        base = popcount(num)
        if num%base == 0:
            cnt += 1
            break
        else:
            num = num%base
            cnt += 1
    return cnt


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

st = 0
for c in s:
    if c == "1":
        st += 1

if st > 1:

    mod_p1 = [0 for i in range(n)]
    mod_n1 = [0 for i in range(n)]
    base1 = 1
    base2 = 1
    for i in range(n):
        t1 = base1%(st+1)
        t2 = base2%(st-1)

        mod_p1[-i-1] = t1
        mod_n1[-i-1] = t2

        base1 *= 2
        base2 *= 2

        base1%=(st+1)
        base2%=(st-1)

    p1 = 0
    n1 = 0
    for i in range(n):
        if s[i] == "1":
            p1 += mod_p1[i]
            n1 += mod_n1[i]

    for i in range(n):
        if s[i] == "0":
            base = p1
            base += mod_p1[i]
            base %= st+1
            print(1+g(base))

        else:
            base = n1
            base -= mod_n1[i]
            base %= st-1
            print(1+g(base))

else:
    mod_p1 = [0 for i in range(n)]
    base1 = 1
    for i in range(n):
        t1 = base1 % (st + 1)

        mod_p1[-i - 1] = t1

        base1 *= 2

        base1 %= (st + 1)

    p1 = 0
    for i in range(n):
        if s[i] == "1":
            p1 += mod_p1[i]

    for i in range(n):
        if s[i] == "0":
            base = p1
            base += mod_p1[i]
            base %= st + 1
            print(1 + g(base))

        else:
            print(0)