# hihoCoder 1506-投掷硬币

hihoCoder 1506-投掷硬币

### 输出

```2 1
0.5 0.5```

`0.500000`

```#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

double ans = 0;
int n, m;

void dfs(const vector<double>& probs, double curprob, int step, int up) {
if (up == m) {
double oneans = curprob;
for (int i = step; i < n; ++i)oneans *= (1 - probs[i]);
ans += oneans;
return;
}
if (step < n) {
dfs(probs, curprob*probs[step], step + 1, up + 1);
dfs(probs, curprob*(1 - probs[step]), step + 1, up);
}
}

int main() {

//freopen("input.txt", "r", stdin);

scanf("%d %d", &n, &m);
vector<double> probs(n, 0);

for (int i = 0; i < n; ++i) scanf("%lf", &probs[i]);
dfs(probs, 1, 0, 0);
printf("%lf\n", ans);
return 0;
}
```

```#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

int main() {

//freopen("input.txt", "r", stdin);

int n, m;
scanf("%d %d", &n, &m);
vector<double> probs(n + 1, 0);
for (int i = 1; i <= n; ++i)scanf("%lf", &probs[i]);

vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
dp[0][0] = 1.0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) { //现在有i枚硬币，所以正面向上的个数j不超过i
dp[i][j] += dp[i - 1][j - 1] * probs[i];  // head
dp[i][j - 1] += dp[i - 1][j - 1] * (1 - probs[i]); // tail
}
}
printf("%lf\n", dp[n][m]);
return 0;
}
```