开发者社区云计算文章正文

CF1265E Beautiful Mirrors （概率dp）

2022-12-01 74

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： CF1265E Beautiful Mirrors （概率dp）

原题链接

思路：

d p [ i ]表示走到第i ii个镜子的期望天数：

d p [ i ] = ( d p [ i − 1 ] + 1 ) ∗ p [ i ] + ( 1 − p [ i ] ) ∗ ( d p [ i − 1 ] + 1 + d p [ i ] )

当这个镜子说她漂亮时，只需要花费1天；

否则，需要从起点重新开始，也就是d p [ i ]

化简得：

其中

(x为输入的数)

注意求逆元的时候要用long long

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+100,mod=998244353;
ll n,p[maxn],dp[maxn];
ll ksm(ll a,ll b){
  ll res=1;
  while(b){
    if(b&1) res=res*a%mod;
    a=a*a%mod;
    b>>=1;
  }
  return res;
}
int main(){
  ll n;cin>>n;  
  dp[0]=0;
  for(int i=1;i<=n;i++){
    cin>>p[i];
  }
  for(int i=1;i<=n;i++){
    dp[i]=(dp[i-1]+1)%mod*100%mod*ksm(p[i],mod-2)%mod;
  }
  cout<<dp[n]<<endl;
  return 0;
}