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: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft

def nxt(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return x % cnt


def count(x):
    s = 0
    while x != 0:
        s += 1
        x = nxt(x)
    return s

def main():
    n = int(input())
    x = input()
    x = int(x, 2)
    for i in range(n):
        y = x ^ (1<<(n-i-1))
        s = count(y)
        print(s)


main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    mem = defaultdict(lambda : None)
    mem[0] = 0
    cnt = defaultdict(lambda : None)
    cnt[0] = 0
    def dfs2(x):
        if cnt[x] is not None:
            return cnt[x]
        cnt[x] = dfs2(x>>1)+(x&1)
        return cnt[x]

    def dfs(x):
        if mem[x] is not None:
            return mem[x]
        p = dfs2(x)
        res = dfs(x%p)+1
        mem[x] = res
        return res
    n = I()
    x = list(map(int, input()))
    s = 0
    p = 1
    for i in range(n):
        s += x[-i-1]*p
        p <<= 1
    p >>= 1
    for i in range(1,n+1):
        x = s^p
        print(dfs(x))
        p >>= 1
    return

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

Submission status: Time Limit Exceeded

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()[:-1]
num = int("0B" + po,0)
co = po.count("1")
for i in range(n):
	if po[i] == "0":
		ima = num + 2**(n-1-i)
		coco = co + 1
		count = 0
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				coco = format(ima,"b").count("1")
	else:
		ima = num - 2**(n-1-i)
		coco = co - 1
		count = 0
		while True:
			if ima == 0:
				break
			else:
				ima %= coco
				count += 1
				coco = format(ima,"b").count("1")
	print(count)

Submission status: Time Limit Exceeded

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

def bin_to_num(st):
    r = 0
    for x in st:
        r *= 2
        if x == '1': r+=1
    return r

def popcount(num):
    x = num
    ret = 0
    while x>0:
        ret += x%2
        x//=2
    return ret

X = bin_to_num(s)

for i in range(n):
    num = X
    if s[i] == '0': num += (1<<(n-i-1))
    else: num -= (1<<(n-i-1))
    ans = 0
    while num:
        pc = popcount(num)
        num %= pc
        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = int(input(), 2)
for i in range(n):
    num = x ^ (2 ** (n - 1 - i))
    count = 0
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase

def main():
    n=int(input())
    num=int(input(),2)
    for i in range(1,n+1):
        ans=0
        nn=num^(1<<(n-i))
        while nn:
            ans+=1
            nn%=bin(nn).count('1')
        print(ans)


BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import Counter

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

@lru_cache()
def _f(n):
    string=bin(n)[2:].zfill(N)
    popcount=Counter(string)['1']
    return n%popcount

def f(n):
    retval=0
    while n!=0:
        retval+=1
        n=_f(n)
    return retval

for i in range(N):
    if X[i]=='1':
        Xi=X[:i]+'0'+X[i+1:]
    else:
        Xi=X[:i]+'1'+X[i+1:]
    n=int(Xi,2)
    print(f(n))

Submission status: Time Limit Exceeded

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)]


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():
    N = INT()
    X = input()
    wa = X.count("1")
    x = 0
    for c in X:
        x <<= 1
        if c == "1":
            x |= 1
    X = x

    for i in range(N):
        count = 0
        x = X ^ (1 << N-i-1)
        while x != 0:
            count += 1
            x %= bit_sum(x)
        print(count)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def solve(X, cnt):
    if X == 0:
        return cnt
    
    X %= bin(X).count('1')
    return solve(X, cnt+1)

for i in range(N):
    print(solve(X ^ 1 << (N - i - 1), 0))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=int(input(),2)
def f(x):
    cnt=0
    for i in bin(x):
        cnt+=i=='1'
    if cnt == 0:
        return 0
    return f(x%cnt)+1
for i in range(n-1,-1,-1):
    print(f(x^(1<<i)))

Submission status: Time Limit Exceeded

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

