当前位置:网站首页>CFdiv2-Beautiful Mirrors-(期望)
CFdiv2-Beautiful Mirrors-(期望)
2022-08-10 22:10:00 【可爱美少女】
题意:
就是有n个魔镜,小A每天都会问镜子,每个镜子说小A美丽的概率为p[i]。如果这个镜子说自己很美,那么下一天会问下一个镜子,如果没有下一个镜子了,那么这一天小A就很开心并且就停止了。如果说小A不美,那么小A下一天会从第一个镜子重新问。问你小A停止的时候天数的期望是多少。
思考:
- 由于一段时间没做期望有点淡忘。看到这题就感觉是很经典的题目,这种没有转移的一般不是期望dp。然后我就想直接套期望的几个公式?要么直接求第i天停止的概率,但是发现不好求。那么可以用公式所有>=i的概率之和,但是这个也不好求。要么是套路概率?成功是p,不成功是(1-p),那么期望就是1/p。但是这题目不使用这个套路,这个套路是不成功的哪个情况,永远都是走向不成功的,但是这个题目不成功的方向也可能会走向成功的地方。
- 但是之前过一道题,就是给你一条链,问你从1走到n的期望步数。这个题目也是不能套公式,也不适用套路,这个也是往左右后也可能往右边走,所以不使用套路。
- 这俩题是一类题。先说从1走到n的题目,如果直接求也不好求,由于期望的线性可加性,那么就可以定义一下xi的状态,让这个题目变得更好求一点。定义xi为从i走到i+1的期望步数。当我走到i点的时候,下一步要么走向i+1,要么走向i-1。如果直接走到i+1不用说了,如果走到i-1呢?如果走到i-1我还知道E(xi-1)的期望。那么E(xi)是不是就求出来和E(xi-1)的关系式了,那么就可以把所有的都推成关于E(x1)的关系式子。而且E(xi) = 1。那么这个题目就求出来了,可以发现对于每个点i,他一般就和几个点相关,那么如果相关的这几个点我知道期望,是不是i点的期望就可以求出来了,那么整个题目就解决了。首先你定义之后,一定要有一个点的期望是个已知的值,这样式子都推成关于这个值的关系式,最后求一下就可以了。
- 现在再看看这个题。如果我定义xi为从第i个镜子走到第i+1个镜子的期望步数,那么总期望就是这些的期望总和。推出来式子发现不好求。
虽然E(x1)可以确定,但是不好求出每个E(xi)与E(x1)关系式。这个定义方式就是照着上个题目定义的,所以可以看出,不同的题目定义方式还是要有一些独特的变化,解决本问题才会更简单。 - 那么我如果定义xi为从第i个镜子开始到停止的期望步数。那么可以确定的状态就是E(xn+1) = 0,因为它已经超过最后一个镜子了。那么推一推式子:
所以就求出来了E(x1)就是答案 - 所以这个题目也是从i点可以走向下一个点,也可以走向别的点,只要我把所有可以走的方向的期望都已知了,那么可以推出一个关于某个已知变量的关系式,那么题目就迎刃而解了。
代码:
#include<bits/stdc++.h>
#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;
}
总结:
多多思考,掌握本质。
边栏推荐
- Qualcomm Platform Development Series Explanation (Application) Introduction to QCMAP Application Framework
- Redis
- 高数_复习_第5章:多元函数微分学
- Shell programming specification and variables
- Extended Chinese Remainder Theorem
- xshell (sed 命令)
- shell programming without interaction
- Regular expression of shell programming and text processor
- 测试4年感觉和1、2年时没什么不同?这和应届生有什么区别?
- 爬虫request.get()出现错误
猜你喜欢
随机推荐
file IO-buffer
What are the concepts, purposes, processes, and testing methods of interface testing?
Service - DHCP principle and configuration
配电网络扩展规划:考虑使用概率性能源生产和消费概况的决策(Matlab代码实现)
元宇宙社交应用,靠什么吸引用户「为爱发电」?
交换机和生成树知识点
亲测有效|处理风控数据特征缺失的一种方法
高数_复习_第5章:多元函数微分学
shell编程之正则表达式与文本处理器
字节跳动原来这么容易就能进去...
QT笔记——用VS + qt 生成dll 和 调用生成的dll
过滤器
ThreadLocal comprehensive analysis (1)
How to translate financial annual report, why choose a professional translation company?
STL-deque
学会开会|成为有连接感组织的重要技能
音乐播放器(未完成版本)
Addition of linked lists (2)
LeetCode Daily 2 Questions 02: Reverse the words in a string (1200 each)
2022年8月10日:使用 ASP.NET Core 为初学者构建 Web 应用程序--使用 ASP.NET Core 创建 Web UI(没看懂需要再看一遍)