####acm archive
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4538
####backjoon online judge
https://www.acmicpc.net/problem/9527
####PDF file
6527.pdf 다운로드
위영진 학생이 본 문제를 못풀겠다고 해서 풀어주었는데 어려웠다.
솔루션을 찾아봐도 소스를 이해할 수가 없어 새로 생각해 내었는데, 나같은 사람을 위해 풀이를 적는다.
본 문제는 1로 표현된 bit의 개수를 세는데 가장 끝판왕인 알고리즘이다.
정수의 범위가 10^16이라 반복문을 돌면 TLE가 나오기 때문에 일반적은 popbit 알고리즘으로는 본 문제를 풀 수가 없다.
따라서 규칙을 찾아서 바로 해를 찾아야한다.
아래의 표를 먼저 보자
먼저 문제는 A부터 B의 비트의 합이므로,
B까지의 누적 비트합에서 A-1의 누적비트합을 빼면 정답이 된다.
위 표에서 누적비트의 수에 적당한 점화식이 생각나지 않으니 2^n인 경우만 따로 뽑아서 보자.
이제 아래와 같은 점화식을 얻을 수 있다.
이제 어떤수 x가 있을때 x보다 작은 2^n의 누적 비트합을 구할 수 있다.
예시를 들면 12의 누적비트합을 구하려고 할때
8의 누적비트합인 13을 먼저 구한다.
그렇다면 이제
9 ,10 ,11 ,12에서의 비트만 구하면 된다.
이는 2진수로 표현한다면 아래와 같다.
이들의 가장 맨 왼쪽의 1비트의 개수는 12-8 인 4개이다. 따라서 본 4개를 추가로 더해주고,
12에서 맨 오른쪽 비트를 뺀 100 즉 4의 누적비트합을 추가로 더해주면 계산은 끝난다.
아래는 본 솔루션에 대한 소스코드이다.
long long pop_accumulation_bit(long long x) {
if (x == 0)return 0;
long long r = 1;
int i;
for (i = 0; x >> (i + 1); i++){
r = r * 2 + (1LL << i) - 1;
}
return r + proc(~(1LL << i)&x) + (x - (1LL << i));
}Copyright (C) 2016 (KimBom) all rights reserved.