CF1265E Beautiful Mirrors 题解

本题为期望 DP 入门题。

为了方便，下面直接认为 \(p_i\) 就是概率。

首先设状态，\(f_i\) 为从第一面镜子到第 \(i\) 面镜子都高兴的期望天数。

然后列方程：

1. 第 \(i\) 天询问失败，从头开始。
   此时概率为 \(1-p_i\)，消耗天数为 \(f_{i-1}+1+f_i\)，于是概率乘代价为 \((1-p_i)(f_{i-1}+1+f_i)\)。
2. 第 \(i\) 天询问成功。
   此时概率为 \(p_i\)，消耗天数 \(f_{i-1}+1\)，于是概率乘代价为 \(p_i(f_{i-1}+1)\)。

综上，有 \(f_i=(1-p_i)(f_{i-1}+1+f_i)+p_i(f_{i-1}+1)\)。

然而 \(p_i\) 只是概率，真正代码中还需要除以 100 才行。

除以 100 之后最后解得 \(f_i=\dfrac{100(f_{i-1}+1)}{p_i}\)，线性递推即可，不要忘记逆元。

代码：

#include 
using namespace std;

typedef long long LL;
const int MAXN = 2e5 + 10, P = 998244353;
int n, p[MAXN];
LL f[MAXN];

int read()
{
	int sum = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
	return sum * fh;
}

LL ksm(LL a, LL b)
{
	LL ans = 1 % P;
	for (; b; b >>= 1)
	{
		if (b & 1) ans = ans * a % P;
		a = a * a % P;
	}
	return ans;
}

int main()
{
	n = read();
	for (int i = 1; i <= n; ++i) p[i] = read();
	for (int i = 1; i <= n; ++i) f[i] = 100ll * (f[i - 1] + 1) % P * ksm(p[i], P - 2) % P;
	printf("%lld\n", f[n]);
	return 0;
}