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:
n = int(input())
x = input()

# ビット反転させる場所
# one_pop_count（1 -> 0）：1回目の割る値
# zero_pop_count（0 -> 1）：1回目の割る値
original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    # one_pop_count が 0 である場合は剰余演算を行わない ==> one_mod は 0
    if one_pop_count != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count

# f の前計算
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

# pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count

# n-1, n-2, ... 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 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 = X.count('1')
cnt1 = cnt+1#0用
cnt2 = cnt-1#1用
nums1 = []
nums2 = []
ans = [1]*N

for i in range(N):
    if X[i] == '0':
        nums1.append(num1)
    else:
        num3 += num1
        num4 += num2
        nums1.append(num2)
    if cnt1 != 0:
        num1 = (num1*2)%cnt1
    if cnt2 != 0:
        num2 = (num2*2)%cnt2

for i in range(N):
    if X[i] == '0':
        if cnt1 != 0: 
            nums2.append((num3+nums1[i])%cnt1)
        else:
            nums2.append(0)
            ans[i] = 0
    else:
        if cnt2 != 0:    
            nums2.append((num4-nums1[i])%cnt2)
        else:
            nums2.append(0)
            ans[i] = 0
nums2.reverse()
ans.reverse()

def p(n):
    if n == 0:
        return
    ans[i] += 1
    c = n%(bin(n).count('1'))
    p(c)

for i in range(N):
    p(nums2[i])
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

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

N=one_int()
S=one_str()

bit_count = S.count("1")
S_num = int(S,2)
S_min = S_num % (bit_count-1) if bit_count-1!=0 else 0
S_plu = S_num % (bit_count+1)




# calc_dict = {i:-1 for i in range(10000)}
# res_dict =  {i:-1 for i in range(10**4)}

# for i in range(1, 10000):
#     if calc_dict[i]==-1:
#         calc_dict[i] = bin(i).count("1")

#     res_dict[i] = i%calc_dict[i]+1

def mods(temp, count):
    count+=1
    if temp!=0:

#         if temp in res_dict:
#             return count+res_dict[temp]
        
#         if temp not in calc_dict:
#             calc_dict[temp]= bin(temp).count("1") 
        count = mods(temp%bin(temp).count("1") , count)

    return count