def bin_to_num(st):
    r = 0
    for x in st:
        r *= 2
        if x == '1': r+=1
    return r

def popcount(num):
    x = num
    ret = 0
    while x>0:
        ret += x%2
        x//=2
    return ret

for i in range(n):
    if s[i] == '0': s = s[:i]+'1'+s[i+1:]
    else: s = s[:i]+'0'+s[i+1:]
    num = bin_to_num(s)
    ans = 0
    while num:
        pc = popcount(num)
        num %= pc
        ans += 1
    print(ans)
    if s[i] == '0': s = s[:i]+'1'+s[i+1:]
    else: s = s[:i]+'0'+s[i+1:]

Submission status: Time Limit Exceeded

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


def popcount(x):
    return x.count('1')


def f(x):
    cnt = 0
    while '1' in x:
        x = bin(int(x, base=2) % popcount(x))[2:]
        cnt += 1

    return cnt


def rev(c):
    if c == '0':
        return '1'
    else:
        return '0'


for i in range(N):
    xi = X[:i] + rev(X[i]) + X[i + 1:]
    print(f(xi))

Submission status: Time Limit Exceeded

Solution code:
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
x=input()
xint=int(x, 2)
ones=0
for i in range(n):
  if x[i]=='1':
    ones+=1
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=xint+pow(2,n-1-i)
    temp1=ones+1
  else:
    temp=xint-pow(2,n-1-i)
    temp1=ones-1
  ans=0
  while temp!=0:
    temp=temp%temp1
    temp2=base10toN(temp,2)
    temp1=0
    for i in range(len(temp2)):
      if temp2[i]=='1':
        temp1+=1
    ans+=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    return f(x % bin(x).count('1')) + 1


n = int(input())
x = int(input(), base=2)
buf = []

for i in range(n):
    buf.append(f(x ^ (1 << i)))

buf.reverse()

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = [int(x) for x in list(input())]
lx = len(x)-1

xx = 0
xx_cnt = 0
for i, y in enumerate(x):
    xx += (1 << (lx-i))*y
    if y == 1:
        xx_cnt += 1

for i in range(n):
    if x[i] == 0:
        val = xx + (1 << (lx-i))*1
        cnt = xx_cnt + 1
    else:
        val = xx - (1 << (lx-i))*1
        cnt = xx_cnt - 1

    ans = 0
    if val == 0:
        print(ans)
    else:
        while val > 0:
            ans += 1
            val = val % cnt
            tmp = val % cnt
            cnt = 0
            while tmp > 0:
                if tmp & 1:
                    cnt += 1
                    tmp = (tmp-1) // 2
                else:
                    tmp = tmp // 2
        print(ans)

Submission status: Time Limit Exceeded

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

num2 = int(x, 2)
ad = 2 ** n
z2o = True
o_cnt = x.count("1")
for i in range(n):
    ad //= 2
    if x[i] == "1":
        num = num2 - ad
        d = o_cnt - 1
    else:
        num = num2 + ad
        d = o_cnt + 1
    cnt = 0
    while num > 0:
        cnt += 1
        num %= d
        bin_num = format(num, "b")
        d = bin_num.count("1")
    print(cnt)

Submission status: Time Limit Exceeded

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

def popcount(x):
    return str(bin(x)).count("1")

cnt=[0]*N

for i in range(1,N):
    p = popcount(i)
    cnt[i]=cnt[i%p]+1


P=X.count("1")
for i in range(N):
    if X[i]=="0":
        ret=int(X,2)+pow(2,N-i-1)
        p=P+1
    else:
        ret=int(X,2)-pow(2,N-i-1)
        p=P-1
    if ret==0:
        print(0)
    else:
        print(cnt[ret%p]+1)

Submission status: Time Limit Exceeded

Solution code:
def popcount(n,ans):
	if n==0: return ans
	ne = n%str(bin(n)).count("1")
	ans = popcount(ne,ans+1)
	return ans

