[ boj : 9527 ] 1의 개수 세기

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

9527번: 1의 개수 세기

문제 : x부터 y까지의 수를 이진수로 표현했을때 나타나는 1의 개수들의 합을 구하시오

해설 : 와 이거 너무어렵습니다 진짜 ㅠㅠㅠㅠㅠ
엄청 고생했습니다. 사실 도움을 받았어요
일단 $\sum_{k=x}^y f(x)$ 를 풀어보면 $\sum_{k=1}^y f(x)$ - $\sum_{k=1}^{x-1} f(x)$ 이 됩니다.
그러면 우리가 할일은 $f(x)$ 를 구하면 되는 것이겠죠?

먼저 이 문제는 DP로도 풀 수 없습니다(범위를 보면 알 수 있죠) 그렇다면 결국 어떤 규칙성을 찾고 이 규칙성을 식으로 나타낼 수 있으면 문제를 해결할 수 있습니다.

어떤 $n$에 관하여 $n$ 이하의 수들 중에서 홀수 인 수들의 개수는 $(n/2)$ 개 입니다.
이 말이 무슨뜻이냐면 현재 위치한 비트자리수의 이상인 수에서 2를 나눈 만큼의 개수가 1이 나온 횟수라는 뜻입니다.

$1011_{(2)}$로 예를 들어보겠습니다.

맨 아래 비트가 1인 경우가 몇번 나오는지 구하려면 맨 아래 비트보다 이상인 비트들로만 이루어진 $1010_{(2)}$인 경우에서 홀수인 애들만 구하는 것이니 10/2 = 5 (1,11,101,111,1001) 이 나옵니다.

맨 아래에서 2번째 자리에서 1인 경우가 몇번 나오는지 구하려면 마찬가지로 현재 위치보다 이상인 비트들로만 이루어진 $1000_{(2)}$인 경우에서 2로 나누어주면 되겠죠. 8/2 = 4(10,11,110,111)

마지막도 똑같이 구해주면 됩니다.

그리고 남은 부분은 현재 위치보다 낮은 자리들의 1의 개수들을 더해주면 되겠죠 ㅎㅎ
$101x_{(2)}$ 의 x에 해당하는 수들이죠
여기에서 이제 현재위치한 비트가 1이라면 +1씩을 더해주고 0이라면 그냥 넘어가면 됩니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll sol(ll x);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll x,y;
    cin >> x >> y;
    x = sol(x-1);
    y = sol(y);
    cout << abs(x - y);
    //cout << x << " " << y;
    return 0;
}
ll sol(ll x)
{
    ll ret = 0, prev = 0, i = 1, y = x;
    while (x>i) 
    {
        if (x & i) {
            ret += prev + 1;
            prev += (x & i);
            x -= i;
        }
        ret += (x / 2);
        i <<= 1;
    }
    return ret+(y-i+1);
}