# 朝田诗乃 的博客

### 题解 P5249 【[LnOI2019]加特林轮盘赌】

posted on 2019-03-11 20:01:10 | under 题解 |

//以上题解由 $X$ 口述，朝田诗乃记录。

$$F[2][1] = P_0 * 0 + (1-P_0) * F[2][2]$$

$$F[2][1] + F[2][2] = 1$$

K个人呢？头两个式子我们可以抄上面的啊！

$$F[n][1] = (1-P_0) * F[n][n]$$

$$F[n][1] + F[n][2] + ... F[n][n] = 1$$

$$F[n][k] -> F[n][k-1]$$

$$F[n][k] -> F[n-1][k-1]$$

$$F[n][k] = P_0 * F[n][k-1] + (1-P_0) * F[n-1][k-1]$$

$$\Sigma_{k=1}^{n}F[n][k] = 1$$

//朝田诗乃：居然被那么多人水过了QAQ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
const int MAXN = 20050;
double p0; int n, k, cur = 1, last;
double f[2][MAXN];
int main() {
cin >> p0 >> n >> k;
f[1][1] = 1;
if(p0 == 0) {
if(n == 1) puts("1");
else puts("0");
return 0;
}
for(int i = 2; i <= n; ++i) {
double a = 1, c = 0, A = 0, C = 0;
last = cur; cur ^= 1;
for(int j = 2; j <= i; ++j) a *= (1-p0), A += a, c = (1-p0) * c + p0 * f[last][j-1], C += c;
f[cur][1] = (1-C) / (A+1);
for(int j = 2; j <= i; ++j)
f[cur][j] = p0 * f[last][j-1] + (1 - p0) * f[cur][j-1];
}
printf("%.10lf", f[cur][k]);
}