SRM475 Div1 Easy

300
全部試す。

シュミレーションで挑んで泣きたくなった。
でも、よく考えたらそうでもなかった。
うさぎがはみ出ることがない以上、偶数インデックスと奇数インデックスのそれぞれに1匹残るかどうかになる。

class RabbitStepping {
public:
  double getExpected(string F, int r) 
  {    
    double sum = 0;
    double cnt = 0;
    for (int bit = 0; bit < (1 << F.size()); ++bit) {
      if (__builtin_popcount(bit) == r) {       
        ++cnt;
        int n[2];
        n[0] = n[1] = 0;
        for (int i = 0; i < F.size(); ++i) {
          if (bit & (1 << i)) n[i % 2] ^= 1;
        }
        sum += n[0] + n[1];
      }
    }

    return sum / cnt;
  }

};