CF1265E Beautiful Mirrors

CF1265E Beautiful Mirrors

洛谷CF1265E Beautiful Mirrors

题目大意

$\text{Creatnx}$有$n$面魔镜，每天她会问一面镜子：“我漂亮吗？”，第$i$面魔镜有$\frac{p_i}{100}$的概率告诉$\text{Creatnx}$她漂亮。

$\text{Creatnx}$从第$1$面镜子开始，每天询问一面镜子。对于第$i$面镜子，将会发生两种情况：

• 如果这面镜子告诉$\text{Creatnx}$她很漂亮：
  • 如果这是第$n$面镜子，那么$\text{Creatnx}$将会很开心并停止询问
  • 否则，$\text{Creatnx}$将在第二天询问第$i+1$面镜子
• 否则，$\text{Creatnx}$将会十分伤心，第二天重新从第$1$面镜子开始询问

求$\text{Creatnx}$停止询问的期望天数对$998244353$取模后的值。

$1\le n\le 2\times 10^5,1\le p_i\le 100$

题解

令$P_i=\frac{p_i}{100}$。

设$f_i$表示从第$i$面镜子开始直到停止询问的期望天数，则转移式如下：

$$f_i=P_i\times f_{i+1}+(1-P_i)\times f_1+1$$

也就是说，当前有$P_i$的可能走到第$i+1$面镜子，有$1-P_i$的可能走到第$1$面镜子。因为从当前的镜子走到另一面镜子需要花费一天的时间，所以要加$1$。

$f_{n+1}=1$，我们要求的是$f_1$。

但是，每个式子中都有$f_1$，所以我们考虑推式子。

先看$f_1$。

$$\begin{gathered} f_1=P_1{f}_2+(1-P_1)f_1+1 \\ {P}_1{f}_1=P_1{f}_2+1 \\ {f}_1=f_2+\frac{1}{P_1} \\ {f}_2=f_1-\frac{1}{P_1} \end{gathered}$$

再看$f_2$。

$$\begin{gathered} f_2=P_2{f}_3+(1-P_2)f_1+1 \\ {f}_1-\frac{1}{P_1}=P_2{f}_3+(1-P_2)f_1+1 \\ {P}_2{f}_1=P_2{f}_3+\frac{1}{P_1}+1 \\ {f}_1=f_3+\frac{1}{P_1{P}_2}+\frac{1}{P_2} \end{gathered}$$

我们可以发现，$f_1=f_{i+1}+\frac{1}{P_1{P}_2\cdots P_i}+\frac{1}{P_2{P}_3\cdots P_i}+\cdots +\frac{1}{P_i}$，也就是

$$f_1=f_{i+1}+\sum _{j=1}^i\prod _{k=j}^i\frac{1}{P_k}$$

我们知道$f_{n+1}=0$，那么就可以用这个式子来求$f_1$了。

时间复杂度为$O(n)$。

code

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,p[200005];
long long now=1,ans=0;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&p[i]);}for(int i=n;i>=1;i--){now=now*mi(p[i],mod-2)%mod*100%mod;ans=(ans+now)%mod;}printf("%lld",ans);return 0;
}