[补题记录] Atcoder Beginner Contest 295(E)

2023-10-14 18:28

本文主要是介绍[补题记录] Atcoder Beginner Contest 295(E),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

URL:https://atcoder.jp/contests/abc295

目录

E

Problem/题意

Thought/思路

Code/代码


E

Problem/题意

给定长度为 N 的数组 A。进行如下操作:

  • 若 Ai = 0,将 Ai 等概率地变为 1 ~ M 中的任意一个数;
  • 对 A 排序;

问第 K 个数地期望是多少。

Thought/思路

概率 DP。(一开始想不明白这个公式,概率论白雪了)

设我们要求的 A[k] = x 且 P[i] 为 x = i 的概率,那么就有如下公式:

E(x) = \sum_{i=1}^{m}i*P(i=x)=\sum_{i=1}^{m}P(x \geqslant i)

 关于这条公式地推导:https://zhuanlan.zhihu.com/p/617048570

因此接下来的问题就变成了:对于每个 i,求出 P(A[k] >= i)。


但是我们不知道 A[k] 该怎么取值,所以还需要将 P(A[k] >= i) 转换为:后面 N - K + 1 个数 >= i 的概率,也就是 [K, N] 中的数都 >= i 的概率。(假设已经排好序)

显然 [K, N] 中的数不会都 >= i,而一般的情况就是:[K, N] 中的前一部分的数 < i、后一部分的数 >= i。


对于前一部分,我们需要依靠 0 来变成 >= i 的数去替换他们,所以记录前一部分的数的个数为 need,这代表了所需要的 0 的最少数量。

也就是说,如果 0 的数量(设为 zero)zero < need,那么就永远不可能满足 [K, N] 中的数都 >= i,概率为 0;反之,如果 need <= 0,就一定满足 [K, N] 中的数都 >= i,概率为 1;


基于概率为 0 的那种情况,就一定能保证 need <= zero。

而 need 是需要的 0 的最少数量,那么我们就可以设:有 need 个 0 变成了 >= i 的数,其带来的概率为:

p(need) = C_{zero}^{need} * P^{need} * (1 - P)^{zero-need}

 其中 P = (m - i + 1) / m,意思是:取出 >= i 的数的概率。

显然一共有 zero 个 0 可以使用,所以考虑 [need, zero] 每一种情况即可。

Code/代码

#include "bits/stdc++.h"#define int long longconst int mod = 998244353;int n, m, k, a[2007], fact[2007], invf[2007];int ksm(int a, int b) {int res = 1;while (b > 0) {if (b & 1) res = res * a % mod;a = a * a % mod;b /= 2;}return res;
}void init() {fact[0] = 1, invf[0] = ksm(1, mod - 2);for (int i = 1; i <= 2000; ++ i) {fact[i] = fact[i - 1] * i % mod;invf[i] = ksm(fact[i], mod - 2) % mod;}
}int C(int x, int y) {if (x < y) return 0;return fact[x] * invf[y] % mod * invf[x - y] % mod;
}signed main() {std::cin >> n >> m >> k;for (int i = 1; i <= n; ++ i) std::cin >> a[i];init();int ans = 0;for (int i = 1; i <= m; ++ i) {int zero = 0, need = n - k + 1;for (int j = 1; j <= n; ++ j) {if (a[j] >= i) need --;if (a[j] == 0) zero ++;}if (need <= 0 or need > zero) { // [k, n] 都 >= i,概率为 1;[k, n] 小于 i 的个数,0 补不上,概率为 0。ans = (ans + (need <= 0 ? 1 : 0)) % mod;continue;}int p1 = (m - i + 1) * ksm(m, mod - 2) % mod; // 选出的数 >= i 的概率 p:(m - i + 1) / mint p2 = (i - 1) * ksm(m, mod - 2) % mod; // 1 - p:(i - 1) / mstd::vector <int> dp1(zero + 1), dp2(zero + 1);dp1[0] = dp2[0] = ksm(1, mod - 2);for (int j = 1; j <= zero; ++ j) {dp1[j] = dp1[j - 1] * p1 % mod;dp2[j] = dp2[j - 1] * p2 % mod;}// 用 0 补充 >= i 的数for (int j = need; j <= zero; ++ j) {ans = (ans + C(zero, j) * dp1[j] % mod * dp2[zero - j] % mod) % mod;}}std::cout << ans;return 0;
}

这篇关于[补题记录] Atcoder Beginner Contest 295(E)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/212314

相关文章

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后,需要到系统环境变量中添加两个变量2. 第3步 “在cmd中

Spring Retry 实现乐观锁重试实践记录

《SpringRetry实现乐观锁重试实践记录》本文介绍了在秒杀商品SKU表中使用乐观锁和MybatisPlus配置乐观锁的方法,并分析了测试环境和生产环境的隔离级别对乐观锁的影响,通过简单验证,... 目录一、场景分析 二、简单验证 2.1、可重复读 2.2、读已提交 三、最佳实践 3.1、配置重试模板

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述:异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明