SRM 537 div1 med: KingXMagicSpells

問題

TopCoder Statistics - Problem Statement

解法

bit ごとに考えます。

dp[day][index][bit] = (day 日目に, index 番目の部屋の duck の数について, bit 目の値が 1 になっている確率) とします。
例えば初日に duck の数が 5 だったら 0 bit 目と 2 bit 目は 1 になっているので, dp[0][index][0] = dp[0][index][2] = 1, みたいな感じです。

dp さえ思いつけば簡単ですね。「XOR では bit ごとに独立に見るのは典型」らしいです。

double dp[55][55][32]; // day, index, bit

class KingXMagicSpells {
public:
    double expectedNumber(vector <int> ducks, vector <int> spellOne, vector <int> spellTwo, int K) {
        int n = ducks.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 32; j++) dp[0][i][j] = (ducks[i]>>j)&1;
        }
        for (int k = 0; k < K; k++) {
            // 1
            for (int i = 0; i < n; i++) for (int j = 0; j < 32; j++) {
                double p = dp[k][i][j];
                if (spellOne[i]>>j & 1) dp[k+1][i][j] += (1-p)/2;
                else dp[k+1][i][j] += p/2;
            }
            // 2
            for (int i = 0; i < n; i++) {
                int next = spellTwo[i];
                for (int j = 0; j < 32; j++) {
                    dp[k+1][next][j] += dp[k][i][j]/2;
                }
            }
        }
        double ret = 0;
        int tmp = 1;
        for (int i = 0; i < 32; i++) {
            ret += tmp * dp[K][0][i];
            tmp <<= 1;
        }
        return ret;
        return 0;
    }
};