提出 #15172713

---

ソースコード 拡げる

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <random>
#include <ctime>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define ld long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast_io cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ld eps = (ld)1 / 1e6;
ll inf = LLONG_MAX, mod1 = 1e9 + 7, mod2 = 998244353;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ll md[200010][2];
ll solve(ll x)
{
    if (!x) return 0;
    bitset<40> bt = x;
    ll t = bt.count();
    return (1 + solve(x % t));
}

int main()
{
    fast_io;
    ll n, i, k0 = 0, n1 = 0, n2 = 0, nw;
    string a;
    cin >> n >> a;
    for (i = 0; i < n; i++)
        if (a[i] == '1') k0++;
    md[0][0] = md[0][1] = 1;
    for (i = 1; i < n; i++)
    {
        if (k0 > 1) md[i][0] = (2 * md[i - 1][0]) % (k0 - 1);
        md[i][1] = (2 * md[i - 1][1]) % (k0 + 1);
    }
    for (i = 0; i < n; i++)
    {
        if (a[i] == '0') continue;
        if (k0 > 1) n1 = (n1 + md[n - i - 1][0]) % (k0 - 1);
        n2 = (n2 + md[n - i - 1][1]) % (k0 + 1);
    }
    for (i = 0; i < n; i++)
    {
        if (k0 == 1 && a[i] == '1')
        {
            cout << "0\n";
            continue;
        }
        if (a[i] == '0') nw = (n2 + md[n - i - 1][1]) % (k0 + 1);
        else nw = (n1 - md[n - i - 1][0] + k0 - 1) % (k0 - 1);
        cout << 1 + solve(nw) << '\n';
    }
    return 0;
}

提出情報

ジャッジ結果