Language: C++

//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <inttypes.h>
#include <map>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <atcoder/all>
using namespace atcoder;

using namespace std;

using ll = int64_t;
using ull = uint64_t;

[[maybe_unused]] constexpr ll LL_MAX = numeric_limits<ll>::max();
[[maybe_unused]] constexpr ll LL_MIN = numeric_limits<ll>::min();
[[maybe_unused]] constexpr ull ULL_MAX = numeric_limits<ull>::max();

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a)-1; i >= (b); i--)

template<typename T>
void chmin(T& x, T y) {
	x = min(x, y);
}

template<typename T>
void chmax(T& x, T y) {
	x = max(x, y);
}

ll csum(ll x, ll y) {
	if (x > 0 && y > 0 && x > LL_MAX - y) {
		return LL_MAX;
	}
	if (x < 0 && y < 0 && x < LL_MIN - y) {
		return LL_MIN;
	}
	return x + y;
}

ll readi() {
	ll ret;
	scanf("%" PRId64 "", &ret);
	return ret;
}

vector<ll> readvi(ll n) {
	vector<ll> ret(n);
	rep(i, 0, n) { ret[i] = readi(); }
	return ret;
}

string reads() {
	string s;
	cin >> s;
	return s;
}

void writei(ll x) {
	printf("%" PRId64 "\n", x);
}

void writevi(const vector<ll>& xs) {
    rep(i,0,xs.size()) {
        if (i < xs.size() - 1) {
            printf("%" PRId64 " ", xs[i]);
        } else {
            printf("%" PRId64 "\n", xs[i]);
        }
    }
}

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

// using mint = modint1000000007;
// using mint = modint998244353;
using mint = modint;

ll popcnt(int n) {
	ll ans_loc = 0;
	rep(i,0,31) {
		if ((ull)n & ((ull)1 << i)) {
			ans_loc++;
		}
	}
	return ans_loc;
}

ll f(int n) {
	ll ans = 0;
	while (n > 0) {
		n = n % popcnt(n);
		ans++;
	}
	return ans;
}

int main() {
	ll N = readi();
	string X = reads();
	vector<bool> digits(N);
	rep(i,0,N) {
		digits[i] = X[N-1-i] == '1';
	}
	ll cnt = 0;
	rep(i,0,N) {
		if (digits[i]) {
			cnt++;
		}
	}
	unordered_map<ll, ll> xModC;
	rep(i,-1,2) {
		ll c = cnt + i;
		if (c <= 0) {
			continue;
		}
		mint::set_mod(c);
		mint x = 0;
		mint pow = 1;
		rep(i,0,N) {
			if (digits[i]) {
				x += pow;
			}
			pow *= 2;
		}
		xModC[c] = x.val();
	}
	unordered_map<ll, ll> powModC;
	for (const auto& kv : xModC) {
		powModC[kv.first] = 1;
	}
	vector<ll> ans;
	rep(i,0,N) {
		ll c = 0;
		if (digits[i]) {
			c = cnt - 1;
		} else {
			c = cnt + 1;
		}
		if (c == 0) {
			ans.push_back(0);
		} else {
			mint::set_mod(c);
			mint pow = powModC[c];
			mint x = xModC[c];
			if (digits[i]) {
				x -= pow;
			} else {
				x += pow;
			}
			ll ans_loc = 1;
			ans_loc += f(x.val());
			ans.push_back(ans_loc);
		}
		for (const auto& kv : powModC) {
			ll C = kv.first;
			ll val = kv.second;
			mint::set_mod(C);
			mint pow = val;
			pow *= 2;
			powModC[C] = pow.val();
		}
	}
	rrep(i,N,0) {
		writei(ans[i]);
	}
}


Compiler output:
a.cc:28:10: fatal error: atcoder/all: No such file or directory
   28 | #include <atcoder/all>
      |          ^~~~~~~~~~~~~
compilation terminated.