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
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
fact = math.factorial
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
X = s()[::-1]
num1 = 1
num2 = 1
num3 = 0
num4 = 0
cnt = 0
for i in range(N):
    if X[i] == '1':
        cnt += 1
cnt1 = cnt+1#0用
cnt2 = cnt-1#1用
nums = []
ans = []
tans = [1]*N
for i in range(N):
    if X[i] == '0':
        nums.append(num1)
    else:
        num3 += num1
        num4 += num2
        nums.append(num2)
    if cnt1 != 0:
        num1 = (num1*2)%cnt1
    if cnt2 != 0:
        num2 = (num2*2)%cnt2
if cnt1 != 0:
    num3 %= cnt1
if cnt2 != 0:
    num4 %= cnt2
for i in range(N):
    if X[i] == '0':
        if cnt1 != 0: 
            ans.append((num3+nums[i])%cnt1)
        else:
            ans.append(0)
            tans[i] = 0
    else:
        if cnt2 != 0:    
            ans.append((num4-nums[i])%cnt2)
        else:
            ans.append(0)
            tans[i] = 0
ans.reverse()
tans.reverse()
def f(n):
    if n == 0:
        return
    tans[i] += 1
    c = n%(list(bin(n)[2:]).count('1'))
    f(c)
for i in range(N):
    f(ans[i])
for i in range(N):
    print(tans[i])

Submission status: Accepted

Solution code:
def Base_n_to_10(X,n):
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(n**(i-1))
    return out#int outn=int(input())
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
n=int(input())
x=input()
ans=[]
pc=x.count("1")
la=[float("inf")]*pc
for i in range(1,pc+1):
    i10=str(Base_10_to_n(i, 2)).count("1")
    if i%i10==0:
      la[i-1]=1
    else:
      la[i-1]=la[(i%i10)-1]+1
