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

2023-10-14 19:15

本文主要是介绍[补题记录] 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/212563

相关文章

Python MySQL如何通过Binlog获取变更记录恢复数据

《PythonMySQL如何通过Binlog获取变更记录恢复数据》本文介绍了如何使用Python和pymysqlreplication库通过MySQL的二进制日志(Binlog)获取数据库的变更记录... 目录python mysql通过Binlog获取变更记录恢复数据1.安装pymysqlreplicat

Servlet中配置和使用过滤器的步骤记录

《Servlet中配置和使用过滤器的步骤记录》:本文主要介绍在Servlet中配置和使用过滤器的方法,包括创建过滤器类、配置过滤器以及在Web应用中使用过滤器等步骤,文中通过代码介绍的非常详细,需... 目录创建过滤器类配置过滤器使用过滤器总结在Servlet中配置和使用过滤器主要包括创建过滤器类、配置过滤

正则表达式高级应用与性能优化记录

《正则表达式高级应用与性能优化记录》本文介绍了正则表达式的高级应用和性能优化技巧,包括文本拆分、合并、XML/HTML解析、数据分析、以及性能优化方法,通过这些技巧,可以更高效地利用正则表达式进行复杂... 目录第6章:正则表达式的高级应用6.1 模式匹配与文本处理6.1.1 文本拆分6.1.2 文本合并6

python与QT联合的详细步骤记录

《python与QT联合的详细步骤记录》:本文主要介绍python与QT联合的详细步骤,文章还展示了如何在Python中调用QT的.ui文件来实现GUI界面,并介绍了多窗口的应用,文中通过代码介绍... 目录一、文章简介二、安装pyqt5三、GUI页面设计四、python的使用python文件创建pytho

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图