n = int(input())
s = input()
for i in range(n):
	if s[i] == "1": temp = int(s[:i] + "0" + s[i+1:],2)
	else: temp = int(s[:i] + "1" + s[i+1:],2)
	print(popcount(temp,0))

Submission status: Time Limit Exceeded

Solution code:
import sys 
input = lambda:sys.stdin.readline().strip()
def perform(n):
    ans = 0
    while n!=0:
        ans+=1
        n = n%(bin(n).count('1'))
    return ans
n = int(input())
x = list(input())
for i in range(n):
    if x[i]=='0':
        x[i] = '1'
    else:
        x[i] = '0'
    print(perform(int(''.join(x),2)))
    if x[i]=='0':
        x[i] = '1'
    else:
        x[i] = '0'

Submission status: Time Limit Exceeded

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

N = int(input())
X = int(input(), 2)

for i in range(N-1, -1, -1):
    flippedX = X^(1<<i)
    nb = 0
    while flippedX:
        binX = bin(flippedX)
        flippedX %= binX.count('1')
        nb += 1
    print(nb)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N = int(input())
X = int(input(), 2)

@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

for i in range(N):
    x = X ^ (1 << (N-1-i))
    cnt = 0
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)

Submission status: Accepted

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

f = [-1] * (n+10)
f[0] = 0

for i in range(1, n+10):
    # python bitcount で見つけたこれを参考に https://ameblo.jp/316228/entry-10518720149.html
    f[i] = f[i % bin(i).count('1')] + 1

init_bitcount = x.count('1')
# Xを init_bitcount+1とinit_bitcount-1で割った余り

x_mod_01 = 0
for digit in x:
    x_mod_01 *= 2
    if digit == '1':
        x_mod_01 += 1
    x_mod_01 %= (init_bitcount+1)

if init_bitcount != 1:
    x_mod_10 = 0
    for digit in x:
        x_mod_10 *= 2
        if digit == '1':
            x_mod_10 += 1
        x_mod_10 %= (init_bitcount-1)

# print(x_mod_01, x_mod_10, init_bitcount)

power_mod_01 = [-1] * (n+10)
power_mod_01[0] = 1
for i in range(1, n+10):
    power_mod_01[i] = power_mod_01[i-1] * 2 % (init_bitcount + 1)

if init_bitcount != 1:
    power_mod_10 = [-1] * (n+10)
    power_mod_10[0] = 1
    for i in range(1, n+10):
        power_mod_10[i] = power_mod_10[i-1] * 2 % (init_bitcount - 1)


for i in range(n):
    if x[i] == '0':
        # 0→1
        first_residue = (x_mod_01 + power_mod_01[n - i - 1]) % (init_bitcount+1)
        print(f[first_residue] + 1)
    else:
        if init_bitcount == 1:
            # 立っているビットの数は0桁、つまりX_i = 0なのでf(X_i) = 0
            print(0)
            continue
        # 1→0
        first_residue = (x_mod_10 - power_mod_10[n - i - 1]) % (init_bitcount-1)
        print(f[first_residue] + 1)

# https://twitter.com/kyopro_friends/status/1281949470100353024
# https://atcoder.jp/contests/aising2020/editorial 公式
# 1回の操作で桁数以下に落ちることに注意すると、操作の繰り返しで急速に値が小さくなり、少ない回数で0に到着する。
# したがってfの表を作るのは今回不要。愚直にやってもできるので。初回の高速化だけが必要。

Submission status: Accepted

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

f = [-1] * (n+10)
f[0] = 0

for i in range(1, n+10):
    # python bitcount で見つけたこれを参考に https://ameblo.jp/316228/entry-10518720149.html
    f[i] = f[i % bin(i).count('1')] + 1

init_bitcount = x.count('1')
# Xを init_bitcount+1とinit_bitcount-1で割った余り