if pc!=1:
  x10=Base_n_to_10(x,2)
  a=x10%(pc+1)
  b=x10%(pc-1)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((a+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append((b-pow(2,n-i,pc-1))%(pc-1))
  for a in ans:
    if a==0:
      print(1)
    else:
      print(1+la[a-1])
else:
  x10=Base_n_to_10(x,2)
  for i in range(1,n+1):
    if x[i-1]=="0":
      ans.append((x10+pow(2,n-i,pc+1))%(pc+1))
    else:
      ans.append("n")
  for a in ans:
    if a==0:
      print(1)
    elif a=="n":
      print(0)
    else:
      print(1+la[a-1])

Submission status: Accepted

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

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    x = x[::-1]

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

Submission status: Accepted

Solution code:
def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

def main():
    n = int(input())
    x = input()

    c1 = x.count('1')
    cc2 = int('0b' + x, 0) % (c1 + 1)

    if c1 == 1:
        for i in range(n):
            if x[i] == '1':
                print(0)
            else:
                print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
        exit()

    cc1 = int('0b' + x, 0) % (c1 - 1)

    for i in range(n):
        if x[i] == '1':
            print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

main()

Submission status: Accepted

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

def popcnt(x):
    n=x
    res=0
    while n>0:
        res+=n%2
        n//=2
    return res

table=[0,1]+[-1 for i in range(219998)]
for i in range(2,220000):
    table[i]=table[i%popcnt(i)]+1

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

plus=0  #もとの数字に1のときのmodをしたやつ
minus=0

for i in range(N):
    plus+=int(X[i])*pow(2,N-1-i,max(1,moto-1))
    minus+=int(X[i])*pow(2,N-1-i,moto+1)
    plus%=(max(1,moto-1))
    minus%=(moto+1)

for i in range(N):
    ans=0
    if X[i]=='1':
        ans=plus
        ans-=pow(2,N-1-i,max(1,moto-1))
        ans%=(max(1,moto-1))
        if moto==1:
            ans=-1
    else:
        ans=minus
        ans+=pow(2,N-1-i,moto+1)
        ans%=(moto+1)
    if ans==-1:
        print(0)
    else:
        print(table[ans]+1)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
k = x.count("1")
cnt = 0
s = int(x, 2)
if k >= 2:
	k1 = s % (k-1)
k2 = s % (k+1)
while s != 0:
	targ = bin(s).count("1")
	s = s % targ
	cnt += 1

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

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

Submission status: Accepted

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

    if one_cnt == 0:
        for i in range(n):
            print(1)
        exit()
    
    x = x[::-1]

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

Submission status: Accepted

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

def main():
    N = int(input())
    Xs = input()
    X = int(Xs, 2)
    d = popcnt(X)

    lut = [0] * N
    for i in range(1, N):
        Xi = i % popcnt(i)
        lut[i] = lut[Xi] + 1

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm if dm else 0
    # print(lut)
    # print(format(X, 'b'))
    
    ans = []
    for i in range(N):
        mask = 1 << (N-i-1)
        Xi = X ^ mask
        _ans = 0
        if Xs[i] == '1':
            if dm:
                m = (mm - pow(2, N-i-1, dm)) % dm
                _ans = lut[m] + 1
            # m = (mm - mask) % dm
        else:
            # m = (mp + mask) % dp
            m = (mp + pow(2, N-i-1, dp)) % dp
            _ans = lut[m] + 1
        ans.append(_ans)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = int(input(),2)
pc = 0
d = []
c = x
for i in range(n):
    d.append(c&1)
    if c&1 == 1:
        pc += 1
    c=c>>1
mp = x%(pc+1)
if pc == 1:
    mm = -1
else:
    mm = x%(pc-1)
for i in range(n):
    if d[-i-1]==0:
        temp = (mp+pow(2,n-i-1,pc+1)) % (pc+1)
        ans = 1
    else:
        if mm == -1:
            temp = 0
            ans = 0
        else:    
            temp = (mm-pow(2,n-i-1,pc-1)) % (pc-1)
            ans = 1
    while temp:
        c = temp
        temppc = 0
        while c:
            if c&1 == 1:
                temppc += 1
            c=c>>1
        if temppc == 0:
            break
        temp = temp % temppc
        ans += 1
    print(ans)

Submission status: Accepted

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

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1

lsp=[1 for i in range(N)]
for i in range(1,N):
  lsp[i]=(lsp[i-1]*2)%bp
lsp.reverse()
fXp=0
for i in range(N):
  if S[i]=='1':
    fXp=(fXp+lsp[i])%bp
    
if bm!=0:
  lsm=[1 for i in range(N)]
  for i in range(1,N):
    lsm[i]=(lsm[i-1]*2)%bm
  lsm.reverse()
  fXm=0
  for i in range(N):
    if S[i]=='1':
      fXm=(fXm+lsm[i])%bm


def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
for i in range(1,bitcount+2):
  ls[i]=ls[f(i)]+1

for i in range(N):
  if S[i]=='0':
    print(ls[(fXp+lsp[i])%bp]+1)
  else:
    if bm==0:
      print(0)
    else:
      print(ls[(fXm-lsm[i])%bm]+1)

Submission status: Accepted

Solution code:
def main(N, X):
    lst = list(map(int, list(X)))
    num = lst.count(1)  # 初期状態で1を持つ数．

    def func(x):    # xは10進数
        lst = list(bin(x)[2:])
        amari =  x % lst.count('1')
        return amari

    d = {}
    for i in range(1, N):
        d[i] = func(i)


    # 反転させるので num + 1 か， num - 1 で割る場合しか存在しない．
    plus = []   # num + 1 で各桁 (2 ** n) を割った値を保存
    minus = []  # num - 1 で各桁 (2 ** n) を割った値を保存

    p = 1
    m = 1
    for n in range(N):
        p %= (num + 1)
        plus.append(p)
        p *= 2
        if num - 1 > 0:
            m %= (num - 1)
            minus.append(m)
            m *= 2

    o = int(X, 2)   # originalの 'o'
    amari_plus = o % (num + 1)
    if num - 1 > 0:
        amari_minus = o % (num - 1)

    for i in range(N):
        if lst[i] == 0:
            amari = (amari_plus + plus[- i - 1]) % (num + 1)
        elif num - 1 <= 0:
            print(0)
            continue
        else:
            amari = (amari_minus + (num - 1) - minus[- i - 1]) % (num - 1)
        ans = 1
        while amari != 0:
            amari = d[amari]
            ans += 1
        print(ans)

if __name__ == '__main__':
    N = int(input())
    X = input()
    main(N, X)

Submission status: Accepted

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

    c1 = x.count('1')
    if c1 > 1:
        cc1 = int('0b' + x, 0) % (c1 - 1)
    cc2 = int('0b' + x, 0) % (c1 + 1)

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

    if c1 == 1:
        for i in range(n):
            if x[i] == '1':
                print(0)
            else:
                print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
        exit()

    for i in range(n):
        if x[i] == '1':
            print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

main()

Submission status: Accepted

Solution code:
n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0
 
 
def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]
 
 
ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = sys.stdin.readline()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i, x_1 - 1)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i, x_1 + 1)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
Xb = input().rstrip()
p = Xb.count('1')
def popcount(x):
    return bin(x).count('1')
