[AtCoder] エイシング プログラミング コンテスト 2020 D – Anything Goes to Zero

2020年12月14日

問題

方針

ビットカウントのアルゴリズム

アルゴリズムについては上記のサイトを参考にしました。

int count_bits(int n) {
    n=(n&0x55555555)+(n>>1&0x55555555);
    n=(n&0x33333333)+(n>>2&0x33333333);
    n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f);
    n=(n&0x00ff00ff)+(n>>8&0x00ff00ff);
    n=(n&0x0000ffff)+(n>>16&0x0000ffff);
    return n;
}

\( 2 \times 10^5 \) 以下の \( f(n) \) の値は、愚直に求めます。

ビット毎に剰余を取る

\( X \) のビットカウントを \( p\) とすると、\( X \) の \( i \) ビット目を反転させたときのビットカウントは、\( p – 1 \) または \( p + 1 \) となります。また、剰余はビット毎に演算しても良いので、\( X \) の \( p – 1 \) と \( p + 1 \) の剰余をあらかじめ計算し、\( i \) ビット目の値によって補正すれば良いです。

ビット毎に剰余を取るには、階乗の剰余のアルゴリズムを使えば良いです。注意として、\( p = 1 \) のとき、\( X_i = 1 \) ならば、答えは \( 0 \) となります。

ビット反転の補正

\( a_1 =  X \bmod (p – 1) \) 、\( a_2 = X \bmod (p + 1) \) とします。これらはあらかじめ求めておきます。

\( X_i = 1 \) のとき

このとき、\( X_i = 0 \) としたときの、\( p – 1 \) による剰余は、

\[(a_1 – 2^{N – i – 1} \bmod (p – 1) + p – 1) \bmod (p – 1)\]

となります。

\( X_i = 0 \) のとき

このとき、\( X_i = 1 \) としたときの、\( p + 1 \) による剰余は、

\[(a_2 + 2^{N – i – 1}) \bmod (p + 1)\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int count_bits(int n) {
    n=(n&0x55555555)+(n>>1&0x55555555);
    n=(n&0x33333333)+(n>>2&0x33333333);
    n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f);
    n=(n&0x00ff00ff)+(n>>8&0x00ff00ff);
    n=(n&0x0000ffff)+(n>>16&0x0000ffff);
    return n;
}

ll modpow(ll a, ll n, ll mod) {
    if (mod <= 0) return 0;
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int solve(int n) {
    if (n == 0) return 0;
    return solve(n % count_bits(n)) + 1;
}

int main() {
    int N;
    string X;
    cin >> N >> X;
    ll p = 0;
    for (int i = 0; i < N; i++) {
        if (X[i] == '1') p++;
    }
    ll a1 = 0;
    ll a2 = 0;
    for (int i = 0; i < N; i++) {
        if (X[i] == '1') {
            if (p == 1) {
                a1 = 0;
            } else {
                a1 = (a1 + modpow(2, N - i - 1, p - 1)) % (p - 1);
            }
            a2 = (a2 + modpow(2, N - i - 1, p + 1)) % (p + 1);
        }
    }
    for (int i = 0; i < N; i++) {
        if (X[i] == '1') {
            if (p == 1) {
                cout << 0 << "\n";
            } else {
                cout << 1 + solve((a1 - modpow(2, N - i - 1, p - 1) + p - 1) % (p - 1)) << "\n";
            }
            
        } else {
            cout << 1 + solve((a2 + modpow(2, N - i - 1, p + 1)) % (p + 1)) << "\n";
        }
    }
    return 0;
}