当前位置: 首页 > news >正文

CF1265E题解

题目。

设 $f_i$ 表示问完了前 $i-1$ 面镜子,还期望要多少天。

有 $f_i=p_i f_{i+1}+(1-p_i)f_1 +1,f_{n+1}=0$ ,答案即为 $f_1$ 。

将递推式变形,有 $f_i-f_1=p_i(f_{i+1}-f_1)+1$。

记 $g_i=f_i-f_1$,则 $g_i=p_i g_{i+1}+1,g_{i+1}=\frac{g_i-1}{p_i},g_1=f_1-f_1=0$。

于是我们可以递推求出所有的 $g_i$ 。

因为 $f_n=p_n f_{n+1}+(1-p_n)f_1+1=f_1-p_n f_1+1$,所以 $f_n-f_1=g_n=1-p_n f_1,f_1=\frac{1-g_n}{p_n}$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
ll n,p[200005],g[200005],ans;
inline ll qpow(ll a,ll b){ll ret=1;while(b){if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1; }return ret;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;g[1]=0;for(int i=1;i<=n;i++){cin>>p[i];p[i]=p[i]*qpow(100,mod-2)%mod;g[i+1]=(g[i]-1+mod)%mod*qpow(p[i],mod-2)%mod;}ans=mod-g[n+1];cout<<ans;return 0;
}
http://www.wxhsa.cn/company.asp?id=1790

相关文章:

  • 数组中的第K大元素
  • Gitee:本土开发者生态的崛起与数字化转型新范式
  • 从本土化优势到全场景覆盖:Gitee如何重塑中国开发者的DevOps体验
  • 【2025-09-11】脆弱的睡眠
  • 正则表达式基础
  • 即时通讯管理平台(后台管理)介绍文档
  • HC32F460串口重定向printf
  • 一个我很喜欢的故事
  • paraview将所有时间步下的数据导入到同一个文件中
  • 代码托管新视野:打造本土化研发协作平台,赋能企业敏捷开发新范式
  • 202312_DASCTF_找找找
  • 浅谈博弈论
  • pyinstaller 打包
  • 基于STM32单片机与OV2640摄像头实现边缘检测
  • 替代FTP的国产传输软件哪个好?国产化文件传输工具推荐
  • 模拟运输振动试验台:保障产品运输安全的关键设备
  • 数据结构与算法-29.图-广度优先搜索
  • 政务外网和互联网啥关系
  • 什么是文件摆渡系统?从应用到优势全面解读!
  • wpf xaml数据绑定时,寻找数据源的几种方式 (RelativeSource)
  • 背负冲击试验机的设计原理与性能优化
  • 钢球落球试验机对汽车玻璃的测试应用
  • 基于STM32F047的ADS1299数据采集与低通滤波系统实现
  • LangChain
  • 军工企业涉密网文件导出用什么系统?答案在这里
  • Gateway 网关坑我! 被这个404 问题折腾了一年?
  • KUKA 机器人型号含义解析
  • LangChain DIfy区别
  • tricks
  • 英语_阅读_water in our body_待读