def calc(X):
    ans = 0
    while X!=0:
        X %= popcount(X)
        ans += 1
    return ans
Xp = 0
Xm = 0
tp = 1
tm = 1
b = 0
if p>1:
    flag = True
else:
    flag = False

for i in reversed(range(N)):
    if Xb[i]=='1':
        Xp += tp
        Xp %= (p+1)
        if flag:
            Xm += tm
            Xm %= (p-1)
    tp *= 2
    tp %= (p+1)
    if flag:
        tm *= 2
        tm %= (p-1)

for i in range(N):
    if Xb[i]=='1' and p==1:
        print(0)
        continue
    elif Xb[i]=='1':
        X = (Xm - pow(2,N-1-i,p-1)+p-1)%(p-1)
    else:
        X = (Xp + pow(2,N-1-i,p+1))%(p+1)
    print(calc(X)+1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
X = list(input())

# xが0になるまで何回かかるか
def calc(x):
    n = len(x)
    c = x.count('1')
    now = 0
    for i in range(n):
        if x[i] == '1':
            now += 2**(n-1-i)
            now %= c
    if now == 0:
        return 1
    else:
        return calc(list(format(now,'b')))+1

count = X.count('1')

a = [1]*(N+1)
if count >= 2:
    a[0] = 1%(count-1)
    for i in range(1,N+1):
        a[i] = a[i-1]*2
        a[i] %= count-1

b = [1]*(N+1)
b[0] = 1%(count+1)
for i in range(1,N+1):
    b[i] = b[i-1]*2
    b[i] %= count+1

suma = 0
sumb = 0
for i in range(N):
    if X[i] == '1':
        suma += a[N-i-1]
        sumb += b[N-i-1]
        sumb %= (count+1)
        if count >= 2:
            suma %= (count-1)

ans = [0]*N
for i in range(N):
    if X[i] == '1':
        if count == 1:
            ans[i] = 0
            continue
        val = (suma-a[N-i-1])%(count-1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1
    else:
        val = (sumb+b[N-i-1])%(count+1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0


def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]


ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])

Submission status: Accepted

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

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

dp = []
for d in range(n):
    if cnt == 1 and X[d] == '1':
      dp.append(-1)
      continue

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from functools import lru_cache,reduce
@lru_cache()
def dfs(n):
    if n == 0:
        return 0
    popcnt = bin(n).count('1')
    if n%popcnt == 0:
        return 1
    return dfs(n%popcnt) + 1

