2019.7.3模拟光影交错（穷举+概率dp）

题目大意：

每一轮有pl的概率得到正面的牌，pd的概率得到负面的牌，1-pl-pd的概率得到无属性牌。

每一轮过后，都有p的概率结束游戏，1-p的概率开始下一轮。

问期望有多少轮后正面的牌数严格大于负面的牌数。

题解：

设\(f[i]\)表示期望有\(f[i]\)轮后含有\(i\)张有属性牌。

\(g[i]\)在i张有属性牌的前提下，正面的牌数严格大于负面的牌数的概率。

\(Ans=\sum_{i=0}^nf[i]*g[i]\)

可以感受到\(n\)大概做个\(10^7\)就够了。

设\(F(x)=\sum_{i>=1}f[i]x^i\)

\(F(x)=\sum_{i=1}^{+∞}(1-p)^{i-1}*((pl+pd)x+(1-pl-pd))^i\)

上式可以化简为\({ax+b \over cx+d}\)的形式。

记一步化简为\((ax+b)/(1-cx)\)。

这个是常系数齐次线性递推的标准形式：

若有\(F={A \over 1-bx}\)，则\(F(1-bx)=A->F=F·bx+A\)，

可以得到这个递推的次数=1，并且0-1次项是定值，因为A的是1次的。

所以手推\(f[0]、f[1]\),即可\(f[i]=f[i-1]*b(i>=2)\)

\[g[x]=
\begin{equation}
\left\{
\begin{array}{**lr**}
0&,x=0\\
g[x-1]-\binom{x-1}{x/2}×p1^{x/2}×p2^{x/2}&,x是偶数\\
g[x-1]+\binom{x-1}{(x-1)/2}×p1^{(x-1)/2+1}×p2^{(x-1)/2}&,x是奇数
\end{array}
\right.
\end{equation}
\]

注意后面那堆东西不能直接算，会爆精度，也需要递推。

Code:

#include<bits/stdc++.h>

#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)

#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)

#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)

#define ll long long

#define pp printf

#define hh pp("\n")

#define db long double

using namespace std;

int num, T;

db pl, pd, p;

const int N = 1000;

db f[2][2 * N + 5]; int o;

db s[N + 5];

db calc(db st, db q) {

	return st * (-q) / (q - 1);

}

const db eps = 1e-9;

db calc2(db p, db w) {

	db c = (1 - p) * w;

	return (1 - p) * (1 - w) * (-c) / (c - 1);

}

int main() {

	freopen("augury.in", "r", stdin);

	freopen("augury.out", "w", stdout);

	scanf("%d", &num);

	for(scanf("%d", &T); T; T --) {

		scanf("%Lf %Lf %Lf", &pl, &pd, &p);

		if(p == 1) {

			pp("%.15Lf\n", pl);

			continue;

		}

		db w = 1 - pl - pd, ans = 0;

		db ps = pl + pd, p1 = pl / ps, p2 = pd / ps;

		db p3 = abs(w) < eps ? (1 - p) : calc2(p, w);

		memset(f, 0, sizeof f);

		f[0][N] = 1 / (1 - p);

		fo(i, 1, N) {

			s[i] = 0;

			fo(j, N - i, N + i) {

				f[!o][j] = (f[o][j - 1] * pl + f[o][j + 1] * pd + f[o][j] * w);

				f[!o][j] *= (1 - p);

				ans += f[!o][j] * (j > N);

				s[i] += f[!o][j] * (j > N);

			}

			o = !o;

		}

		if(abs(s[N - 1]) > eps) ans += calc(s[N], s[N] / s[N - 1]);

		pp("%.15Lf\n", ans);

	}

}

巴特西

2019.7.3模拟光影交错（穷举+概率dp）

题目大意：

题解：

Code:

最新文章

热门文章

巴特西

2019.7.3模拟 光影交错（穷举+概率dp）

题目大意：

题解：

Code:

最新文章

热门文章

2019.7.3模拟光影交错（穷举+概率dp）