朝田诗乃 的博客

朝田诗乃 的博客

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

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

说这个题目的 $n$ 是 $10^4$ ,当 $n=0$ 和 $n=1$ 的时候答案是显然的,然后我们考虑两个人的情况。比方说两个参赛者,一个yyy,一个雪碧。先崩yyy,如果他 $P_0$ 的概率崩死了,那yyy没了,剩一个雪碧,雪碧赢了;如果他 $(1-P_0)$ 的概率没死,那么游戏要继续呀。雪碧来到了第一位,yyy相当于到了第二位。其实这个局面,和开枪前没有区别,只不过是yyy和雪碧互换了位置罢了。

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

这样,我们设 $F[2][1]$ 表示第一个人最终幸存的概率, $F[2][2]$ 表示第二个人最终幸存的概率。

$$ 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 $$

当前我们在崩第1个玩家,这个时候排在第k位玩家的概率会是怎么样的呢?

概率 $1-P_0$ :如果第一个玩家没被崩死,所有人都向前走了一步!

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

概率 $P_0$ :如果第一个玩家被崩死,所有人还是都向前走了一步!

$$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] $$

这一共能给你 $n$ 个等式。

由于最后有且仅有最后一个幸存者,所以有

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

解n元一次方程,高斯消元能拿10pts。

手动消元就能100pts了。

最后要特判一下 $P_0=0$ 的情况。

总复杂度 $O(n^2)$

题解By X

//朝田诗乃:居然被那么多人水过了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]);
}