for i in range(N):
    if S[i]=="0":
        part = pow(2, (N-i-1), bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = pow(2, (N-i-1), bit_count-1)
        num = (S_min - part)%(bit_count-1)
        print(mods(num, 0))

Submission status: Accepted

Solution code:
n = int(input())
X = input()
x = int(X,2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+2)
for i in range(1,bitx+2):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = 0
xmm = 0


if bitx != 1:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
            xmm += pow(2, n-(i+1), bitm)
    for i in range(n):
        if X[i] == '1':
            xm = (xmm - pow(2,n-i-1,bitm)) % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
else:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
    for i in range(n):
        if X[i] == '1':
            l.append(str(0))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
print('\n'.join(l))

Submission status: Accepted

Solution code:
n = int(input())
x_s = input()
x = int(x_s, 2)

pops = bin(x).count("1")
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
for i in range(0,n):
    if x_s[i] == '1':
        if pops > 1:
            tmp = (x_pop_m - pow(2,n-1-i,(pops - 1)))%(pops - 1)
        else:
            print(0)
            continue
    else:
        tmp = (x_pop_p + pow(2,n-1-i,(pops + 1))) % (pops + 1)
    cnt = 1
    while tmp:
        tmp %= bin(tmp).count("1")
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/D_input.txt")
else:
    f=sys.stdin
#from 2nd count
def cnt_func(num):
    cnt=0
    while num:
        num%=bin(num).count("1")
        cnt+=1
    return cnt+1
n=int(f.readline().strip())
s=f.readline().strip()
input_val=int(s,2)
input_one_count=s.count("1")
#Base value
zero_first=input_val%(input_one_count+1)
one_first=input_val%(input_one_count-1) if input_one_count>1 else 0
ans=0
for idx,emt in enumerate(s):
    p=n-idx-1
    if emt=="0": #inverted to "1"
        ans=cnt_func((zero_first+(pow(2,p,input_one_count+1)))%(input_one_count+1))
    else: #inverted to "0"
        if input_one_count>1:
            ans=cnt_func((one_first-(pow(2,p,input_one_count-1)))%(input_one_count-1))
        else:
            ans=0
    print(ans)
f.close()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
X = input()
if X == '0':
    for _ in range(N):
        print(1)
        exit()

mem = [None] * (200005)
mem[0] = 0
def f(n):
    if mem[n] is not None: return mem[n]
    c = bin(n).count('1')
    r = 1 + f(n%c)
    mem[n] = r
    return r

for i in range(200005):
    f(i)

cnt = X.count('1')
a,b = cnt+1, cnt-1

ans = [None] * N

n = 0
for c in X:
    n *= 2
    n += int(c)
    n %= a
for i,c in reversed(list(enumerate(X))):
    if c=='1': continue
    ans[i] = mem[(n+pow(2,N-i-1,a))%a] + 1

if b:
    n = 0
    for c in X:
        n *= 2
        n += int(c)
        n %= b
    for i,c in reversed(list(enumerate(X))):
        if c=='0': continue
        ans[i] = mem[(n-pow(2,N-i-1,b))%b] + 1
else:
    for i in range(N):
        if ans[i] is None:
            ans[i] = 0

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

Submission status: Accepted

Solution code:
n = int(input())
x = input()
count_1 = x.count('1')
value = [0, 0]
x_int = int(x, 2)
value[0] = x_int % (count_1 - 1) if count_1 > 1 else 0
value[1] = x_int % (count_1 + 1)
for i in range(n):
    if x[i] == '0':
        tmp = (pow(2, n - i - 1, count_1 + 1) + value[1]) % (count_1 + 1)
    else:
        if count_1 == 1:
            print(0)
            continue
        tmp = (-pow(2, n - i - 1, count_1 - 1) + value[0]) % (count_1 - 1)
    ans = 1
    while tmp > 0:
        tmp = tmp % (bin(tmp).count('1'))
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = input()   
              
x_val = int(X, 2)
pc_x = X.count('1')
              
x_mod_pc_x_plus_1 = x_val % (pc_x + 1)
x_mod_pc_x_minus_1 = x_val % max(pc_x - 1, 1)
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
        if pc == 0:
            print(0)
            continue
        val = (x_mod_pc_x_minus_1 - pow(2, N-i-1, pc)) % pc
    else:     
        pc = pc_x + 1
        val = (x_mod_pc_x_plus_1 + pow(2, N-i-1, pc)) % pc
    ans = 1   
    while val > 0:
        val %= bin(val).count('1')
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
# わからんわからんわからんわからんわからん
# なんで1500人も解いてんの？この界隈天才しかおらん
table = [0 for i in range(2*10**5+5)]
for i in range(2*10**5+5):
    table[i] = "{:0b}".format(i).count("1")


def main():
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            # 反転してt+1
            p = pow(2, N-i-1, t+1)
            x = x1 + p
            x %= t+1
        elif t != 1:
            p = pow(2, N-i-1, t-1)
            x = x2 - p
            x %= (t-1)
        else:
            ans = 0
        while x > 0:
            x %= table[x]
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D Anything Goes to Zero

n = int(input())
x = input()

original_pop_count = x.count("1")
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
  if one_pop_count != 0:
    one_mod = (one_mod * 2 + int(b)) % one_pop_count
  zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count

#fの前計算
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
  pop_count[i] = pop_count[i//2] + i % 2
  f[i] = f[i % pop_count[i]] + 1

#pow2の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
  if one_pop_count != 0:
    one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
  zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count

for i in range(n-1, -1, -1):
  if x[n-1-i] == "1":
    if one_pop_count != 0:
      nxt = one_mod
      nxt -= one_pow2[i]
      nxt %= one_pop_count
      print(f[nxt] + 1)
    else:
      print(0)
  if x[n-1-i] == "0":
    nxt = zero_mod
    nxt += zero_pow2[i]
    nxt %= zero_pop_count
    print(f[nxt] + 1)

Submission status: Accepted

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


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_mod_pcount_X_pls1 = X_int % pcount_X_pls1
    if pcount_X_mns1 != 0:
        X_mod_pcount_X_mns1 = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            n = (X_mod_pcount_X_pls1 + pow(2, N-i-1, pcount_X_pls1)) % pcount_X_pls1
        else:
            if pcount_X_mns1 == 0:
                print(0)
                continue
            n = (X_mod_pcount_X_mns1 - pow(2, N-i-1, pcount_X_mns1)) % pcount_X_mns1

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

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

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
  res = [None] * n
  for i in range(n):
    res[i] = II()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI()
  return res
def FR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR(n):
  res = [None] * n
  for i in range(n):
    res[i] = IF()
  return res
def LIR_(n):
  res = [None] * n
  for i in range(n):
    res[i] = LI_()
  return res
def SR(n):
  res = [None] * n
  for i in range(n):
    res[i] = S()
  return res
def LSR(n):
  res = [None] * n
  for i in range(n):
    res[i] = LS()
  return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
  def f(n, c):
    tmp = n % c
    t = tmp
    b = 0
    while tmp:
      if tmp & 1:
        b += 1
      tmp //= 2
    if t:
      return f(t, b) + 1
    else:
      return 1
  n = II()
  a = S()
  b = 0
  for ai in a:
    if ai == "1":
      b += 1
  a = a[::-1]
  bp = 0
  bm = 0
  if b != 1:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bm += pow(2, i, b - 1)
        bp %= b + 1
        bm %= b - 1
    ans = []
    for i, ai in enumerate(a):
      if ai == "1":
        tmpbm = bm - pow(2, i, b - 1)
        tmpbm %= b - 1
        ans.append(f(tmpbm, b - 1))
      else:
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return
  else:
    for i, ai in enumerate(a):
      if ai == "1":
        bp += pow(2, i, b + 1)
        bp %= b + 1
    ans = []
    for i, ai in enumerate(a):
      if ai == "1":
        ans.append(0)
      else:
        tmpbp = bp + pow(2, i, b + 1)
        tmpbp %= b + 1
        ans.append(f(tmpbp, b + 1))
    for ai in ans[::-1]:
      print(ai)
    return


#main
if __name__ == '__main__':
  solve()

Submission status: Accepted

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

if count == 0:
  for i in range(N):
    print(1)
    quit()
elif count == 1:
  if X[-1] == "1":
    for i in range(N):
      if i != N - 1:
        print(2)
      else:
        print(0)
  else:
    for i in range(N):
      if i!= N - 1:
        if X[i] == "1":
          print(0)
        else:
          print(1)
      else:
        print(2)
  quit()
  

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    now *= 2
    nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    

    nowm *= 2
    nowm %= (count - 1)
  
  else:
    now %= count
    nowp %= (count + 1)
    nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    num += now
    num %= count
    nump += nowp
    nump %= count + 1
    numm += nowm
    numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      #if count == 2:
      #  nextn[i] = 0
      #else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        ni = N - i - 1
        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0] = m2; m1[1] = i

        ans[i] = 1 + f2(n)

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

def f(n):
    cnt = 0
    while n>0:
        n = n%popcnt(n)
        cnt += 1
    return cnt

def solve(X):
    Y = int(X, 2)
    c = X.count("1")
    m, p = c-1, c+1
    Ym, Yp = Y%m if m else -1, Y%p
    for i in range(N):
        if X[i] == "1":
            Y = (Ym - pow(2,N-i-1,m))%m if Ym!=-1 else -1
        else:
            Y = (Yp + pow(2,N-i-1,p))%p
        print(f(Y) + 1 if Y!=-1 else 0)

N = int(input())
solve(input())

Submission status: Accepted

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

LEN=2*10**5+10
moves=[0]*LEN
for i in range(1,LEN): #1～Nまでのすべての数について、0になるまでの操作回数を求める
 tmp=i
 cnt=0
 while tmp!=0:
   popcount=0
   for j in range(20):
     if tmp&(1<<j):
       popcount+=1
   tmp%=popcount
   cnt+=1
 moves[i]=cnt

n=int(input())
x=input()
k=x.count('1') 
if k==0: 
   for i in range(n):
       print(1)
elif k==1: 
   pos=x.index('1') 
   for i in range(n):
       if i==pos: 
           print(0)
       else:
           if pos==n-1: 
               print(2)
           else:
               if i==n-1: 
                   print(2)
               else:
                   print(1)
else:
   sum1=0 
   sum2=0 
   tmp1=1
   tmp2=1
   for i in range(n-1,-1,-1): 
       if x[i]=='1':
           sum1+=tmp1
           sum1%=k+1
           sum2+=tmp2
           sum2%=k-1
       tmp1*=2
       tmp1%=k+1
       tmp2*=2
       tmp2%=k-1
   for i in range(n):
       if x[i]=='0': 
           tmp=sum1+pow(2,n-i-1,k+1)
           tmp%=k+1
           print(moves[tmp]+1)
       else: 
           tmp=sum2-pow(2,n-i-1,k-1)
           tmp%=k-1
           print(moves[tmp]+1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque

def sum_count(arr):
    mem = arr[:]
    while True:
        if len(mem) == 1:break
        tmp = []
        while True:
            if len(mem) == 1:
                tmp.append(mem[-1])
                mem = tmp[:]
                break
            if len(mem) == 0:
                mem = tmp[:]
                break
            x1, x2 = mem.pop(), mem.pop()
            tmp.append(int(x1) + int(x2))

    return int(mem[0])

def run():
    N = int(input())
    X = list(input())[::-1]
    lis_bf = []
    lis_af = []
    count1 = sum_count(X)
    sum_val_bf, sum_val_af = 0, 0
    if count1 <= 1:
        for i in range(N):
            tmp_af = 0
            if int(X[i]):
                tmp_af = pow(2, i, count1 + 1)
            lis_af.append(tmp_af)
            sum_val_af += tmp_af
            sum_val_af %= count1 + 1

        for i in list(range(N))[::-1]:
            ans = 0
            if X[i] == '1':
                print(0)
                continue
            else:
                next_val = (sum_val_af + pow(2, i, count1 + 1)) % (count1 + 1)
            # print(next_val)
            ans += 1
            # print(f'i : {i}, next_val : {next_val}')
            while True:
                if next_val == 0: break
                val = next_val
                count_n = sum_count(list(bin(val)[2:]))
                next_val = val % count_n
                ans += 1
                # print(f'next_val : {next_val}')
            print(ans)
        return None

    for i in range(N):
        tmp_bf, tmp_af = 0,0
        if int(X[i]):
            tmp_bf = pow(2, i , count1-1)
            tmp_af = pow(2, i, count1+1)
        lis_bf.append(tmp_bf)
        lis_af.append(tmp_af)
        sum_val_bf += tmp_bf
        sum_val_bf %= count1-1
        sum_val_af += tmp_af
        sum_val_af %= count1 + 1

    for i in list(range(N))[::-1]:
        ans = 0
        if X[i] == '1':
            next_val = (sum_val_bf - lis_bf[i]) % (count1-1)
        else:
            next_val = (sum_val_af + pow(2, i, count1+1)) % (count1+1)
        #print(next_val)
        ans += 1
        #print(f'i : {i}, next_val : {next_val}')
        while True:
            if next_val == 0:break
            val = next_val
            count_n = sum_count(list(bin(val)[2:]))
            next_val = val % count_n
            ans += 1
            #print(f'next_val : {next_val}')
        print(ans)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
from sys import stdin

def mpow(n, p, mod):
    if mod == 0:
        return 0
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def popcount(u):
    if u == 0:
        return 0
    a = u % bin(u).count('1')
    return 1 + popcount(a)
def main():
    input = stdin.readline
    n = int(input())
    x = '0b' + input()
    xs = int(x, 0)
    xc = x.count('1')
    xsp = mpow(xs, 1, xc + 1)
    xsm = mpow(xs, 1, xc - 1)
    for i in range(2, n + 2):
        if x[i] == '0':
            y = xsp + mpow(2, n - i + 1, xc + 1)
            y = mpow(y, 1, xc + 1)
        elif xc == 1:
            print(0)
            continue
        else:
            y = xsm - mpow(2, n - i + 1, xc - 1)
            y = mpow(y, 1, xc - 1)
        print(popcount(y) + 1)
main()

Submission status: Accepted

Solution code:
from sys import stdin

def mpow(n, p, mod):
    if mod == 0:
        return 0
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def popcount(u):
    if u == 0:
        return 0
    a = u % bin(u).count('1')
    return 1 + popcount(a)
def main():
    input = stdin.readline
    n = int(input())
    x = '0b' + input()
    xs = int(x, 0)
    xc = x.count('1')
    xsp = mpow(xs, 1, xc + 1)
    xsm = mpow(xs, 1, xc - 1)
    for i in range(2, n + 2):
        if x[i] == '0':
            y = xsp + mpow(2, n - i + 1, xc + 1)
            y = mpow(y, 1, xc + 1)
            print(popcount(y) + 1)
        elif xc == 1:
            print(0)
        else:
            y = xsm - mpow(2, n - i + 1, xc - 1)
            y = mpow(y, 1, xc - 1)
            print(popcount(y) + 1)
main()

Submission status: Accepted

Solution code:
n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(n):
    return bin(n).count('1')

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)

Submission status: Accepted

Solution code:
def solve(N,X):
    ans = []
    cnt = X.count("1")
    rem_ori = [0,0]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem_ori[0] += pow(2,N-i-1,cnt-1)
                rem_ori[0] %= (cnt-1)
            else:
                rem_ori[0] = 0
            rem_ori[1] += pow(2,N-i-1,cnt+1)
            rem_ori[1] %= (cnt+1)

    rem = [(rem_ori[0] if X[i] == "1" else rem_ori[1]) for i in range(N)]
    for i in range(N):
        if X[i] == "1":
            if cnt != 1:
                rem[i] -= pow(2,N-i-1,cnt-1)
                rem[i] %= (cnt-1)
                ans.append(cal(rem[i],1))
            else:
                ans.append(0)
        else:
            rem[i] += pow(2,N-i-1,cnt+1)
            rem[i] %= (cnt+1)
            ans.append(cal(rem[i],1))

    return ans

def cal(rem,rec):
    if rem == 0:
        return rec
    else:
        b = bin(rem)[2:]
        cnt = b.count("1")
        rem %= cnt
        return cal(rem,rec+1)

def main():
    N = int(input())
    X = input()

    ans = solve(N,X)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0:
        one_mod = (one_mod *2 + int(b))%one_pop_count
    zero_mod = (zero_mod *2 + int(b))%zero_pop_count

f = [0]*220001
pop_count = [0]*220001
for i in range(1, 220001):
    pop_count[i] = pop_count[i//2] + i%2
    f[i] = f[i%pop_count[i]] + 1

one_pow2 = [1]*220001
zero_pow2 = [1]*220001
for i in range(1, 220001):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] *2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] *2 % zero_pop_count

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt]+1)
        else:
            print(0)

    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt]+1)

