SRM537 Div1 Medium

500
DP[K日][部屋N][Bビット] = K日が経過した部屋NのBビット目が１になっている確率。

class KingXMagicSpells {
public:
  double expectedNumber(vector <int> D, vector <int> S1, vector <int> S2, int K)
  {
    const int N = D.size();
    const int B = 30 + 1;
    ++K;

    double dp[K][N][B];
    fill(&dp[0][0][0], &dp[K - 1][N - 1][B], 0);
   
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < B; ++j) {
        dp[0][i][j] = (bool)(D[i] & (1 << j));
      }
    }
   
    // spell1 : xor
    // spell2 : move
    for (int day = 0; day + 1 < K; ++day) {
      for (int room = 0; room < N; ++room) {
        for (int bit = 0; bit < B; ++bit) {
          if (S1[room] & (1 << bit)) {
            dp[day + 1][room][bit] += (1.0 - dp[day][room][bit]) * 0.5;
          } else {
            dp[day + 1][room][bit] += dp[day][room][bit] * 0.5;
          }
          dp[day + 1][S2[room]][bit] += dp[day][room][bit] * 0.5;
        }
      }
    }

    double ret = 0;
    for (int i = 0; i < B; ++i) {
      ret += dp[K - 1][0][i] * (1 << i);
    }
    return ret;
  }
};