PKU 3105 Expectation

• 各桁のビットに着目して解いていく
• 各桁ごとにビットが立つ確率を求め、それらを2^i倍して足していけば良い
• 答えが合わずに困ってたら、1〜nまでで考えていたのが原因だった。本当は0〜n-1
• G++で提出したらWA、C++だとACだった。やっぱり納得が行かない。

int countBits(int n, int s)
{
	int result = n / (1 << (s + 1)) * (1 << s);
	int rest = n % (1 << (s + 1)) - (1 << s);
	if (rest < 0) {
		rest = 0;
	}
	return result + rest;
}

int main() {
	int k;
	cin >> k;
	for (int i = 0; i < k; ++i) {
		double sum = 0;
		int n;
		cin >> n;
		for (int bit = 0; bit < 31; ++bit) {
			double p = countBits(n, bit) / (double)n;
			p = 2.0 * p * (1.0 - p);
			p *= (1 << bit);
			sum += p;
		}

		printf("%.5lf\n", sum);
	}
}