def main():
    N = int(input())
    X = input()
    cnt = 0
    for i in range(N):
        if X[i] == '1':
            cnt += 1
    
    if cnt == 0:
        for i in range(N):
            print(1)
        return 
    
    power1 = [0] * N
    power2 = [0] * N
    for i in range(N):
        if cnt > 1:
            power1[i] = pow(2,i,cnt - 1)
        power2[i] = pow(2,i,cnt + 1)
    
    modu1 = 0
    modu2 = 0
    ans = [0] * N
    for i in range(N):
        if X[N - i - 1] == '1':
            if cnt > 1:
                modu1 += power1[i]
                modu1 %= (cnt - 1)
            modu2 += power2[i]
            modu2 %= (cnt + 1)
    
    for i in range(N):
        if X[i] == '1':
            if cnt == 1:
                ans[i] = 0
                continue
            now = modu1
            now -= power1[N - i - 1]
            now %= (cnt - 1)
            ans[i] = dfs(now) + 1
        else:
            now = modu2
            now += power2[N - i - 1]
            now %= (cnt + 1)
            ans[i] = dfs(now) + 1
    print('\n'.join(map(str,ans)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
x = input()
cnt = x.count("1")
x_cnt_plus = 0
x_cnt_minus = 0
for i in range(n):
    if x[i] == "1":
        x_cnt_plus += pow(2, n - i - 1, cnt + 1)
        x_cnt_plus %= cnt + 1
        if cnt > 1:
            x_cnt_minus += pow(2, n - i - 1, cnt - 1)
            x_cnt_minus %= cnt - 1
for i in range(n):  # 上からi 桁目に注意
    if x[i] == "0":
        f = x_cnt_plus + pow(2, n - i - 1, cnt + 1)
        f %= cnt + 1
    else:
        if cnt == 1:
            print(0)
            continue
        f = x_cnt_minus + cnt - 1 - pow(2, n - i - 1, cnt - 1)
        f %= cnt - 1
    ans = 1
    while f != 0:
        cnt_f_1 = 0
        k = f
        while k:
            if k % 2:
                cnt_f_1 += 1
            k //= 2
        f = f % cnt_f_1
        ans += 1
    print(ans)
"""
step1; 1を数える cnt_1 
step2 : 全体の計算をする cnt1 + 1 とcnt1 -1 それぞれ
step3 : それぞれの桁に対して0 なら cnt+ 1 を適用 + 2**k mod cnt + 1
            1ならcnt - 1　を適用 - 2**k mod (cnt-1)
step4 : その中でf(x)を0になるまで計算
"""

Submission status: Accepted

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

c1 = x.count('1')
if c1 > 1:
    cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

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

if c1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
    exit()

for i in range(n):
    if x[i] == '1':
        print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)

Submission status: Accepted

Solution code:
def solve(N, strX):
    def getNum1s(numD):
        num1s = [0] * (1<<numD)
        for S in range(1, 1<<numD):
            num1s[S] = num1s[S ^ (S & -S)] + 1
        return num1s
    num1s = getNum1s(20)

    fs = [0] * (N+1)
    for x in range(1, N+1):
        fs[x] = fs[x%num1s[x]] + 1

    M = strX.count('1')
    M1, M9 = M+1, M-1

    XmodM1 = 0
    for X in strX:
        XmodM1 *= 2
        XmodM1 += int(X)
        XmodM1 %= M1
    XmodM9 = 0
    for X in strX:
        XmodM9 *= 2
        XmodM9 += int(X)
        XmodM9 %= M9

    modM1s = []
    modM1 = 1
    for d in range(N+2):
        modM1s.append(modM1)
        modM1 *= 2
        modM1 %= M1

    modM9s = []
    modM9 = 1
    for d in range(N+2):
        modM9s.append(modM9)
        modM9 *= 2
        modM9 %= M9

    anss = []
    for X, modM1, modM9 in zip(strX[::-1], modM1s, modM9s):
        if X == '0':
            Y2 = (XmodM1 + modM1) % M1
        else:
            Y2 = (XmodM9 - modM9) % M9
        ans = fs[Y2] + 1
        anss.append(ans)

    return anss[::-1]


def solve2(N, strX):
    def getNum1s(numD):
        num1s = [0] * (1<<numD)
        for S in range(1, 1<<numD):
            num1s[S] = num1s[S ^ (S & -S)] + 1
        return num1s
    num1s = getNum1s(20)

    fs = [0] * (N+1)
    for x in range(1, N+1):
        fs[x] = fs[x%num1s[x]] + 1

    M = strX.count('1')
    M1, M9 = M+1, M-1

    XmodM1 = 0
    for X in strX:
        XmodM1 *= 2
        XmodM1 += int(X)
        XmodM1 %= M1

    modM1s = []
    modM1 = 1
    for d in range(N+2):
        modM1s.append(modM1)
        modM1 *= 2
        modM1 %= M1

    anss = []
    for X, modM1 in zip(strX[::-1], modM1s):
        if X == '0':
            Y2 = (XmodM1 + modM1) % M1
            ans = fs[Y2] + 1
        else:
            ans = 0
        anss.append(ans)

    return anss[::-1]


N = int(input())
strX = input().rstrip()

num1 = strX.count('1')

if num1 == 0:
    anss = [1] * N
elif num1 == 1:
    anss = solve2(N, strX)
else:
    anss = solve(N, strX)

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

Submission status: Accepted

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

ans_reduce,ans_add = 0,0
for i in range(n):
    if(one_num>1):
        ans_reduce = (ans_reduce+pow(2,n-i-1,one_num-1)*(1 if x[i] == '1' else 0))%(one_num-1)
    ans_add = (ans_add+pow(2,n-i-1,one_num+1)*(1 if x[i] == '1' else 0))%(1+one_num)

for i in range(n):
    now_one = one_num + (-1 if x[i] == '1' else 1)
    if(now_one == 0):
        print(0)
        continue
    num = ((ans_reduce if x[i] == '1' else ans_add) + pow(2,n-i-1,now_one)*(-1 if x[i] == '1' else 1))%now_one
    ans = 1
    while(num!=0):
        ans += 1
        num = num % bin(num).count('1')
    print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############
popc = [0] * ((1 << 18) + 1)
for bit in range(1, 1 << 18):
    opt = bin(bit).count('1')
    popc[bit] = bit % opt

f_list = [0] * ((1 << 18) + 1)
for i in range(1, 1 << 18):
    now = popc[i]
    cnt = 1
    while True:
        if now == 0:
            f_list[i] = cnt
            break
        now = popc[now]
        cnt += 1

N = getN()
X = input()
NX = len(X)
time = X.count('1')
t1 = time + 1
t2 = time - 1

lis_left_1 = [0] * NX

now = 1 % t1
lis_left_1[0] = now
for i in range(1, NX):
    now = (2 * now) % t1
    lis_left_1[i] = now

lis_left_2 = [0] * NX

if t2 > 0:
    now = 1 % t2
    lis_left_2[0] = now
    for i in range(1, NX):
        now = (2 * now) % t2
        lis_left_2[i] = now

left_mother_1 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_1 += lis_left_1[NX - i - 1]

left_mother_2 = 0
for i in range(NX):
    if int(X[i]) == 1:
        left_mother_2 += lis_left_2[NX - i - 1]

for i in range(N):
    # 1が0に left_mother_2, t2
    if int(X[i]) == 1:
        if t2 == 0:
            print(0)
            continue
        opt_mom = left_mother_2
        opt_mom -= lis_left_2[NX - i - 1]
        opt_mom %= t2
        print(f_list[opt_mom] + 1)
    # 0が1に left_mother_1, t1
    else:
        opt_mom = left_mother_1
        opt_mom += lis_left_1[NX - i - 1]
        opt_mom %= t1
        print(f_list[opt_mom] + 1)

Submission status: Accepted

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

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]

    if Xc == 0:
        [print(1) for i in range(N)]
    elif Xc == 1:
        d = X.index(1)
        ans1 = 0
        for j in range(N):
            if X[j]:
                ans1 += pow(2,N-1-j,Xc+1)
                ans1 %= Xc+1

        for j in range(N):
            if d == j:
                print(0)
            else:
                if d == N-1 or j == N-1:
                    print(2)
                else:
                    print(1)
    else:
        ans1 = 0
        ans2 = 0
        for j in range(N):
            if X[j]:
                ans1 += pow(2,N-1-j,Xc+1)
                ans1 %= Xc+1
                ans2 += pow(2,N-1-j,Xc-1)
                ans2 %= Xc-1

        for i in range(N):
            if X[i]:# 1->0
                ans = (ans2 - pow(2,N-1-i,Xc-1)) % (Xc-1)
            else:# 0->1
                ans = (ans1 + pow(2,N-1-i,Xc+1)) % (Xc+1)
            count = 1
            while ans > 0:
                tmp = str(bin(ans)).count('1')
                ans %= tmp
                count += 1
            print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def popcnt(n):
    return bin(n).count("1")
