[PS] Latin America 2013 Problem C Counting ones

####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
pdfをダウンロード
魏永珍さんは本題ができないと言ったので、彼にやらせたが、難しい.
ソリューションを探してもソースコードが理解できないので、新しいソリューションを考え出して、私のような人のために解答を書きました.
本問題は,1で表されるビットの個数を最後尾とするアルゴリズムである.
整数の範囲は10^16であるため,繰り返しの文にTLEが現れるため,一般的なpopbitアルゴリズムでは本問題を解決できない.
そのため、私たちはルールを見つけて、すぐに危害を見つけなければなりません.
まず下の表を見てみましょう

まず、問題はAからBの位の和です.
Bへの積算ビット和からA−1の積算ビット和を減算すると正解となる.
上の表では積算ビット数に適切な点火方式を指定していないので、2^nの場合だけ別のものを選んでみます.

今では以下のような点火式が得られます.

ある数xのときxより小さい2^nの累積ビット和を求めることができるようになった.
例えば、12の累積ビット和を求めようとすると
まず、8の累積ビットと13を求める.
では今.9 ,10 ,11 ,12のビット数を要求するだけです.
これをバイナリで表すと次のようになります.

彼らの一番左の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.