No.66 輝け☆全国たこやき杯 - yukicoder
class TakoyakiCup {
public:
void solve(void) {
int M,N;
cin>>M;
N = (1<<M);
vector<double> S(N, 0.0);
REP(i,N)
cin>>S[i];
auto win = [&](int x, int y) {
return S[x]*S[x]/(S[x]*S[x]+S[y]*S[y]);
};
vector<vector<double>> dp(N, vector<double>(M+1,0));
REP(i, N)
dp[i][0] = 1.0;
FOR(i, 1, M+1)
{
int len = (1<<i);
REP(x, N)
{
int l = x/len*len;
int r = l+len;
int mid = l+len/2;
if (x < mid)
FOR(y, mid, r)
dp[x][i] += dp[x][i-1]*dp[y][i-1]*win(x,y);
else
FOR(y, l, mid)
dp[x][i] += dp[x][i-1]*dp[y][i-1]*win(x,y);
}
}
cout<<dp[0][M]<<endl;
}
};