mayoko’s diary

プロコンとかいろいろ。

Saiko~ No Contesuto #01 わくわく排他的論理和

電車の中で考えて解法がわかったのでワクワクしながらコードを書いたんですが 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 が立つ確率  p_K は,
 p_{n+1} = q(1-p_n) + (1-q)p_n
の漸化式を解くことによって得られます。

で, double 周りでつらみ生えた件ですが, これです。


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;
}