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:
def popcount(n):
    return bin(n).count("1")


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


n = int(input())
# f(0)~f(n)までを計算しておく
F = [f(i) for i in range(n + 2)]
x = input()
pcx = x.count("1")
# xをpcx-1,pcx+1で割ったあまりをそれぞれ計算

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

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

Submission status: Accepted

Solution code:
import math

A = [0]*200001
for i in range(18):
    for j in range(2**i,2**(i+1)):
        if j <= 200000:
            A[j] = i + 1

def bii(x):
    a = A[x]
    o = [0]*a
    for i in range(a):
        o[i] = x % 2
        x //= 2
    return o

def f(x):
    bi = bii(x)
    popcount = sum(bi)
    a = x % popcount
    if a == 0:
        return 1
    else:
        return f(a)+1

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

popc = sum(X)
D = dict()
E = dict()
for j in [popc-1,popc+1]:
    E[j] = 0
    D[j] = [0]*N
    b = 1
    if j == 0:
        continue
    for i in range(N):
        D[j][i] = b
        E[j] += X[i] * b
        E[j] %= j
        b *= 2
        b %= j

aaaa = []
for i in range(N):
    an = X[-(i+1)]
    bb = 1 - 2 * an
    #もしi桁目が1ならば、ビット反転によってpopcとXは減る
    #もしi桁目が0ならば、ビット反転によってpopcとXは増える
    if popc == 1 and an == 1:
        print(0)
        continue
    j = popc + bb
    su = (E[j] + bb * D[j][-(i+1)] + j) % j
    if su == 0:
        print(1)
        continue
    else:
        print(f(su)+1)
        continue

Submission status: Accepted

Solution code:
def power(x, y, p) : 
    if y==0: return 1%p
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % p  
      
    if (x == 0) : 
        return 0
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % p 
    return res  

F = [0,1,1]
for i in range(3,200001):
	F += [ 1 + F[i%(bin(i).count('1'))]]
	

n=int(input())
s=input()
ones = s.count('1')
a = ones -1
b = ones
c = ones+1
moda = modb = modc = 0
for i in range(n-1,-1,-1):
	pos = n-1-i
	if s[i]=='1':
		if a>0 : moda = (moda + power(2, pos, a) ) %a
		modc = (modc + power(2, pos, c) ) %c

