Solution to SP4060 Game with Probability Problem。

设 \(f_i,g_i\) 分别表示还剩 \(i\) 个的时候轮到 Alice 和 Bob 时 Alice 分别的胜率。

概率经典倒推。那么显然有 \(f_0=0,g_0=1\)。

然后就是一个分讨，讨论这个人想要正面还是反面。很显然，对于同样的剩余棋子数，两个人先手的情况对于这颗棋子的喜爱程度是一样的。也就是说，要么都想要，要么都不想要。

什么时候想要呢？拿掉过后自己胜率更大，也就是 \(g_{i-1}>f_{i-1}\)。此时有：

\[ f_i=(1-p)\times g_i+p\times g_{i-1}\\ g_i=(1-q)\times f_i+q\times f_{i-1} \]

发现是互相影响的，这个时候先不要着急怀疑自己推错了，因为我们这里有两个未知数，又刚好有两个方程，暴解一下就有：

\[ f_i=\dfrac {(1-p)\times q\times f_{i-1}+p\times g_{i-1}}{1-(1-p)(1-q)}\\ g_i=\dfrac {(1-q)\times p\times g_{i-1}+q\times f_{i-1}}{1-(1-p)(1-q)} \]

然后 \(g_{i-1}<f_{i-1}\) 的情况也差不多，把拿的概率和不拿的概率换一下：

\[ f_i=p\times g_i+(1-p)\times g_{i-1}\\ g_i=q\times f_i+(1-q)\times f_{i-1} \]

解方程组有：

\[ f_i=\dfrac {(1-q)\times p\times f_{i-1}+(1-p)\times g_{i-1}}{1-p\times q}\\ g_i=\dfrac {(1-p)\times q\times g_{i-1}+(1-q)\times f_{i-1}}{1-p\times q} \]

然后就可以开始 DP 了。最后的答案就是 \(f_{\min(n,1000)}\)。

还有个问题就是 \(n\) 特别大然后这个看起来也不太能矩乘，但是这个 DP 式有个好处是它的增长趋势是指数级的，所以我们 DP 到 \(1000\) 就可以了。

#include <bits/stdc++.h>
namespace XSC062 {
const int maxn = 1e3 + 5;
using db = double;
db p, q;
int T, n;
db f[maxn], g[maxn];
int min(int x, int y) {
	return x < y ? x : y;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d %lf %lf", &n, &p, &q);
		f[0] = .0, g[0] = 1.0;
		for (int i = 1; i <= n && i <= 1000; ++i) {
			if (g[i - 1] > f[i - 1]) {
				f[i] = ((1 - p) * q * f[i - 1] + p * g[i - 1]) / (1 - (1 - p) * (1 - q));
				g[i] = ((1 - q) * p * g[i - 1] + q * f[i - 1]) / (1 - (1 - p) * (1 - q));
			}
			else {
				f[i] = ((1 - q) * p * f[i - 1] + (1 - p) * g[i - 1]) / (1 - p * q);
				g[i] = ((1 - p) * q * g[i - 1] + (1 - q) * f[i - 1]) / (1 - p * q);
			}
		}
		printf("%.6lf\n", f[min(n, 1000)]);
	}
	return 0;
}
} // namespace XSC062
int main() {
	XSC062::main();
	return 0;
}