x_mod_01 = 0
x_mod_10 = 0
for digit in x:
    x_mod_01 *= 2
    x_mod_10 *= 2
    if digit == '1':
        x_mod_01 += 1
        x_mod_10 += 1
    x_mod_01 %= (init_bitcount+1)
    if init_bitcount != 1:
        x_mod_10 %= (init_bitcount-1)

# print(x_mod_01, x_mod_10, init_bitcount)

power_mod_01 = [-1] * (n+10)
power_mod_01[0] = 1
for i in range(1, n+10):
    power_mod_01[i] = power_mod_01[i-1] * 2 % (init_bitcount + 1)

if init_bitcount != 1:
    power_mod_10 = [-1] * (n+10)
    power_mod_10[0] = 1
    for i in range(1, n+10):
        power_mod_10[i] = power_mod_10[i-1] * 2 % (init_bitcount - 1)


for i in range(n):
    if x[i] == '0':
        # 0→1
        first_residue = (x_mod_01 + power_mod_01[n - i - 1]) % (init_bitcount+1)
        print(f[first_residue] + 1)
    else:
        if init_bitcount == 1:
            print(0)
            continue
        # 1→0
        first_residue = (x_mod_10 - power_mod_10[n - i - 1]) % (init_bitcount-1)
        print(f[first_residue] + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

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

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    if numof1 == 1:
        pass
    else:
        for i1 in range(1, n+1):
            bin2_m[-i1] = num2
            num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    if numof1 == 1:
        xas10_m = 0
    else:
        xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            if numof1 == 1:
                print(0)
            else:
                t0 = xas10_m - bin2_m[j1]
                t0 = t0 % (numof1 - 1)
                if t0 == 0:
                    print(1)
                else:
                    print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
sn = input()
sr = ''.join(list(reversed(sn)))
sint = int(sn, 2)
spop = sn.count('1')

def f(x):
    count = 0
    while x != 0:
        count += 1
        pop = bin(x).count('1')
        x %= pop
    return count



m1 = sint % (spop + 1)
m2 = 0 if spop <= 1 else sint % (spop - 1)

a = [0] * n
for i in range(n):
    if sr[i] == '0':
        d = pow(2, i, spop + 1)
        m = (m1 + d) % (spop + 1)
        a[i] = f(m) + 1
    elif spop != 1:
        d = pow(2, i, spop - 1)
        m = (m2 - d + spop - 1) % (spop - 1)
        a[i] = f(m) + 1
    else:
        a[i] = 0

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    bit = input()[::-1]
    count = bit.count("1")
    count_plus = count+1
    count_minus = count-1
    pow_plus = [1 % count_plus]
    for i in range(n):
        pow_plus.append(pow_plus[-1]*2 % count_plus)
    if count_minus != 0:
        pow_minus = [1 % count_minus]
        for i in range(n):
            pow_minus.append(pow_minus[-1]*2 % count_minus)
    else:
        pow_minus = []

    bit_plus = 0
    bit_minus = 0

    for i in range(n):
        if bit[i] == "1":
            bit_plus = (bit_plus+pow_plus[i]) % count_plus
    if count_minus != 0:
        for i in range(n):
            if bit[i] == "1":
                bit_minus = (bit_minus+pow_minus[i]) % count_minus
    ans = []
    for i in range(n):
        if bit[i] == "1":
            if count_minus == 0:
                ans.append(0)
                continue
            bit_ans = (bit_minus-pow_minus[i]) % count_minus
            count = count_minus
        else:
            bit_ans = (bit_plus+pow_plus[i]) % count_plus
            count = count_plus
        cnt = 1
        while bit_ans:
            b = str(bin(bit_ans)).count("1")
            bit_ans = bit_ans % b
            cnt += 1
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)


main()

Submission status: Accepted

Solution code:
import sys

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f 

input = sys.stdin.readline
N = int(input())
X = input().strip()

n0 = 0
for x_i in X:
    if x_i == "1":
        n0 += 1
