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 main():

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

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

    if p == 0:
        ans = [1]*n
        for i in range(n):
            print(ans[i])
        exit()

    if p == 1:
        ans = [0]*n
        for i in range(n):
            if x[i] == '1':
                ans[i] = 0
            else:
                if i != n-1:
                    if x[-1] != 1:
                        ans[i] = 1
                    else:
                        ans[i] = 2
                else:
                    ans[i] = 2
        for i in range(n):
            print(ans[i])
        exit()

    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

    X1 = 0
    X2 = 0
    import copy
    s = copy.copy(x)
    s.reverse()
    #print(s)
    for i in range(n):
        if s[i] == '1':
            X1 += power(2, i, p+1)
            X2 += power(2, i, p-1)

    #print(p)
    #print(X1)
    #print(X2)
    ans = [0]*n
    for i in range(n):
        if x[i] == '0':
            temp = X1
            temp += power(2, n-1-i, p+1)
            temp %= (p+1)
            if temp == 0:
                ans[i] = 1
                continue
            cnt = 0
            d = p+1
            while temp:
                cnt += 1
                temp %= d
                b = format(temp, 'b')
                d = 0
                for j in range(len(b)):
                    if b[j] == '1':
                        d += 1
        else:
            temp = X2
            temp -= power(2, n-1-i, p-1)
            temp %= (p-1)
            if temp == 0:
                ans[i] = 1
                continue
            cnt = 0
            d = p-1
            while temp:
                cnt += 1
                temp %= d
                b = format(temp, 'b')
                d = 0
                for j in range(len(b)):
                    if b[j] == '1':
                        d += 1
        ans[i] = cnt
    #print(*ans)
    for i in range(n):
        print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

pop = [0]*(N+1)
amari = [0]*(N+1)
for i in range(1,N+1):
    pop[i]=pop[i-(i&(-i))]+1
    amari[i] = amari[i%pop[i]]+1

cnt1 = 0
for i in range(N):
    if X[i]=="1":
        cnt1+=1
Y = cnt1+1
Z = cnt1-1

baseY = 0
baseZ = 0
for i in range(N):
    K = int(X[N-1-i])
    if K==1:
        baseY += pow(2,i,Y)
        if Z!=0:
            baseZ += pow(2,i,Z)
        else:
            baseZ =-1
baseY = baseY%Y
if Z!=0:
    baseZ = baseZ%Z
else:
    baseZ = -1

for i in range(N):
    if X[i]=="0":
        out = (baseY + pow(2,N-1-i,Y))%Y
        print(amari[out]+1)
    elif X[i]=="1":
        if Z!=0:
            out = (baseZ - pow(2,N-1-i,Z))%Z
            print(amari[out]+1)
        else:
            print(0)

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int, list(input())))
X.reverse()
def int2bit(n):
	ret = [0 for i in range(18)]
	cnt = 0
	i = 0
	while n > 0:
		ret[i] = n % 2
		cnt += n % 2
		n = n // 2
		i += 1
	return (ret, cnt)

def func(bit, popcount):
	ret = 0
	base = 1
	for b in bit:
		ret = (ret + base*b) % popcount
		base = (base * 2) % popcount
	return ret

def func2(n):
	(bit, popcount) = int2bit(n)
	return func(bit, popcount)

F = [0 for _ in range(N+1)]

for n in range(1, N+1):
	a = func2(n)
	F[n] = 1 + F[a]
P = sum(X)

f_1 = func(X, P+1)
f_0 = func(X, max(1, P-1))

base_1 = [1]
base_0 = [1]
for i in range(N-1):
	base_1.append((base_1[i] * 2) % (P+1))
	base_0.append((base_0[i] * 2) % max(1, P-1))
for i in range(N):
	idx = N - 1 - i
	if X[idx] == 0:
		print(1 + F[(f_1 + base_1[idx]) % (P+1)])
	if X[idx] == 1:
		if P == 1:
			print(0)
		else:
			print(1 + F[(f_0 - base_0[idx]) % (P-1)])

Submission status: Accepted

Solution code:
def popcount(n):
    ans=0
    for i in range(20):
        if n>>i & 1:
            ans+=1
    return ans

