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

9-30

AT_arc102_c

非常好的容斥题。

首先我们显然要枚举不能等于的点数 \(x\),然后发现两个筛子点数 \(\ne x\) 并不好做。

接下来的推导都是在我们确定 \(x\) 的情况下的。

考虑将限制转化为不存在任意筛子组合的 \((p, x - p)\),满足 \(1 \le p \le x - p \le k\),根据列出的不等式,容易发现整数对的个数为 \(y = \left \lfloor x / 2 \right \rfloor - \max(x - k, 1) + 1\) 个。

这题的妙处就在于它是对不满足条件的对数(相同的算作一对)容斥。也就是我们不在乎整数对内部具体地数值,只在乎他们的对数。这样做的好处是后面可以方便地计算他们的方案数。

然后计算至少 \(i\) 对的组合的方案数设为 \(g_i\),则显然从 \(y\) 种数对中选择 \(i\) 对的方案数为 \(\binom{y}{i}\),剩下有 \(n - 2i\) 个数,因为是容斥,有至少的限制,所以剩下的可以任意分配。考虑插空法,就是将 \(n - 2i\)无差别的筛子分为 \(k\) 组,每组可以空,于是方案数为 \(\binom{n - 2i + k - 1}{k - 1}\)

我们得出 \(g_i = \binom{n - 2i + k - 1}{k - 1}\)。考虑其容斥系数为 \((-1)^i\),将 \(g_i\) 相加。我们就得出了对于每个 \(x\) 的答案。

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

相关文章:

  • 探索 Nim 中的 sequtils 与箭头语法 —— 立即计算与惰性计算的那些事
  • 250930
  • Gitee:中国开发者生态中的本土化代码托管领导者
  • 价值博弈白箱:元人文AI的可审计未来
  • 八段锦
  • Gitee崛起:中国开发者生态的破局者与赋能引擎
  • 【VMware Workstation】Debian 13 桌面版安装
  • B树,B+树技术分享
  • 无管理员权限电脑完成MySQL数据库创建流程
  • 机台设备数据管理:提升生产效率的关键策略
  • 【瑶池数据库动手活动及话题精选(体验Dify on DMS,参与Meta Agent讨论)】
  • 时钟设计优化实战
  • 河南外贸建站 | 河南外贸建站公司 | 河南外贸独立站定制 - 详解
  • kuboard使用的etcd空间清理(3个etcd)
  • 死锁的处理策略-预防死锁
  • 跨网文件安全交换系统:提升数据传输安全性和合规性
  • 随笔
  • 强化学习、深度学习、大模型、智能体
  • Node生态中最优雅的数据库事务处理机制
  • 详细介绍:扒透 STL 底层!map/set 如何封装红黑树?迭代器逻辑 + 键值限制全手撕----《Hello C++ Wrold!》(23)--(C/C++)
  • 期货市场API对接完全指南:实时行情获取与实战应用
  • Tomcat使用redis管理session
  • NOC片上网络总线初探
  • AT_agc037_c [AGC037C] Numbers on a Circle
  • 记账本|基于SSM的家庭记账本小程序设计与实现(源码+数据库+文档) - 实践
  • redis数据连接写法
  • 缩放 div
  • 死锁的概念
  • 【2025-09-29】团队合作
  • 杂凑算法学习笔记