Submission status: Accepted

Solution code:
import math


def f(n):
    pop = 0
    ntemp = n
    for i in range(int(math.log2(n)) + 1):
        pop += ntemp % 2
        ntemp //= 2
    return n % pop


n = int(input())
S = input()
popcount = 0
for i in range(n):
    popcount += int(S[i])

# 1が1個しかない場合の例外処理
if popcount == 1:
    if S[-1] == 1:
        ans = [2] * n
        ans[-1] = 0
    else:
        ans = [1] * n
        ans[-1] = 2
        for i in range(n):
            if S[i] == '1':
                ans[i] = 0
    for i in range(n):
        print(ans[i])
    exit()


Sint = int(S, 2)
remminus = Sint % (popcount - 1)
remplus = Sint % (popcount + 1)

# 1,2,4,...の余りのリストを準備
remlistminus = []
remlistplus = []
temp = 1
for i in range(n):
    remlistminus.append(temp)
    temp = (temp * 2) % (popcount - 1)
temp = 1
for i in range(n):
    remlistplus.append(temp)
    temp = (temp * 2) % (popcount + 1)
remlistminus.reverse()
remlistplus.reverse()

ans = []
for i in range(n):
    count = 1
    if S[i] == '0':
        rem = (remplus + remlistplus[i]) % (popcount + 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    else:
        rem = (remminus - remlistminus[i]) % (popcount - 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    ans.append(count)
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
N=int(input())
X=input()
c=X.count('1')
r1=int(X,2)%(c-1) if c>1 else 0
r2=int(X,2)%(c+1)
d=[0]*(N+1)
for i in range(N):
    d[i+1]=d[(i+1)%bin(i+1).count('1')]+1
for i in range(N):
    if X[i]=='0':
        n=(r2+pow(2,N-i-1,c+1))%(c+1)
    else:
        if c==1:
            print(0)
            continue
        n=(r1-pow(2,N-i-1,c-1))%(c-1)
    print(d[n]+1)

Submission status: Accepted

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

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1 # 0になりうる
zero_pop_count = original_pop_count + 1

# X mod p(X) += 1 の前計算
one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count

# f の前計算
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    # pop_count[i] = pop_count[i // 2] + i % 2
    pop_count[i] = bin(i)[2:].count('1')
    f[i] = f[i % pop_count[i]] + 1

for i in range(n-1, -1, -1):
    if x[n-i-1] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= pow(2, i, one_pop_count)
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    elif x[n-i-1] == '0':
        nxt = zero_mod
        nxt += pow(2, i, zero_pop_count)
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Submission status: Accepted

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

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

x = int(X, 2)
pcx = X.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)


for i in range(N):
    if X[i] == '0':
        X_next = pc2 + pow(2,N-1-i,pcx+1)
        X_pop_next = pcx + 1
    elif X[i] == '1' and pcx - 1 != 0:
        X_next = pc1 - pow(2,N-1-i,pcx-1)
        X_pop_next = pcx - 1
    else :
        print(0)
        continue
    
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
    
    print(ans)