CFdiv2-Beautiful Mirrors-(期望)

E

题意：
就是有n个魔镜，小A每天都会问镜子，每个镜子说小A美丽的概率为p[i]。如果这个镜子说自己很美，那么下一天会问下一个镜子，如果没有下一个镜子了，那么这一天小A就很开心并且就停止了。如果说小A不美，那么小A下一天会从第一个镜子重新问。问你小A停止的时候天数的期望是多少。

思考：

1. 由于一段时间没做期望有点淡忘。看到这题就感觉是很经典的题目，这种没有转移的一般不是期望dp。然后我就想直接套期望的几个公式？要么直接求第i天停止的概率，但是发现不好求。那么可以用公式所有>=i的概率之和，但是这个也不好求。要么是套路概率？成功是p,不成功是(1-p)，那么期望就是1/p。但是这题目不使用这个套路，这个套路是不成功的哪个情况，永远都是走向不成功的，但是这个题目不成功的方向也可能会走向成功的地方。
2. 但是之前过一道题，就是给你一条链，问你从1走到n的期望步数。这个题目也是不能套公式，也不适用套路，这个也是往左右后也可能往右边走，所以不使用套路。
3. 这俩题是一类题。先说从1走到n的题目，如果直接求也不好求，由于期望的线性可加性，那么就可以定义一下xi的状态，让这个题目变得更好求一点。定义x_i为从i走到i+1的期望步数。当我走到i点的时候，下一步要么走向i+1，要么走向i-1。如果直接走到i+1不用说了，如果走到i-1呢？如果走到i-1我还知道E(x_i-1)的期望。那么E(x_i)是不是就求出来和E(x_i-1)的关系式了，那么就可以把所有的都推成关于E(x₁)的关系式子。而且E(x_i) = 1。那么这个题目就求出来了，可以发现对于每个点i，他一般就和几个点相关，那么如果相关的这几个点我知道期望，是不是i点的期望就可以求出来了，那么整个题目就解决了。首先你定义之后，一定要有一个点的期望是个已知的值，这样式子都推成关于这个值的关系式，最后求一下就可以了。
4. 现在再看看这个题。如果我定义x_i为从第i个镜子走到第i+1个镜子的期望步数，那么总期望就是这些的期望总和。推出来式子发现不好求。
   虽然E(x₁)可以确定，但是不好求出每个E(x_i)与E(x₁)关系式。这个定义方式就是照着上个题目定义的，所以可以看出，不同的题目定义方式还是要有一些独特的变化，解决本问题才会更简单。
5. 那么我如果定义x_i为从第i个镜子开始到停止的期望步数。那么可以确定的状态就是E(x_n+1) = 0，因为它已经超过最后一个镜子了。那么推一推式子：
   
   所以就求出来了E(x₁)就是答案
6. 所以这个题目也是从i点可以走向下一个点，也可以走向别的点，只要我把所有可以走的方向的期望都已知了，那么可以推出一个关于某个已知变量的关系式，那么题目就迎刃而解了。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 998244353,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];

int ksm(int a,int b)
{
	int sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return sum;
}

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i];
	int up = 0,down = 1,sum = 0,tp = ksm(100,mod-2)%mod;
	for(int i=1;i<=n;i++)
	{
		up = (up+down)%mod;
		down = down*va[i]%mod*tp%mod;
	}
	sum = up*ksm(down,mod-2)%mod;
	sum = (sum%mod+mod)%mod;
	cout<<sum;
	return 0;
}
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

总结：
多多思考，掌握本质。