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

CF2127F Hamed and AghaBalaSar

真是个美难题。

首先不难发现一个序列的贡献被分成了若干段,每一段最后一个位置是最大值,否则不是最大值。而一个段的贡献是最大值减去这个段的第一个数。

首先我们要对这个贡献进行统计就需要寻找统计思路。我们考虑枚举最大值,这样我们发现我们枚举有多少最大值复杂度是对的,这是经典的调和级数。

但是现在仍然不好计算。我们需要关心每个段第一个数的贡献,还要大概知道段是怎么分的,会不会存在只有一个值在一段的情况,还要限制每一个位置的大小。。。这看起来并不好统计。

我们可以考虑拆贡献,对于每个位置计算贡献。在算贡献前我们得先推出总方案数的式子。我们考虑有多少最大值为 \(k\) 的合法序列。显然我们可以考虑插板,但是我们要限制 \(\forall 1\le i<n, a_i\le k\),我们可以使用容斥解决,我们钦定一些位置超过了 \(k\),此时我们不妨设:

\[f(n,m,k)=\sum_{i=0} (-1)^i\binom{n}{i}\binom{m-i(k+1)+n-1}{n-1} \]

那么对于最大值为 \(k\) 的合法序列个数即为 \(f(n-1,m-k,k)\)

对于最大值的位置贡献是好算的,首先对于最后一个位置的贡献显然为 \(k\times f(n-1,m-k,k)\)。然后对于其它位置的贡献也很好算,总和为 \((n-1)k\times f(n-2,m-2k,k)\)

然后考虑算每一段第一个数的贡献,我们显然不能够枚举第一个数是什么,但是我们知道我们要统计的是所有合法情况的第一个数的和,我们发现除了第 \(n\) 个位置以外前 \(n-1\) 个位置的限制是等价的,那么第一个数的贡献显然就是 \(\frac {m-k}{n-1}\times f(n-1,m-k,k)\)。然后对于 \(\forall 1<i<n\) 的位置的贡献也大差不差,首先要求 \(a_{i-1}=k\),然后都是相当于是求在所有 \(f(n-2,m-2k,k)\) 种方案中这一个位置的数的和,同样每个位置也是等价的,那么每个位置的贡献就是 \(\frac {m-2k}{n-2}\times f(n-2,m-2k,k)\),最后有 \(n-2\) 个位置,把分母约掉即可。别忘了 \(a_n\) 也可以产生贡献,而它的贡献及其简单,就是 \(k\times f(n-2,m-2k,k)\)

我们发现对于每个 \(k\) 只需要求出 \(f(n-1,m-k,k)\)\(f(n-2,m-2k,k)\) 就可以直接算答案了。想做出这道题感觉主要的难点是想到拆贡献以及在算贡献的时候注意到位置的等价使得我们可以利用类似概率的思想去简化式子。代码。

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

相关文章:

  • 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 年餐饮一次性用品实力厂家最新推荐榜单:覆盖牙签 / 牙线 / 筷子套 / 杯盖 / 杯垫多品类且资质口碑双优的标杆企业权威甄选
  • 校内模拟赛 路径 题解
  • 05-FreeRTOS的内存管理
  • 2025攻丝机品牌最新权威推荐排行榜:聚焦全自动攻丝机,半自动等机型,精选攻丝机实力厂商助企业高效选购
  • 软件测试覆盖率详解
  • oppoR9m刷Linux系统: 说明-注意事项-知识点
  • 手机框架材质