電車の中で考えて解法がわかったのでワクワクしながらコードを書いたんですが double 周りでつらみが生えた。
解法
2 進数の各桁 i ごとに, そのビットが立つ確率 p_i を求めると, 期待値の線形性により, 答えは
2^0 * p_0 + 2^1 * p_1 + ...
となります。ということで, 2 進数の桁 i が立つ確率を求めましょう。
L から R までで 2 進数の桁 i が立っているものの数を求めて, 数字を 1 つ選んだ時に i 桁目が立っているものを選ぶ確率を元芽ます。この値を q とします。すると, K 回数字を選んだ時 2 進数の桁 i が立つ確率 は,
の漸化式を解くことによって得られます。
で, double 周りでつらみ生えた件ですが, これです。
C++ で pow(-1,43594979775965213) ってやるとなぜか 1 が出力されるんですがなぜですか
— マヨ子@荒川区ではアッラーが湧く (@mayoko_) 2015, 11月 18
long long のでかい値になると, double で表しきれなくなるので, でかい数の下の桁が潰れて, 奇数であって欲しい数が偶数になってしまいます。対策としては, 下のコードのように -1 の場合を特別扱いするか, long double を使えば良いです。
// N までの数で k ビット目が立っている数字の数を求める ll countBit(ll N, int k) { ll cycle = 1ll<<(k+1); ll R = N/cycle * cycle; ll ret = R/2; ll tmp = N+1-R-(1ll<<k); if (tmp > 0) ret += tmp; return ret; } int main() { int T; cin >> T; cout << powl(-1,435949797759652133) << endl; while (T--) { ll K, L, R; cin >> K >> L >> R; double ans = 0; for (int i = 0; i < 32; i++) { ll n1 = countBit(R, i) - countBit(L-1, i); ll n0 = R-L+1-n1; double prob = 1.*(n0-n1)/(n0+n1); double plus; if (prob != -1) plus = 0.5 * (1 - pow(prob, K)); else plus = 0.5 * (1-pow(prob, K%2)); plus *= 1ll<<i; ans += plus; } printf("%.15lf\n", ans); } return 0; }