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

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

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("
")
#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
", 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
", ans);
	}
}