[2016北京集训测试赛5]azelso-[概率/期望dp]
2024-08-25 20:50:28
Description
Solution
感谢大佬的博客https://www.cnblogs.com/ywwyww/p/8511141.html
定义dp[i]为[p[i],p[i+1])的期望经过次数,f[i]为处理完事件i后不会再回到i点或以前,直接到终点的概率。
则$dp[i]=1+(1-f[i])+(1-f[i])^{2}+......=\frac{1}{f[i]}$
设事件i+1的胜率为k。
1:下一个事件是敌人,则f[i]=kf[i+1],即$dp[i]=\frac{dp[i+1]}{k}$。
2:下一个事件是旗子,则$f[i]=f[i+1](1+k(1-f[i+1])+k^{2}(1-f[i+1]^{2}+...)=\frac{f[i+1]}{1-k+kf[i+1]}$
把f替换为dp得$dp[i]=(1-k)dp[i+1]+k$
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int mod=1e9+;
typedef long long ll;
ll ksm(ll x,ll k)
{
ll re=;
while (k)
{
if (k&) re=re*x%mod;
k>>=;
x=x*x%mod;
}
return re;
}
ll h,n;
ll p[],a[],b[];char c[][];
ll dp[],ans=;
int main()
{
scanf("%lld%lld",&h,&n);
for (int i=;i<=n;i++)
{
scanf("%s%lld%lld%lld",c[i],&p[i],&a[i],&b[i]);
a[i]=a[i]*ksm(b[i],mod-)%mod;
}
dp[n]=;
for (int i=n;i;i--)
if (c[i][]=='X') dp[i-]=dp[i]*ksm(a[i],mod-)%mod;
else dp[i-]=((-a[i]+mod)%mod*dp[i]%mod+a[i])%mod;
p[n+]=h;
for (int i=;i<=n;i++) ans=(ans+(p[i+]-p[i])%mod*dp[i]%mod)%mod;
cout<<ans;
}
最新文章
- JQuery 获得div绝对,相对位置的坐标方法
- method
- 中文Locale
- PHP, LDAPS and Apache
- 辛巴学院-Unity-剑英陪你零基础学c#系列(一)Hello World
- 无IDE时编译和运行Java
- oracle储存过程,job,视图,触发器(记性不好,写个例子自己记)
- Spark问题记录
- Oracle EBS-SQL (PO-14):检查报价单与成本对比.sql
- windows如何获取Win10 Win8 Win8.1版本
- Angular - - ngClass、ngClassEven、ngClassOdd、ngStyle
- Spring Security 入门(1-3-3)Spring Security - logout 退出登录
- python中filter,reduce,map的用法
- 带你了解zabbix如何监控mysql主从到报警触发
- socket详解(二)----实例和多线程,线程池使用
- How to Conduct High-Impact Research and Produce High-Quality Papers
- matlab:统计矩阵中某元素的个数
- org.springframework.web.servlet.PageNotFound - No mapping found for HTTP request with URI
- Summary: gcd最大公约数、lcm最小公倍数算法
- TCP/IP协议和IP