题目大意：
每一轮有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]=
egin{equation}
left{
egin{array}{**lr**}
0&,x=0\
g[x-1]-inom{x-1}{x/2}×p1^{x/2}×p2^{x/2}&,x是偶数\
g[x-1]+inom{x-1}{(x-1)/2}×p1^{(x-1)/2+1}×p2^{(x-1)/2}&,x是奇数
end{array}
ight.
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("
")
#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);
}
}