N=int(input())
X=input()
n=0

for i in range(N):
    if X[i]=='1':
        n+=1
np1=0
nm1=0
temp1=1
temp2=1
nm=n-1
if nm==0:
    nm=1
for i in range(N-1,-1,-1):
    if X[i]=='1':
        np1=(np1+temp1)%(n+1)
        nm1=(nm1+temp2)%nm
    temp1=(temp1*2)%(n+1)
    temp2=(temp2*2)%nm
    
for i in range(N):
    ans=1
    if X[i]=='1':
        if n==1:
            print(0)
            continue
        temp=(nm1-pow(2,(N-1-i),n-1))%(n-1)
        while temp>0:
            pop_n=popcount(temp)
            temp=temp%pop_n
            ans+=1
    elif X[i]=='0':
        temp=(np1+pow(2,(N-1-i),n+1))%(n+1)
        while temp>0:
            pop_n=popcount(temp)
            temp=temp%pop_n
            ans+=1
    print(ans)

Submission status: Accepted

Solution code:
#create date: 2020-07-11 21:18

import sys
stdin = sys.stdin

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

def popcount(m):
    res = 0
    while m:
        if m & 1:
            res += 1
        m //= 2
    return res
def f(m):
    cnt = 0
    while m:
        #print("test", m)
        m = m % popcount(m)
        cnt += 1
    return cnt

def main():
    n = ni()
    x = ns()
    pop0 = x.count("1") + 1
    pop1 = x.count("1") - 1
    y0 = 0; y1 = 0
    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "1":
            y0 += pow(2, r, pop0)
            y0 %= pop0
            if pop1 != 0:
                y1 += pow(2, r, pop1)
                y1 %= pop1

    for i, xi in enumerate(x):
        r = n - i - 1
        if xi == "0":
            m = (y0 + pow(2, r, pop0)) % pop0
            print(f(m) + 1)
        else:
            if pop1 == 0:
                print(0)
                continue
            m = (y1 - pow(2, r, pop1)) % pop1
            print(f(m) + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())
# 文字列の入力
X = input()
one = 0
intX = 0
bitnow = 1
for i in reversed(range(len(X))):
    if X[i] == '1':
        one += 1
        intX += bitnow
    bitnow *= 2
hi = one + 1
lo = one - 1
hirembase = intX % hi
lorembase = 0
if lo != 0:
    lorembase = intX % lo
# print(intX)
# print(hi)
# print(lo)
# print(hirembase)
# print(lorembase)
bo = []
for i in range(200010):
    num = 0
    while i != 0:
        bit = bin(i)
        bitnum = 0
        for j in range(len(bit)):
            if j == 0 or j == 1:
                continue
            if bit[j] == '1':
                bitnum += 1
        i = i % bitnum
        num += 1
    bo.append(num)
ans = []
hirem = 1
lorem = 1
for i in reversed(range(len(X))):
    if X[i] == '0':
        num = (hirembase + hirem + hi) % hi
        ans.append(bo[num] + 1)
    else:
        if one == 1:
            ans.append(0)
        else:
            num = (lorembase - lorem + lo) % lo
            ans.append(bo[num] + 1)
    hirem = (hirem * 2) % hi
    if one != 1:
        lorem = (lorem * 2) % lo
# print(ans)
# 出力
for i in reversed(range(len(ans))):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a, b = numX % (popcount_X + 1), numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1):
    if x == '1' and popcount_X == 1:
        print(0); continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1')
        temp %= p
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    N=int(sys.stdin.readline())
    X=sys.stdin.readline()

    no=X.count('1')
    np=no+1
    nm=no-1
    nm_flag=bool(nm)

    np_mods=[-1]*N
    nm_mods=[-1]*N
    
    np_mods[0]=1
    nm_mods[0]=1
    
    for i in range(1,N):
        np_mods[i]=(np_mods[i-1]*2)%np
        if nm_flag:
            nm_mods[i]=(nm_mods[i-1]*2)%nm

    np_mods.reverse()
    nm_mods.reverse()
    
    np_mods_sum=0
    nm_mods_sum=0
    for i in range(N):
        if X[i]=='1':
            np_mods_sum+=np_mods[i]
            nm_mods_sum+=nm_mods[i]

    for i in range(N):
        if X[i]=='0':
            n=(np_mods_sum+np_mods[i])%np

        else:
            if nm_flag:
                n=(nm_mods_sum-nm_mods[i])%nm
            else:
                print(0)
                continue
        if n==0:
            print(1)
            continue
        count=1
        while True:
            bs=str(bin(n))[2:]
            k=bs.count('1')
            n=n%k
            count+=1
            if n==0:
                break
        print(count)

