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

· · 题解

说这个题目的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]);
}