HDU 6568 Math
2024-10-06 09:32:26
Math
\(f_i\)为从\(i\)到\(i+1\)的期望步数。
\(f_i = 1-p + p(f_i + 2((1-q)^{n-i}(n-i) + q\sum_{j=0}^{n-i-1}(1-q)^{j}j))\)
移项相减得:
\(f_i = 1+\frac{2p((1-q)^{n-i}(n-i) + q\sum_{j=0}^{n-i-1}(1-q)^{j}j)}{1-p}\)
然后预处理一个前缀和就可以了。
代码:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head
const int N = 1e5 + 10;
int n;
double p, q, _q[N], sum[N];
int main() {
while(~scanf("%d %lf %lf", &n, &p, &q)) {
sum[0] = 0;
_q[0] = 1;
for (int i = 1; i <= n; ++i) {
_q[i] = _q[i-1]*(1-q);
sum[i] = sum[i-1] + _q[i]*i;
}
double ans = 0;
for (int i = 0; i < n; ++i) {
ans += 1+(2*p*(_q[n-i]*(n-i)+q*sum[n-i-1]))/(1-p);
}
printf("%.10f\n", ans);
}
return 0;
}
最新文章
- 关于C#操作防火墙,阻止程序联网
- jquery学习方法
- EF ASP.NET MVC 更新出错:ObjectStateManager中已存在具有同一键的对象
- 用jquery实现简单的表单验证
- Sonar+Hudson+Maven构建系列之一:安装Sonar
- web.xml中JSP配置及 EL表达式
- PCA主成分分析
- AbstractRoutingDataSource实现动态数据源切换 专题
- 2016/12/22 dplの课练
- sqlserver 分割字符串和调用
- 【JVM】查看JVM加载的类及类加载器的方法
- leetcode 90. subsets
- JAVA条件语句:if;switch case
- macbook 下 spark开发环境搭建(基于idea 和maven)及spark单机写运行jar
- Hive记录-Hive介绍(转载)
- Codeforces 820B - Mister B and Angle in Polygon
- tomcat版本号的修改
- bzoj1050 旅行
- Django之XSS攻击
- MSVC與CRT的恩怨情仇