[백준] 9527 - 1의 개수 세기

https://www.acmicpc.net/problem/9527

9527번: 1의 개수 세기

 

 

 

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
map<ll,ll> mp;
void init() {
    mp[1] = 1;
    for(int i = 2; pow(2, i) - 1 <= 1e16; i++) {
        ll t1 = pow(2, i);
        ll t2 = pow(2, i - 1);
        mp[t1 - 1] = t2 + 2 * mp[t2 - 1];
    }
}

ll g(ll x) {
    if(x <= 0) return 0LL;

    ll idx = 0;
    for(int i = 0; ;i++) {
        if(pow(2, i) - 1 > x) {
            idx = i - 1;
            break;
        }
    }

    ll tmp = pow(2, idx) - 1;
    if(tmp == x) {
        return mp[tmp];
    } else {
        return mp[tmp] + (x - tmp) + g(x - tmp - 1);
    }
}
int main() {
    fastio;
    ll a, b;
    cin >> a >> b;

    init();
    cout << g(b) - g(a - 1) << '\n';
    return 0;
}

먼저

$$g(y)=\sum_{x=0}^{y}f(x)$$

와 같은 함수를 생각해보았다. 

 

그림을 그려보면 g(y)는 y가 2^{n} - 1 일때 규칙을 가진다.

 

예를들어 y가 7일때 g(7) = 4 + 2 * g(3) 인데,

이런식으로 세 부분으로 쪼갤 수 있는 걸 알 수 있다.

 

$$g(2^{n}-1) = 2^{n - 1} + 2 \times g(2^{n - 1}-1)$$

 

 

그리고 g(y)의 함수에서 y의 값이 2^{n} - 1 이 아닌 경우에도

g(12) = g(7) + g(4) + 5

이런식으로 세 부분을 쪼갤 수 있다.

 

y 보다 작으면서 가장 큰 2^{n} - 1를 구해서 tmp라고 하면

g(y) = g(tmp) + g(y - tmp - 1) + (y - tmp) 의 재귀식으로 구할 수 있다.