main()

Submission status: Accepted

Solution code:
N = int(input())
X = input()
tmp = sum(X[i] == '1' for i in range(N))

for_zero = tmp + 1
for_one = tmp - 1
zero_S = 0
one_S = 0


numbers = [0] * N
counts = [1] * N

if tmp == 1:
    for i in range(N):
        if X[i] == '1':
            counts[i] = 0
    # =====================first sweep
    tmp_zero = 1
    for i in range(N):
        if X[-i - 1] == '1':
            zero_S += tmp_zero
            zero_S %= for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero

    # =====================second sweep
    tmp_zero = 1
    for i in range(N):
        if X[-i - 1] == '1':
            pass
        else:
            numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero

else:
    # =====================first sweep
    tmp_zero = 1
    tmp_one = 1
    for i in range(N):
        if X[-i - 1] == '1':
            one_S += tmp_one
            one_S %= for_one
            zero_S += tmp_zero
            zero_S %= for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero
        tmp_one *= 2
        tmp_one %= for_one

    # =====================second sweep
    tmp_zero = 1
    tmp_one = 1
    for i in range(N):
        if X[-i - 1] == '1':
            numbers[-i - 1] = (one_S - tmp_one) % for_one
        else:
            numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero
        tmp_one *= 2
        tmp_one %= for_one




def solution(number):
    loop = 0
    while number != 0:
        popcount = 0
        for i in range(30):
            if (1 << i) & number:
                popcount += 1
        number %= popcount
        loop += 1
    return loop

for i in range(N):
    counts[i] += solution(numbers[i])

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

Submission status: Accepted

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

import sys
input=sys.stdin.readline


LEN=2*10**5+10

moves=[0]*LEN
for i in range(1,LEN):
  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 bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X=input()
XX=int(X,2)
m=X.count('1')
if m-1>0:
    l=[XX%(m+1),(XX%(m-1))]
else:
    l=[XX%(m+1),0]
for i in range(N):
    if X[i]=='0':
        n=l[0]+pow(2,(N-1)-i,m+1)
        n%=m+1
    else:
        if m-1==0:
            print(0)
            continue
        n=l[1]-pow(2,(N-1)-i,m-1)
        n%=m-1
    ans=1
    while n>0:
        n%=bin(n).count('1')
        ans+=1
    print(ans)

Submission status: Accepted

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

def main():
    from sys import stdin, stdout
    input = stdin.readline
    print = stdout.write
    n = int(input())
    x = input().rstrip()
    pc = sum(1 for i in x if i == '1')
    xint = int(x, 2)
    lpc = [1 for i in range(n)]
    upc = [1 for i in range(n)]
    dp = [1 for i in range(n+1)]
    for i in range(1, n+1):
        dp[i] = dp[i % popcount(i)] + 1
    lmod = xint % (pc - 1) if pc >= 2 else -1
    rmod = xint % (pc + 1)
    if pc >= 2:
        for i in range(1, n):
            lpc[i] = (lpc[i - 1] * 2) % (pc - 1)
    for i in range(1, n):
        upc[i] = (upc[i - 1] * 2) % (pc + 1)
    for i in range(n - 1, -1, -1):
        if x[n-1-i] == '1':
            if pc == 1:
                print('0\n')
            else:
                print('%d\n' % (dp[(lmod - lpc[i]) % (pc-1)]))
        else:
            print('%d\n' % (dp[(rmod + upc[i]) % (pc+1)]))

main()

Submission status: Accepted

