当前位置: 首页 > news >正文

P13969 [VKOSHP 2024] Exchange and Deletion

赛时状态极差,打醉拳想出来的奇怪概率做法。

首先前 \([1,n-k]\) 的位置是等效的。先刻画 \(b\) 的限制,发现 \(a\) 中前 \(n-k\) 个位置中被操作过的位置一定比没操作过的位置大,且其它位置一定是单调递增,于是在 \(b\) 中其它位置形成的子序列必然是一个有序的排列,即 \([1,2,3,\cdots]\)

\(b\) 的作用就是限定了被操作位置数的范围,显然我们并不需要关系被操作的是哪些位置,只需要关心数量即可。并且我们已经确定了这些位置的唯一顺序,所以我们计数时将后面的值视为无序,只需要关心有多少种方案使得操作设计设计到了 \(l\) 个位置即可。

注意到对于 \(\forall i\in[1,n-k],j\in[n-k+1,n]\),满足 \(P(a_i=j)=\frac 1 n\)

证明可以考虑归纳。归纳时我们保持 \(n\) 不变是好的,现在考虑往前面加一个数,也就是 \(k\leftarrow k+1\),对于当前 \(n-k+1\) 的数,前面 \(a_i=n-k+1\) 的概率是 \(\frac {n-k+1}{n}\times \frac 1 {n-k+1}=\frac 1 n\)。对于后面的数有两种情况,一种是提前被选且 \(n-k+1\) 没覆盖,概率为 \(\frac 1 n\times\frac {n-k}{n-k+1}\),另一种是 \(n-k+1\) 已经提前被要的值选了,概率为 \(\frac 1 n\times\frac {1}{n-k+1}\),加起来恰为 \(\frac 1 n\)

考虑对涉及到 \(l\) 个位置计数。我们不妨利用条件概率,先把操作框在前 \(l\) 个位置和后 \(k\) 个位置之间,概率为 \(\prod_{i=1}^k \frac{l+k-i+1}{n-i+1}=\frac{(l+k)!(n-k)!}{l!n!}\)。然后在这些数之间,我们先选出 \(\binom{k}{l}\) 个数出来,然后对于一种方案的概率有 \(\frac{k!}{(l+k)!}\),感性理解一下,确定了一个数的值后,确定下一个值的难度与删去一个位置是等效的。严谨证明可能比较屎,我有一个证明,这里太小了写不下。如果有简洁证明的巨佬可以教教我~

http://www.hskmm.com/?act=detail&tid=21517

相关文章:

  • Matlab 通用库的fft和dsp toolbox的dsp.fft对比
  • [CTS2024] 众生之门
  • [CEOI 2025] Equal Mex
  • [ROI 2018] Quick sort
  • CF2127F Hamed and AghaBalaSar
  • 2025 年PPH 管厂家推荐榜单:江苏镇江扬中优质 PPH 管道/管材/管件厂家权威精选
  • Label-Free Liver Tumor Segmentation
  • CF1951G Clacking Balls
  • [ABC311Ex] Many Illumination Plans
  • 2025 预分散颜料厂家最新推荐榜:超高含量技术 + 合规企业全景指南,纺丝 / 吹膜专用产品选型手册
  • 倍增思想与其优化
  • 2025 年 AI 健康管理领域推荐深护智康,社区、基层公卫、母婴 AI 健康管理、AI + 大健康管理、AI 健康管理师公司推荐
  • 2025 最新权威推荐:全国开锁公司口碑排行榜,含智能锁专项服务与紧急上门品牌详解汽车保险柜开锁/汽车锁开锁/保险柜开锁/智能开锁/快速上门开锁公司推荐
  • 从“看得见”到“能决策”:Operation Intelligence 重构企业智能运维新范式
  • 实用指南:Ubuntu 中 Bash / Zsh / Ash / Dash 的使用与区别(含对比图)
  • 2025 年杭州软件开发公司最新推荐榜单:聚焦服务经验与售后体系的五大优质公司权威指南
  • Nginx 与 LNMP 架构部署 - 详解
  • QMT委托对象orderInfo的属性以及对应的值
  • 2025 年电动门厂家最新推荐排行榜:实力厂家深度解析,含技术认证、案例及选购指南
  • 2025 年透骨液膏药代理加盟 / 足浴包膏药代理加盟 / 青岛膏药代理加盟推荐:青岛步泽药业布泽草本透骨液代理合作解析
  • 单链表实现队列
  • 死锁易错知识点整理
  • 2025广州1688代运营服务商推荐排行榜,阿里巴巴全店,实力商家,店铺装修,产品推广,流量优化,国际站,新店起量,数据分析,爆款打造代运营公司推荐
  • 2025 海南财税公司最新推荐榜:三亚海口代理记账 / 税务合规服务机构权威解析海南代理财税/海南财税代理/海南注册公司财税/海南代理记账财税公司推荐
  • 2025 年 TM 芯片经销商最新推荐榜:聚焦规模化采购与敏捷物流, 实力解析
  • 2025 天微芯片经销商最新推荐榜:品牌实力测评与采购指南 —— 权威揭秘优质服务商选择标准
  • 读人形机器人27太空中
  • 2025 年酒店一次性用品源头厂家最新推荐榜单:含牙签牙线筷子套杯盖等全品类及采购选择指南酒店一次性牙签/牙线/筷子套/杯盖/杯垫/杯套用品 厂家推荐
  • 2025 年餐饮一次性用品实力厂家最新推荐榜单:覆盖牙签 / 牙线 / 筷子套 / 杯盖 / 杯垫多品类且资质口碑双优的标杆企业权威甄选
  • 校内模拟赛 路径 题解