# print("n0", n0)
r_p = 0 # 0 -> 1のケース
r_n = 0 # 1 -> 0のケース
X = X[::-1]
for i in range(N):
    x = int(X[i])
    r_p += x * pow(2, i, n0+1)
    r_p %= (n0+1)
    if 1 < n0:
        r_n += x * pow(2, i, n0-1)
        r_n %= (n0-1)
# print("r_p", r_p, "r_n", r_n)

ans = []
# print(n)
for i in range(N):
    count = 1
    diff = (1 if X[i] == "0"  else -1)
    # print("x_i", X[i], "diff", diff)
    n = n0 + diff
    if n == 0:
        ans.append(0)
        continue
    if diff == 1:
        r = r_p + (diff * pow(2, i, n))
        r %= n
    else:
        r = r_n + (diff * pow(2, i, n))
        r %= n
    # print("n", n, "r", r)
    n = r
    # print("n", n)
    while 0 < n:
        r = popcount(n)
        count += 1
        # print("n", n)
        if r == 0:
            break
        n = n % r
    ans.append(count)

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

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし


N = I()
X = LI2()
X.reverse()

if N == 0:
    print(1)
    exit()

A = [0]*(2*10**5+1)  # Ai = f(i)
for i in range(1,2*10**5+1):
    k = 0
    for j in range(18):
        if (i >> j) & 1:
            k += 1
    A[i] = A[i % k] + 1


r = sum(X)  # Xの各桁の和

if r >= 2:
    B = [1] + [0]*(N-1)  # Bi = 2**i mod (r-1)
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    b,c = X[0],X[0]  # b,c = X mod (r-1),X mod (r+1)
    for i in range(1,N):
        B[i] = (B[i-1]*2) % (r-1)
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            b += B[i]
            b %= r-1
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r+1)])
        else:
            print(1+A[(b-B[i]) % (r-1)])

else:
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    c = X[0]  # c = X mod (r+1)
    for i in range(1,N):
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r+1)])
        else:
            print(0)

Submission status: Accepted

Solution code:
n = int(input())
s = input()[::-1]
cnt = s.count('1')
# 最初にとるあまりは2種類しかない、　一回余りを取ると2 * 10^5以下になる、あとはふつうにできる
# 最初にとるあまりについて->ビット1桁変わるだけ、あまり2種類について最初の状態でのあまりを計算、
# 1桁変わったところはどうするか？->mod二種類で前計算しておいて足す/引く -> もう一回mod
fac0 = [1] * (n + 1)
fac1 = [1] * (n + 1)
for i in range(1, n + 1):
    fac0[i] = fac0[i - 1] * 2 % (cnt + 1)
    if cnt > 1:
        fac1[i] = fac1[i - 1] * 2 % (cnt - 1)


all0 = 0
all1 = 0
for i in range(n):
    if s[i] == '1':
        all0 = (all0 + fac0[i]) % (cnt + 1)
        if cnt > 1:
            all1 = (all1 + fac1[i]) % (cnt - 1)


def pakuri_poppu(c):
    c = (c & 0x5555555555555555) + (c >> 1 & 0x5555555555555555)
    c = (c & 0x3333333333333333) + (c >> 2 & 0x3333333333333333)
    c = (c + (c >> 4)) & 0x0F0F0F0F0F0F0F0F
    return c * 0x0101010101010101 >> 56 & 0x7f


def bon(x):
    p = pakuri_poppu(x)
    res = 1
    while x:
        x %= p
        p = pakuri_poppu(x)
        res += 1
    return res