Solution code:
n = int(input())
x = list(input())
c1 = x.count("1")+1
c2 = c1-2

now1 = 0
now2 = 0

for i in range(n):
    if x[-1-i] == "1":
        now1 += pow(2,i,c1)
        if c2 != 0:
            now2 += pow(2,i,c2)
        
    now1 %= c1
    if c2 != 0:
        now2 %= c2

for i in range(n):
    if x[i] == "1":
        #print(n-1-i)
        if c2 == 0:
            print(0)
            continue
        now = (now2-pow(2,n-1-i,c2))%c2
        #print(i,now,c2)
        count = 1
        while now > 0:
            q = bin(now)
            y = q.count("1")
            now %= y
            count += 1
        print(count)
    else:
        #print(n-1-i)
        now = (now1+pow(2,n-1-i,c1))%c1
        #print(i,now,c1)
        count = 1
        while now > 0:
            q = bin(now)
            y = q.count("1")
            now %= y
            count += 1
        print(count)

Submission status: Accepted

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

def okikae(n):
    kaisu = 0
    if n == 0:
        return 0
    while 1:
        P = popcnt1(n)
        n %= P
        kaisu += 1
        if n == 0:
            return kaisu

OKI = [okikae(i) for i in range(200001)]
X = int(input())
Norig = input()
N = int(Norig,2)
Npop = Norig.count("1")
F = Npop + 1
H = Npop - 1
if H == 0:
    H = -1
FueAmari = N%(Npop + 1)
if Npop != 1:
    HeruAmari = N%(Npop - 1)
else:
    HeruAmari = -1
Fues = []
Herus = []
fue = 1
heru = 1
for i in range(2*(10**5+1)):#2^0の桁から
    fue %= F
    heru %= H
    Fues.append(fue)
    Herus.append(heru)
    fue *= 2
    heru *= 2
RNorig = reversed(Norig)
Results = []
Zougen = []#増えたらTrue
Kaisu = [0] * X
#上の桁から見ていく。ゼロなら減ってイチなら増える
for n,bit in enumerate(Norig):#2**(N-1-n)の桁
    if bit == "0":#増える
        Zougen.append(True)
        print(1+OKI[(FueAmari + Fues[X-1-n] )% F])
    else:
        if H == -1:
            print(0)
            continue
        Zougen.append(False)
        print(1+OKI[(HeruAmari - Herus[X-1-n]) % H])

Submission status: Accepted

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

dp = [0] * n
for i in range(1, n-1):
    tmp = i
    cnt = 0
    while tmp > 0:
        cnt += tmp % 2
        tmp //= 2
    dp[i] = dp[i%cnt] + 1

c = x.count('1')

if c == 1:
    dp_2 = [0] * n
    dp_2[0] = 1 % (c + 1)
    for i in range(1, n):
        dp_2[i] = (2 * dp_2[i-1]) % (c + 1)

    mod_2 = 0
    for i in range(n):
        if x[i] == '1':
            mod_2 = (mod_2 + dp_2[n-i-1]) % (c + 1)

    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            mod = (mod_2 + dp_2[n-i-1]) % (c + 1)
            print(dp[mod] + 1)
else:
    dp_1 = [0] * n
    dp_2 = [0] * n
    dp_1[0] = 1 % (c - 1)
    dp_2[0] = 1 % (c + 1)
    for i in range(1, n):
        dp_1[i] = (2 * dp_1[i-1]) % (c - 1)
        dp_2[i] = (2 * dp_2[i-1]) % (c + 1)

    mod_1 = 0
    mod_2 = 0
    for i in range(n):
        if x[i] == '1':
            mod_1 = (mod_1 + dp_1[n-i-1]) % (c - 1)
            mod_2 = (mod_2 + dp_2[n-i-1]) % (c + 1)

    for i in range(n):
        if x[i] == '1':
            mod = (mod_1 - dp_1[n-i-1]) % (c - 1)
            print(dp[mod] + 1)
        else:
            mod = (mod_2 + dp_2[n-i-1]) % (c + 1)
            print(dp[mod] + 1)

Submission status: Accepted

