Description
你现在在第 0 关，胜利可以到下一关，失败则回到上一关。特别地，在第 0 关失败后依然在第 0 关。你在第 $i$ 关胜利的概率为 $p_i$。现在问你过掉 $n$ 关期望需要进行多少次对局。试求答案对 $998244353$ 取模之后的结果。
Solution
考虑设 $f_i$ 表示从 $i$ 到 $n$ 的期望局数。
然后有：
其中 。
然后有 $f_{i + 1} = p_{i + 1}f_{i + 2} + (1 - p_{i + 1})f_i + 1$。
移项，得：
把那个 $(1 - p_{i + 1})$ 除过去，得到：
然后你不停代换到 $f_0$，最后解一下方程就好了。
啊还有另一种方法：
你设 $f_i$ 表示从关卡 $i$ 到关卡 $(i + 1)$ 所需的期望步数。
那么有：
那个 1 就是你无论赢不赢你都要打一盘，赢了就直接过关了，输了就还要加上后面的 $(1 - p_i)(f_{i - 1} + f_i)$ 的代价。
然后那个 $(1 - p_i)$ 就是输了的概率嘛，你输了就会回到第 $(i - 1)$ 关嘛对不对。
然后你再花 $f_{i - 1}$ 局的期望步数到关卡 $i$，然后再花 $f_i$ 的期望局数过关嘛对吧。
然后化简一下上述式子就可以 $O(n)$ 做啦。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <cstdio>
#define mod 998244353
#define maxN 1000010
long long f[maxN];
long long pow (long long x, long long y)
{
if(!y)
{
return 1;
}
else
{
long long dq = pow(x, y >> 1);
if(!(y & 1))
{
return dq * dq % mod;
}
else
{
return dq * dq % mod * x % mod;
}
}
}
long long inv (long long x)
{
return pow(x, mod - 2);
}
int main ()
{
long long n = 0;
scanf("%lld", &n);
long long A = 0, B = 0;
scanf("%lld %lld", &A, &B);
f[1] = B * inv(A) % mod;
long long Sum = f[1];
for(long long i = 1;i < n; i++)
{
long long x = 0, y = 0;
scanf("%lld %lld", &x, &y);
Sum = (Sum * (y * inv(x) % mod - 1) % mod) + (y * inv(x) % mod);
Sum %= mod;
f[i + 1] = f[i] + Sum;
f[i + 1] %= mod;
}
printf("%lld", f[n]);
return 0;
}
|