for i in range(n):
	if s[i] == '0': #ajout
		add = power(2, n-1-i, c)
		ans = (modc + add) % c
		# ~ print("i",i, "add",add,"ans",ans)
		print(F[ans]+1)
	else: # retrait
		if a<=0: print(0)
		else:
			sub = power(2, n-1-i, a)
			ans = (moda - sub) % a
			print(F[ans]+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

# 各クエリO(1)
# 求めたいのは0になるまでの回数
# 事前に1 - 2*10**5まで、になった回数を記録しておくとか？ (小さい方の数は必ずわかっている) (あまりがbit超で10**5を超えないのはわかっている)

# これがクリアされても 2**(2*10**5)の数字であまりが取れない問題がある
# 一回割ってしまえばこっちのもんよ

N = a_int()
X = read()[:-1]
px0 = X.count('1')
px0p = px0 + 1
px0n = (px0 - 1) if px0 != 1 else -1
# 上から、px0-1, px0, px0+1で割ったもの
x0n = 0
x0 = 0
x0p = 0

for i, bit in enu(reversed(X)):
    if bit == '1':
        x0n += pow(2, i, px0n)
        x0n %= px0n
        x0 += pow(2, i, px0)
        x0 %= px0
        x0p += pow(2, i, px0p)
        x0p %= px0p


x0 = [x0n, x0, x0p]  # px0-1, px0, px0+1で割ったもの

first_mod = []  # 後ろから順番に1回だけ操作を行ったときの数字(Xi % popcount(Xi))
for i, bit in enumerate(reversed(X)):
    if bit == '0':
        # 1に反転する
        first_mod.append((x0[2] + pow(2, i, px0p)) % (px0p))
    elif bit == '1':
        if px0n != -1:
            first_mod.append((x0[0] - pow(2, i, px0n)) % (px0n))
        else:
            first_mod.append(-1)


# print(first_mod[::-1], sep='\n')  # これが違うぞーなんでだ
# これは必ずpx0+-1よりも小さいので、事前に対応表を作っておけばすぐに求められる(それとも求めなくてもいいか？)(logがつくからしなくても良さそう)

ans = []
for x in reversed(first_mod):
    if x == -1:
        ans.append(0)
        continue
    cnt = 1  # すでに一回操作しているので
    while x != 0:
        x = x % bin(x).count('1')
        cnt += 1
    ans.append(cnt)


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

Submission status: Accepted

Solution code:
def f(n):
    cnt = 0
    while n:
        buf = n
        pc = 0
        while buf:
            pc += buf%2
            buf //= 2
        n = n%pc
        cnt += 1
    return cnt

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

v1, v2 = 0, 0
cnt = X.count("1")
for i, j in enumerate(X[::-1]):
    if j=="1":
        v1 += pow(2, i, cnt+1)
        v1 %= (cnt+1)

        if cnt>1:
            v2 += pow(2, i, cnt-1)
            v2 %= (cnt-1)

for i in range(N):
    p = N-i-1
    buf = 0
    c2 = 0
    if X[i]=="0":
        c2 = cnt+1
        buf = (v1+pow(2, p, c2))%c2
        print(f(buf)+1)
    else:
        c2 = cnt-1
        if c2>0:
            buf = (v2-pow(2, p, c2))%c2
            print(f(buf)+1)
        else:
            print(0)

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  s = str(input())
  num_bit = 0
  for i in range(N):
    if s[i] == '1':
      num_bit += 1
  ans_1 = 0#bit 0 to 1のときpopcount (n) = num_bit + 1
  for i in range(N):
    if s[N-1-i] == "1":
      ans_1 += pow(2, i, num_bit+1)
      ans_1 %= (num_bit+1)
  ans_2 = 0
  if num_bit > 1:
    for i in range(N):
      if s[N-1-i] == "1":
        ans_2 += pow(2, i, num_bit-1)
        ans_2 %= (num_bit-1)
  ans = [0] * N
  for i in range(N):
    ans_temp = 1
    if s[N-1-i] == '1':
      if num_bit == 1:
        f = 0
        ans_temp = 0
      else:
        f = ans_2 - pow(2, i, num_bit-1)#1bitだけ1に注意
        f %= (num_bit-1)
    else:
      f = ans_1 + pow(2, i, num_bit + 1)
      f %= (num_bit+1)
    while f != 0:
      f = f % bin(f).count('1')
      ans_temp += 1
    ans[N-1-i] = ans_temp
  for i in ans:
    print(i)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from itertools import repeat

import random

def bitcount(x):
	result = 0
	while x > 0:
		if x % 2 == 1: 
			result += 1

		x //= 2
	return result

ff = {}

def f(x):
	count = 0
	while x != 0:
		count += 1
		#print(x, bitcount(x))
		x = x % bitcount(x)	
	return count

def brute(s):
	chars = [char for char in s]

	result = []

	def flip(i):
		if chars[i] == '1':
			chars[i] = '0'
		else:
			chars[i] = '1'

	for i in range(len(s)):
		flip(i)
		x = int("".join(chars), 2)
		result.append(f(x))
		flip(i)

	return result

def solve(n, s):
	bc = s.count('1')

	x = 0
	pow = 1
	for bit in reversed(range(n)):
		if s[bit] == '1':
			x += pow
		pow *= 2


	mods1 = []
	mod1, mod2 = bc + 1, bc - 1
	mods2 = []

	#print(mod1, mod2)

	pow = 1
	mods1.append(pow % mod1)

	if mod2 != 0:
		mods2.append(pow % mod2)

	for bit in range(1, n):
		if mod1 != 0:
			mods1.append(2 * mods1[bit - 1] % mod1)
		if mod2 != 0:
			mods2.append(2 * mods2[bit - 1] % mod2)

	mods1 = list(reversed(mods1))
	mods2 = list(reversed(mods2))

	#print(mods1)
	#print(mods2)

	x_mod_1 = 0
	x_mod_2 = 0
	for bit in reversed(range(n)):
		if s[bit] == '1':		
			x_mod_1 = (x_mod_1 + mods1[bit]) % mod1
			if mod2 != 0:
				x_mod_2 = (x_mod_2 + mods2[bit]) % mod2

	#print(x_mod_1, x_mod_2)

	result = []

	for bit in reversed(range(n)):
		if s[bit] == '0':
			new_mod = (x_mod_1 + mods1[bit]) % mod1
			result.append(1 + f(new_mod))

		else:
			if mod2 == 0:
				result.append(0)
			else:				
				new_mod = (x_mod_2 - mods2[bit]) % mod2
				#print('new mod', new_mod)
				result.append(1 + f(new_mod))

	return list(reversed(result))


#n = 200000
n = int(input())
s = input()
#s = "".join(list(repeat('1', n)))

sol = solve(n, s)
for x in sol:
	print(x)

#print(brute(s))

Submission status: Accepted

Solution code:
N = int(input())
X = input()
def popcount(n):
    tmp = n
    cnt = 0
    while tmp:
        cnt += tmp % 2
        tmp >>= 1
    return cnt
def f(n):
    tmp = n
    cnt = 0
    while tmp:
        cnt += 1
        ff = popcount(tmp)
        tmp %= ff
    return cnt
cnt = 0
LL = [0 for _ in range(200010)]
for i in range(200010):
    LL[i] = f(i)
for i in range(N):
    cnt += X[i] == '1'
A = [1 for _ in range(N+1)]
B = [1 for _ in range(N+1)]
for i in range(N):
    A[i+1] = A[i] << 1
    A[i+1] %= cnt + 1
for i in range(N):
    B[i+1] = B[i] << 1
    if cnt > 1:
        B[i+1] %= cnt - 1
    else:
        B[i+1] = 0
S = 0
T = 0
for i in range(N):
    S += X[i] == '1'
    T += X[i] == '1'
    if i != N-1:
        S <<= 1
        T <<= 1
        S %= cnt + 1
        if cnt > 1:
            T %= cnt - 1
        else:
            T = 0
C = [S for _ in range(N)]
D = [T for _ in range(N)]
for i in range(N):
    if X[i] == '1':
        D[i] -= B[N-1-i]
        if cnt == 1:
            print(0)
        else:
            D[i] %= cnt - 1
            print(LL[D[i]]+1)
    else:
        C[i] += A[N-1-i]
        C[i] %= cnt + 1
        print(LL[C[i]]+1)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""





n = onem()

po = input()
#num = int("0B" + po,0)
co = po.count("1")

num = [0,0]

for i in range(n):
	num[0] *= 2
	num[1] *= 2
	if po[i] == "1":
		num[0] += 1
		num[1] += 1
	if co > 1:
			num[0] %= co-1
	num[1] %= co+1
	

for i in range(n):
	if po[i] == "0":
		coco = co + 1

		ima = num[1] + pow(2,(n-1-i),coco)
		ima %= coco
		coco = format(ima,"b").count("1")
		count = 1
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				"""
				if ima >= 10**5 + 1:
					coco = dp[ima-(10**5 + 1)]
				else:
				"""
				coco = format(ima,"b").count("1")

	else:
		coco = co - 1
		if coco == 0:
			count = 0
			print(count)
			continue
		ima = num[0] - pow(2,(n-1-i),coco)
		ima %= coco
		count = 1
		coco = format(ima,"b").count("1")
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				"""
				if ima >= 10**5 + 1:
					coco = dp[ima-(10**5 + 1)]
				else:
				"""
				coco = format(ima,"b").count("1")
	print(count)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()

	a=[0]*(2*10**5+100)
	for i in range(1,2*10**5+50):
		b=bin(i).count("1")
		a[i]=a[i%b]+1
	#print(a)

	s=input()
	c=s.count("1")
	#print(c)

	if c==1:
		ans=[]
		for i,ss in enumerate(reversed(s)):
			if ss=="1":
				ans.append(0)
			else:
				if s[-1]=="1" or i==0:
					ans.append(2)
				else:
					ans.append(1)

		for i in reversed(ans):
			print(i)
		exit()


	p=c+1
	n=c-1
	pp=0
	nn=0

	for i,ss in enumerate(reversed(s)):
		#print(i)
		if ss=="1":
			pp+=pow(2,i,p)
			nn+=pow(2,i,n)
			pp%=p
			nn%=n


	ans=[]

	for i,ss in enumerate(reversed(s)):
		if ss=="0":
			k=pp+pow(2,i,p)%p
			k%=p
			ans.append(a[k]+1)
		else:
			k=nn-pow(2,i,n)%n
			k%=n
			ans.append(a[k]+1)

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






if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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


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


f = defaultdict(int)
for i in range(1, N + 1):
    f[i] = f[i % popcount(i)] + 1

P = X.count('1')
base = dict()
R = defaultdict(int)
for r in [P - 1, P + 1]:
    if r == 0:
        continue
    base[r] = [1] * N
    for i in range(1, N):
        base[r][i] = base[r][i - 1] * 2 % r
    R[r] = sum(base[r][i] * int(X[i]) for i in range(N)) % r

ans = [0] * N
for i in range(N):
    if X[i] == '1' and P == 1:
        ans[i] = 0
        continue
    if X[i] == '0':
        r = P + 1
        res = R[r] + base[r][i]
    else:
        r = P - 1
        res = R[r] - base[r][i]
    ans[i] = f[res % r] + 1

for i in range(N):
    print(ans[N - i - 1])

Submission status: Accepted

Solution code:
arr=[0,1,1,2]
n=4*(10**5)+100
for i in range(4,n):
    b=bin(i)[2:]
    k=b.count('1')
    arr.append(arr[i%k]+1)
    #print(b,arr[i])
n=int(input())
z=input()
l=z.count('1')
l1=l+1
l2=l-1
ans1=0
ans2=0
for i in range(n):
    if(z[i]=='1'):
        u=pow(2,n-1-i,l1)
        ans1=(ans1+u)%l1
        if l2>0:
            ans2=(ans2+pow(2,n-1-i,l2))%l2
for i in range(n):
    if z[i]=='0':
        p=ans1+pow(2,n-1-i,l1)
        p%=l1
        print(1+arr[p])
    else:
        if l2==0:
            print(0)
        else:
            p=ans2-pow(2,n-1-i,l2)
            p%=l2
            print(1+arr[p])

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
l=[1]*(2*10**5+2)
for i in range(1,2*10**5+1):
    l[i]=l[i%str(bin(i)).count("1")]+1
deka=0
for i in range(n):
    if x[i]=="1":
        deka+=pow(2,n-i-1,c+1)
        deka%=c+1
tiisa=0
if c!=1:
    for i in range(n):
        if x[i]=="1":
            tiisa+=pow(2,n-i-1,c-1)
            tiisa%=c-1

for i in range(n):
    if x[i]=="0":
        nex=(deka+pow(2,n-i-1,c+1))%(c+1)
    else:
        if c-1==0:
            nex=-1
        else:
            nex=(tiisa-pow(2,n-i-1,c-1))%(c-1)
    if nex==0:
        print(1)
    elif nex==-1:
        print(0)
    else:
        print(l[nex])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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

def f(y):
    cnt  = 0
    tmp = y
    while tmp:
        tmp = tmp%popcnt(tmp)
        cnt += 1
    return cnt

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

cc = 0
for e in x:
    if e == '1':
        cc += 1

if cc == 0:
    for i in range(n):
        print(1)
    exit()
if cc == 1:
    p = 1
    q = 1
    #xをccで割った時の余り
    s = 0
    #xをcc-1で割った時の余り
    t = 0

    for i in range(n-1,-1,-1):
        if x[i] == '1':
            s = (s+p)%(cc+1)
        p = p*2%(cc+1)




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


p = 1
q = 1
#xをccで割った時の余り
s = 0
#xをcc-1で割った時の余り
t = 0

for i in range(n-1,-1,-1):
    if x[i] == '1':
        s = (s+p)%(cc+1)
        t = (t+q)%(cc-1)
    p = p*2%(cc+1)
    q = q*2%(cc-1)



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

Submission status: Accepted

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

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

A=int(X,2)
#apは0->1の時の一回目の変換の値。
ap=A%(k+1)

am=100
if k != 1:
  am=A%(k-1)

popc_list=[-1]*(k+3)

def F(num):
  #print(str(num)+"called")
  if num==0:
    return 0
  if popc_list[num]!=-1:
    return popc_list[num]
  
  popc=0
  for s in bin(num):
    if s == "1":
      popc+=1
      
  popc_list[num]=F(num%popc)+1
  return popc_list[num]
  

for i in range(N):
  if X[i] == "0":
    print(F((ap+pow(2,N-1-i,k+1))%(k+1))+1)
  else:
    if k == 1:
      print(0)
      continue
    print(F((am-pow(2,N-1-i,k-1))%(k-1))+1)
"""
print(popc_list)
print(k)
"""

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007

def solve(n):
    ans = 0
    while(n > 0):
        tmp = n
        pc = 0
        # print("wait")
        while(tmp > 0):
            if tmp % 2 == 1:
                pc += 1
            tmp //= 2
        n = n % pc
        ans += 1

    return ans



def main():
    n = getN()
    S = getS()
    N = int(S, 2)
    yobi = []

    for i in range(0, 200200):
        ret = solve(i)
        yobi.append(ret)
    # print(yobi)

    tmp = N
    pc = 0
    # print("N", N)
    pc = Counter(S)["1"]

    start1 = N % (pc + 1)
    rui1 = [1 % (pc + 1)]
    for i in range(n + 2):
        rui1.append((rui1[-1] * 2) % (pc + 1))
    if pc > 1:
        start2 = N % (pc - 1)
        rui2 = [1 % (pc - 1)]
        for i in range(n+2):
            rui2.append((rui2[-1] * 2) % (pc - 1))

    # print(start1, start2, pc)
    # print(rui1)
    # print(rui2)
    for i, c in enumerate(S):
        if c == "0":
            nx = (start1 + rui1[n - i - 1]) % (pc + 1)
            print(yobi[nx] + 1)
        if c == "1":
            if pc == 1:
                print(0)
            else:
                nx = (start2 - rui2[n - i - 1]) % (pc - 1)
                print(yobi[nx] + 1)

    # print(int("".join(["1" for i in range(200200)])) % 1)

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

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
#import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s, n, node):
    # 頂点が探索済みかどうかのチェック配列
    check = [False for _ in range(n)]
    check[s] = True
    # 次見る頂点を格納するキュー
    queue = deque([s])
    visited_num = 1

    # 問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color = [-1 for _ in range(n)]
    color[s] = 0

    while visited_num < n:
        # グラフが全連結ではない場合
        if len(queue) == 0:
            # 空配列を返す
            # 現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex = queue.popleft()
        # インデックスがない場合は
        for next_vertex in node[now_vertex]:

            if check[next_vertex] == True:
                continue

            queue.append(next_vertex)
            check[next_vertex] = True

            # 問題固有の計算
            color[next_vertex] = color[now_vertex]+1
            visited_num += 1

    return color


mod = 10**9+7
# n=int(input())
# n,m=list(map(int,input().split()))
# a=list(map(int,input().split()))
def ceil(x, y): return (x+y-1)//y
def input_list(): return list(map(int, input().split()))


n = int(input())
tmp = input()

x = int(tmp, 2)
bit_num = tmp.count("1")
#bit = x % bit_num
p_bit = x % (bit_num+1)
m_bit_flg = False
if bit_num < 2:
    m_bit_flg = True
else:
    m_bit = x % (bit_num-1)

for i in range(n):
    if tmp[i] == "0":
        cal = (p_bit+pow(2, n-i-1, bit_num+1)) % (bit_num+1)
    else:
        if m_bit_flg:
            print(0)
            continue
        cal = (m_bit-pow(2, n-i-1, bit_num-1)) % (bit_num-1)
    ans = 1
    while(cal > 0):
        cal = cal % bin(cal).count("1")
        ans += 1
    # print(cal_bit_num)
    # print(bin(cal))
    print(ans)
    # exit()

Submission status: Accepted

Solution code:
N = int(input())
X = input()
p0 = X.count('1')
p1, p2 = p0-1, p0+1
mem = {0:0}
def f(n):
    if n in mem:
        return mem[n]
    else:
        p = bin(n).count('1')
        ret = f(n % p) + 1
        mem[n] = ret
        return ret
r1 = r2 = 0
k1 = k2 = 1
for i in range(N):
    if X[-i-1] == '1':
        if p1 > 0:
            r1 = (r1+k1) % p1
        r2 = (r2+k2) % p2
    if p1 > 0:
        k1 = k1 * 2 % p1
    k2 = k2 * 2 % p2

ans = [None]*N
k1 = k2 = 1
for i in range(N):
    if X[-i-1] == '0':
        r = (r2 + k2) % p2
        ans[-i-1] = f(r) + 1
    elif p1 > 0:
        r = (r1 - k1) % p1
        ans[-i-1] = f(r) + 1
    else:
        ans[-i-1] = 0
    if p1 > 0:
        k1 = k1 * 2 % p1
    k2 = k2 * 2 % p2
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
n = int(input())
x = input()
temp = x.count("1")
mod1 = [1]
for i in range(n-1):
    mod1.append(mod1[-1] * 2 % (temp + 1))
mod1.reverse()
num1 = 0
for i in range(n):
    if x[i] == "1":
        num1 += mod1[i]
        num1 %= (temp + 1)
if temp == 1 or temp == 2:
    mod2 = [0] * n
else:
    mod2 = [1]
    for i in range(n-1):
        mod2.append(mod2[-1] * 2 % (temp - 1))
    mod2.reverse()
    num2 = 0
    for i in range(n):
        if x[i] == "1":
            num2 += mod2[i]
            num2 %= (temp - 1)
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        if temp == 1:
            print(0)
            continue
        elif temp == 2:
            print(1)
            continue
        else:
            num = num2 - mod2[i]
            num %= (temp - 1)
    else:
        num = num1 + mod1[i]
        num %= (temp + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
S = input()

flag_m = [0]*(N)
#flag = [0]*(N)
flag_p = [0]*(N)
keta_list_m = [0]*(N)
#keta_list = [0]*(N)
keta_list_p = [0]*(N)

mod = S.count('1')

if mod == 1:
    flag_p[-1] = int(S[-1]) % (mod+1)
    keta_list_p[-1] = 1 % (mod+1)
    keta_p = 1
    for i in reversed(range(N-1)):
        keta_p *= 2
        keta_p %= (mod+1)
        keta_list_p[i] = keta_p
        if S[i] == '1':
            flag_p[i] = keta_p
    sum_f_p = sum(flag_p)

    for i in range(N):
        if S[i] == '1':
            print(0)
            continue
        else:
            num = (sum_f_p + keta_list_p[i]) % (mod+1)
    
        ans = 1
        if num == 0:
            print(ans)
            continue

        while True:
            cnt = 0
            tmp = 0
            while (1 << tmp) <= num:
                if num & 1 << tmp:
                    cnt += 1
                tmp += 1
            num %= cnt
            ans += 1
            if num == 0:
                print(ans)
                break
    exit()

flag_p[-1] = int(S[-1]) % (mod+1)
flag_m[-1] = int(S[-1]) % (mod-1)
keta_list_p[-1] = 1 % (mod+1)
keta_list_m[-1] = 1 % (mod-1)
keta_m = 1
keta_p = 1
for i in reversed(range(N-1)):
    keta_m *= 2
    keta_m %= (mod-1)
    keta_p *= 2
    keta_p %= (mod+1)
    keta_list_m[i] = keta_m
    keta_list_p[i] = keta_p
    if S[i] == '1':
        flag_p[i] = keta_p
        flag_m[i] = keta_m

sum_f_m = sum(flag_m)
sum_f_p = sum(flag_p)
#print(mod)
#print(flag)
for i in range(N):
    if S[i] == '1':
        num = (sum_f_m - keta_list_m[i]) % (mod-1)
    else:
        num = (sum_f_p + keta_list_p[i]) % (mod+1)
    #print('k', num)

    ans = 1
    if num == 0:
        print(ans)
        continue

    while True:
        cnt = 0
        tmp = 0
        while (1 << tmp) <= num:
            if num & 1 << tmp:
                cnt += 1
            tmp += 1
        num %= cnt
        ans += 1
        if num == 0:
            print(ans)
            break

Submission status: Accepted

Solution code:
n = int(input())
s = input()
st = 0
for i in range(n):
    st += int(s[i])
#print(st)
if st == 1:
    if s[-1] == '1':
        for _ in range(n-1):
            print(2)
        print(0)
    else:
        for i in range(n):
            if s[i] == '1':
                print(0)
            elif i == n-1:
                print(2)
            else:
                print(1)
    exit()
m1 = [1]
p1 = [1]
for i in range(n-1):
    m1.append(m1[-1]*2%(st-1))
    p1.append(p1[-1]*2%(st+1))
if st-1 == 1:
    m1[0] = 0
if st+1 == 1:
    p1[0] = 0
m1.reverse()
p1.reverse()
#print(m1)
#print(p1)
ansm = 0
ansp = 0
for i in range(n):
    ansm += m1[i] * int(s[i])
    ansp += p1[i] * int(s[i])
#print(ansm)
#print(ansp)
time = [0 for _ in range(20)]
def nex(time):
    for i in range(20):
        if time[i] == 0:
            time[i] += 1
            return time
        else:
            time[i] = 0
ans = [0 for _ in range(200001)]
time2 = 1
time[0] = 1
while time2 <= 200000:
    #print(time,time2)
    ans[time2] = ans[time2 % sum(time)] + 1
    time = nex(time)
    time2 += 1
#print([i for i in range(20)])
#print(ans[:20])
for i in range(n):
    if s[i] == '1':
        use = (ansm-m1[i]) % (st-1)
    else:
        use = (ansp+p1[i]) % (st+1)
    print(1+ans[use])

Submission status: Accepted

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

M = 2 * (10 ** 5) + 10
ret = [0] * (M + 1)
for i in range(M + 1) :
  x = i
  c = 0
  while x != 0 :
    x = x % bin(x).count('1')
    c += 1
  ret[i] = c
  
p = bin(X).count('1')
a = X % (p + 1)
if p > 1 :
  b = X % (p - 1)

for i in range(N - 1, -1, -1) :
  if (1 << i) & X :
    if p == 1 :
      print(0)
    else :
      print(ret[(b - pow(2, i, p - 1)) % (p - 1)] + 1)
  else :
    print(ret[(a + pow(2, i, p + 1)) % (p + 1)] + 1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

m = 2*10**5+10
ans = [0] * m
for i in range(1,m):
    nnow = i
    res = 0
    stnow = bin(nnow).count('1')
    while nnow:
        # print(nnow)
        nnow %= stnow
        stnow = bin(nnow).count('1')
        res += 1
    ans[i] = res
# for i in range(10):
#     print(i,ans[i])
n = inp()
s = list(input())
tmp = s.count('1')
stm = tmp-1
stp = tmp+1
numm = 0
nump = 0
for i,x in enumerate(s):
    if x == '1': 
        nump += pow(2,n-i-1,stp)
        nump %= stp
        if stm > 0:
            numm += pow(2,n-i-1,stm)
            numm %= stm

for i in range(n):
    if s[i] == '0':
        nnow = (nump+pow(2,n-i-1,stp))%stp
    else:
        if stm <= 0:
            print(0)
            continue
        nnow = (numm-pow(2,n-i-1,stm))%stm
    # print(nnow)
    print(ans[nnow]+1)