Solution code:
import sys, math, copy
sys.setrecursionlimit(10**8)

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    A0 = 0
    A1 = 0
    B = sum(x)
    for i in range(n):
        if B+1 != 0:
            A0 += x[i]*pow(2,n-i-1,B+1)
            A0 %= B+1
        if B-1 != 0:
            A1 += x[i]*pow(2,n-i-1,B-1)
            A1 %= B-1
    for i in range(n):
        if x[i] == 0:
            BB = B + 1
            AA = A0 + pow(2,n-i-1,BB)
        else:
            BB = B - 1
            if BB == 0:
                AA = 0
            else:
                AA = A1 - pow(2,n-i-1,BB)
        ans = 1
        if BB == 0:
            print(0)
            continue
        while AA%BB != 0:
            AA = AA%BB
            AAA = AA
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = input()
remain = [None]*(n)
ans = [1]*(n)
one = x.count("1")+1
if one == 2:
    for i in range(n):
        if x[i] == "1":
            ans[i] = 0
            remain[i] = 0

num = 0
for i in range(n-1, -1, -1):
    if x[i] == "1":
        num += pow(2, n-1-i, one)

for i in range(n):
    if x[i] == "0":
        num_temp = num+pow(2, n-1-i, one)
        num_temp %= one
        remain[i] = num_temp


one -= 2
if one == 0:
    pass

else:
    num = 0
    for i in range(n-1, -1, -1):
        if x[i] == "1":
            num += pow(2, n-1-i, one)

    for i in range(n):
        if x[i] == "1":
            num_temp = num-pow(2, n-1-i, one)
            num_temp %= one
            remain[i] = num_temp

for i in range(n):
    if remain[i] != 0:
        rem = remain[i]
        while rem != 0:
            ans[i] += 1
            popcount = format(rem, "b").count("1")
            rem %= popcount

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = input()
d = {}
def sub(val):
    if val in d:
        return d[val]
    pc = 0
    for i in range(val.bit_length()):
        if val>>i&1:
            pc += 1
    if pc==0:
        ans = 0
    else:
        tmp = val % pc
        if tmp==0:
            ans = 1
        else:
            ans = sub(tmp) + 1
    d[val] = ans
    return ans

pc = sum(item=="1" for item in a)
val0 = 0 # pc-1
val1 = 0 # pc+1
for i in range(n):
    if a[i]=="1":
        if pc>1:
            val0 += pow(2,n-1-i,pc-1)
        val1 += pow(2,n-1-i,pc+1)
        
ans = [None]*n
# print(a)
for i in range(n):
    if a[i]=="1":
        if pc==1:
            val = 0
            ans[i] = 0
        else:
            val = (val0 - pow(2,n-1-i,pc-1))%(pc-1) #(1<<(n-1-i))
            ans[i] = sub(val) + 1
#         print(1, bin(val)[2:], pc-1)
    else:
        val = (val1 + pow(2,n-1-i,pc+1))%(pc+1) #(1<<(n-1-i))
        ans[i] = sub(val) + 1
#         print(0, bin(val)[2:], pc+1)
write("\n".join(map(str, ans)))

Submission status: Accepted

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

nxt = [0]*n
zero2one = 0
one2zero = 0

cnt = 0
for i in range(n):
    if x[i]=='1':
        cnt += 1

zero2one = 0
for i in range(n):
    zero2one += int(x[i])*pow(2,n-i-1,cnt+1)
zero2one %= cnt+1

one2zero = 0
if cnt>1:
    for i in range(n):
        one2zero += int(x[i])*pow(2,n-i-1,cnt-1)
    one2zero %= cnt-1

for i in range(n):
    if x[i]=='0':
        nxt[i] = (zero2one + pow(2,n-i-1,cnt+1))%(cnt+1)
    else:
        if cnt>1:
            nxt[i] = (one2zero - pow(2,n-i-1,cnt-1))%(cnt-1)
        else:
            nxt[i] = -1

