自动搬运

查看原文

来自洛谷，原作者为

	诗乃 あなた以上の人なんて、どこにもいないよ♡

搬运于2025-08-24 22:08:42，当前版本为作者最后更新于2019-03-11 20:01:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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