N = int(input())
L = [0]*(N+1)
for i in range(1,N+1):
    L[i] = L[i%popcnt(i)]+1
L[N] = -1
X = input()
M = X.count("1")+1
m = max(1,M-2)
X = list(X)
XM = int(X[-1])
Xm = int(X[-1])
tM = 1
tm = 1
X.reverse()
for i in range(1,N):
    tM = tM*2%M
    tm = tm*2%m
    if X[i] == "1":
        XM = (XM + tM)%M
        Xm = (Xm + tm)%m
ans = []
tM = 1
tm = 1
for i in range(N):
    A = 0
    if X[i] == "0":
        A = (XM + tM)%M
    else:
        A = (Xm + m - tm)%m
        if M == 2:
            A = N
    ans.append(A)
    tM = (tM*2)%M
    tm = (tm*2)%m
ans.reverse()
for a in ans:
    print(L[a]+1)

Submission status: Accepted

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

cnt = 0
for i in range(N):
    if X[i] == "1":
        cnt += 1
    
down = [0] * N
up = [0] * N
ald = 0
alu = 0
for i in range(N):
    up[i] = pow(2, N-1-i, cnt+1)
    if X[i] == "1":
        alu += up[i]
        alu %= cnt+1
    if cnt <= 1:
        continue
    down[i] = pow(2, N-1-i, cnt-1)
    if X[i] == "1":
        ald += down[i]
        ald %= cnt-1

for i in range(N):    
    if X[i] == "1":
        if cnt == 1:
            print(0)
            continue
        n = (ald - down[i]) % (cnt-1)
    else:
        n = (alu + up[i]) % (cnt+1)
    ans = 1
    while n != 0:
        c = 0
        for j in range(20):
            if (n >> j) % 2 == 1:
                c += 1
        n %= c
        ans += 1
    print(ans)