MX = 2*10**5+5
ans = [0]*MX
for i in range(MX):
    xn = bin(i)[2:]
    res = 0
    while(xn != '0'):
        l = len(xn)
        res += 1
        cnt = 0
        for j in range(l):
            if xn[j]=='1':
                cnt += 1
        after = 0
        for j in range(l):
            after += int(xn[j])*pow(2,l-j-1,cnt)
            after %= cnt
        xn = bin(after)[2:]
    ans[i]=res

for i in range(n):
    if nxt[i]==-1:
        print(0)
    else:
        print(ans[nxt[i]]+1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def all_bit_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f
  
n = int(readline())
d = [0]*(n+1)
d[1] = 1
for i in range(2,n+1):
  q = all_bit_count(i)
  p = i%q
  d[i] = d[p]+1
  
x = input()
c = x.count('1')

a1 = 0
a0 = 0
C = max(1,c-1)
for i,xi in enumerate(x[::-1]):
  if xi == '1':
    a1 += pow(2,i,C)
    a1 %= C
    a0 += pow(2,i,c+1)
    a0 %= (c+1)
    
for i,xi in enumerate(x):
  if xi == '1':
    if c > 1:
      cc = (a1 - pow(2,n-1-i,C))%C
      print(d[cc]+1)
    else:
      print(0)
  else:
    cc = (a0 + pow(2,n-1-i,c+1))%(c+1)
    print(d[cc]+1)

Submission status: Accepted

Solution code:
n = int(input())
x = input()
flg = [0] * n
for i in range(n):
    if x[i] == '1':
        flg[i] = 1
x = int(x, 2)
cnt = sum(flg)
if cnt == 1:
    x_a = 0
else:
    x_a = x % (cnt - 1)
x_b = x % (cnt + 1)


for i in range(n):
    if flg[i] == 1:
        if cnt == 1:
            print(0)
            continue
        t = (x_a - pow(2, n-i-1, cnt-1)) % (cnt - 1)
    else:
        t = (x_b + pow(2, n-i-1, cnt+1)) % (cnt + 1)

    if t == 0:
        print(1)
    else:
        tmp = 1
        while t > 0:
            pop = bin(t).count('1')
            t = t % pop
            tmp += 1

        print(tmp)

Submission status: Accepted

Solution code:
def rem(n, a):
    if a == 0:
        return 0
    ans=0
    for i in n:
        ans*=2
        ans+=i
        ans%=a
    return ans
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
    
n, x = int(input()), list(map(int,input()))

p = x.count(1)
m = [0] * n
q = p - 1
if q!=0:
    m[0] = 1
    for i in range(1, n):
        m[i] = 2 * m[i - 1] % q

w = p + 1
k = [0] * n
k[0] = 1
for i in range(1, n):
    k[i] = 2 * k[i - 1] % w

s = rem(x, q)
t = rem(x, w)
for i in range(n):
    if x[i] == 0:
        a = (t + k[n - i - 1]) % w
        
    else:
        if q == 0:
            print(0)
            continue
        # if i == 3:
        #     print(s,k[n-i-1])
        a = (s - m[n - i - 1]) % q

    cnt = 1
    b = popcnt(a)
    # if i == 3:
    #     print(a,b)
    while b:
        a %= b
        b = popcnt(a)
        cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


import time


INF = float("inf")
MOD = 10**9 + 7


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa

def bit(n, k):
    return (n >> k) & 1

def main():
    start = time.time()
    N = INT()
    X = input()
    origX = X
    wa = X.count("1")
    x = 0
    px = 0
    nx = 0
    start = time.time()
    for c in X:
        x <<= 1
        px <<= 1
        nx <<= 1
        if c == "1":
            x |= 1
            px |= 1
            nx |= 1
        px %= (wa+1)
        if wa != 1:
            nx %= (wa-1)
        else:
            nx %= wa
    if wa == 1:
        nx = None
    # print(time.time()-start)
    # start = time.time()
    X = x
    table = [None]*(N+1)
    table[0] = 0
    table[1] = 1
    for i in range(1, N+1):
        table[i] = table[i % bit_sum(i)] + 1
    # print(time.time()-start)
    # start = time.time()

    for i, c in enumerate(origX):
        count = 0
        if c == "1":
            if wa == 1:
                print(0)
                continue
            x = (nx-pow(2, N-i-1, wa-1)) % (wa-1)
            print(table[x]+1)
        else:
            x = (px+pow(2, N-i-1, wa+1)) % (wa+1)
            print(table[x]+1)
    # print(time.time()-start)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))



n = readint()
x = readstr()

a = int(x,2)

bit = x.count('1')

z = [0]*(n+1)
for i in range(1,n+1):
    b = i
    while b>0:
        c = 0
        for j in range(b.bit_length()):
            if b&(1<<j):
                c += 1
        b%=c
        z[i]+=1

if bit!=1:
    p = a%(bit-1)
q = a%(bit+1)

ans = [1]*n
for i in range(n):
    if x[i]=='1':
        if bit==1:
            b = 0
            ans[i]-=1
        else:
            b = p-pow(2,n-i-1,bit-1)+bit-1
            b%=bit-1
    else:
        b = q+pow(2,n-i-1,bit+1)
        b%=bit+1
    ans[i]+=z[b]

printrows(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def popcorn(i,k):
    num = 0
    ii = i
    while ii > 0:
        if ii&1:
            num += 1
        ii //= 2
    if i%num:
        return popcorn(i%num,k+1)
    else:
        return k+1

def main():
    n = int(ipt())
    x = list(map(int,list(input())))
    si = sum(x)
    su = si+1
    sd = max(1,si-1)
    amu = 0
    amd = 0
    n2u = [1]
    if si == 2:
        n2d = [0]
    else:
        n2d = [1]
    for i in x[::-1]:
        if i:
            amu = (amu+n2u[-1])%su
            amd = (amd+n2d[-1])%sd
        n2u.append((n2u[-1]*2)%su)
        n2d.append((n2d[-1]*2)%sd)
    for i,xi in enumerate(x):
        if xi:
            ni = (amd-n2d[-2-i])%sd
            if si == 1:
                print(0)
            elif ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))
        else:
            ni = (amu+n2u[-2-i])%su
            if ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