for i in range(n - 1, -1, -1):
    if s[i] == '0':
        print(bon((all0 + fac0[i]) % (cnt + 1)))
    else:
        if cnt == 1:
            print(0)
            continue
        print(bon((all1 - fac1[i]) % (cnt - 1)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
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(readline())


def ints(): return list(map(int, readline().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, readline().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, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().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
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


N = a_int()
X = read()[:-1]
tmp = X.count('1')  # Xの1の数
X = list(map(int, list(X[::-1])))


# オリジナルをpop(X)+-1で割ったものを作っておく
Xmodpop = [0, 0, 0]
for i, x in enumerate(X):
    if x:
        Xmodpop[1] += pow(2, i, tmp + 1)
        if tmp != 1:
            Xmodpop[-1] += pow(2, i, tmp - 1)
Xmodpop[1] %= tmp + 1
if tmp != 1:
    Xmodpop[-1] %= tmp - 1

X_nex = []  # 一度操作したあとの値
for i in range(N):
    if X[i] == 1:
        if tmp == 1:
            X_nex.append(-1)
            continue
        X_nex.append((Xmodpop[-1] - pow(2, i, tmp - 1)) % (tmp - 1))
    else:
        X_nex.append((Xmodpop[1] + pow(2, i, tmp + 1)) % (tmp + 1))

# 愚直に操作
ans = []
for i in range(N):
    n = X_nex[i]
    if n == -1:
        ans.append(0)
        continue
    cnt = 1
    while n:
        popc = bin(n).count('1')
        n %= popc
        cnt += 1
    ans.append(cnt)

print(*ans[::-1], sep='\n')

Submission status: Accepted

Solution code:
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
x = int(input(), 2)

# 事前計算
cnt = popcnt(x)
init_big = x % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = x % (cnt - 1)

# 差分計算
result = []
for i in range(n):
    if not (x >> i) & 1:
        result.append((init_big + pow(2, i, cnt + 1)) % (cnt + 1))
    elif x == 1 << i or cnt - 1 == 0:
        result.append("x")
    else:
        result.append((init_small - pow(2, i, cnt - 1)) % (cnt - 1))

ans = []
for x in result[::-1]:
    if x == "x":
        ans.append(0)
    else:
        ans.append(rec(x) + 1)

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

Submission status: Accepted

Solution code:
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]
xint_mi,xint_pl=0,0

for i,y in enumerate(x):
  if xpop>1:
    xint_mi+=(pow(2,n-i-1,xpop-1)*y)%(xpop-1)
    xint_mi%=(xpop-1)
  xint_pl+=(pow(2,n-i-1,xpop+1)*y)%(xpop+1)
  xint_pl%=(xpop+1)

for i,y in enumerate(x):
  if y and xpop>1:
    yint=xint_mi-pow(2,n-i-1,xpop-1)
    ypop=xpop-1
  else:
    yint=xint_pl+pow(2,n-i-1,xpop+1)
    ypop=xpop+1
  if y==1 and xpop==1:
    print(0)
    continue
  yint%=ypop
  #print(yint,ypop)
  print(f(yint)+1)

Submission status: Accepted

Solution code:
import sys

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


N = I()
X = LI2()
X.reverse()

if N == 0:
    print(1)
    exit()

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


r = sum(X)

if r >= 2:
    B = [0]*N
    C = [0]*N
    b,c = 0,0
    for i in range(N):
        if i == 0:
            B[i] = 1
            C[i] = 1
            if X[i] == 1:
                b = 1
                c = 1
        else:
            B[i] = (B[i-1]*2) % (r-1)
            C[i] = (C[i-1]*2) % (r+1)
            if X[i] == 1:
                b += B[i]
                b %= r-1
                c += C[i]
                c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 1:
            print(1+A[(b-B[i]) % (r-1)])
        else:
            print(1+A[(c+C[i]) % (r+1)])

else:
    C = [0] * N
    c = 0
    for i in range(N):
        if i == 0:
            C[i] = 1
            if X[i] == 1:
                c = 1
        else:
            C[i] = (C[i - 1] * 2) % (r + 1)
            if X[i] == 1:
                c += C[i]
                c %= r + 1

    for i in range(N - 1, -1, -1):
        if X[i] == 0:
            print(1 + A[(c + C[i]) % (r + 1)])
        else:
            print(0)