M = X.count("1")
a = -1
if M==1:
    a = X.index("1")

def f0(X,M):
    if M<=0: return 0
    ret = 0
    for i,x in enumerate(X[::-1]):
        if x=="1" :
            ret += pow(2,i,M)
            ret %= M
    return ret

def f(M):
    if M==0: return 0
    n = bin(M).count("1")
    return 1+f(M%n)

n0 = f0(X,M+1)
n1 = f0(X,M-1)

for i in range(N):
    if M==1 and a==i:
        print(0)
    else:
        if X[i] == "0":
            n = (n0 + pow(2,N-1-i,M+1))%(M+1)
        else:
            n = (n1 - pow(2,N-1-i,M-1))%(M-1)
        print(f(n)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

n = int(input())
x = input()
mod = x.count("1")
flag = (mod == 1)
if mod == 0:
    for i in range(n):
        print(1)
    exit()
@lru_cache(maxsize = n+1)
def f(x):
    if x==0:return 0
    y = x
    cnt = 0
    while y>0:
        cnt += y&1
        y >>= 1
    x %= cnt
    return f(x) + 1
if mod == 1:mod += 2
powmod = [[1%(mod-1)]*n,[1%(mod+1)]*n]

for i in range(n-1):
    powmod[0][i+1] = powmod[0][i]*2%(mod-1)
    powmod[1][i+1] = powmod[1][i]*2%(mod+1)

X = [0,0]
for i,b in enumerate(x[::-1]):
    X[0] += powmod[0][i]*int(b)
    X[1] += powmod[1][i]*int(b)
    X[0] %= mod-1
    X[1] %= mod+1
ans = [0]*n
for i in range(n):
    if flag:
        if x[n-1-i] == "1":
            ans[n-1-i] = 0
        else:
            now = (X[0] + powmod[0][i])%(mod-1)
            ans[n-i-1] = f(now) + 1
        continue
    if x[n-1-i] == "1":
        now = (X[0] - powmod[0][i])%(mod-1)
    else:
        now = (X[1] + powmod[1][i])%(mod+1)
    ans[n-i-1] = f(now) + 1
print("\n".join(str(i) for i in ans))