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

容斥与二项式反演

先挖坑,后填坑。


容斥

容斥,实际上就是用总的方案数减去不合法的方案数。

我们考虑以下组合恒等式:

\[\sum_{i = 0}^{n} (-1) ^ {i} C_{n}^{i} = [n = 0] \]

为什么这个式子跟容斥有关呢?

我们考虑不合法的数量为 \(n\),如果我们计算 \(n\) 的子集并且乘上容斥系数后,你就会发现答案只有在 \(n = 0\) 时有值,所以这个就是对的。

分特产

我们考虑钦定 \(i\) 个人不选特产,其余任意的方案数,这个可以用挡板法解决,所以答案就为:

\[\sum_{i = 0}^{n - 1} (-1)^{i} C_n^i \prod_{j = 1}^m C_{a_j + n - i - 1}^{a_j} \]

硬币购物

我们先考虑没有硬币的情况,可以发现这个可以直接用多重背包预处理来做。

那么现在加上限制后我们考虑容斥,我们枚举至少集合内不满足条件,那么这个只需要减一减然后再乘个容斥系数就做完了。

[SDOI2013] 方程

我们这里只考虑模数是质数的情况。

首先没有限制是好做的,直接挡板法即可,然后你就会发现第二种限制也是好做的,可以理解为在这个集合内拿走一些数,之后我们在考虑容斥,把第一种限制转换为第二种限制,然后就做完了。

水仙花

我们注意到连续的一段钦定不合法的长度不会超过 \(\log_2 m\) 之后我们预处理一个东西,设 \(pre_{i,j}\) 表示连续不合法长度为 \(i\),结尾为 \(j\) 的方案数,这个是好转移的,之后对于同一长度的求个和,记为 \(sum_i\),目前复杂度 \(O(m \log_2^2 m)\)

之后我们利用容斥先写出答案的表达式:

\[ans = \sum_{i = 0}^n f(i) \ \ (-1)^i \]

其中我们设 \(f(i)\) 表示钦定 \(i\) 个不合法方案数,我们上魔法,根据上面的式子设计出来一个 dp,我们设 \(dp_i\) 表示考虑到前 \(i\) 个数的答案,那么就有如下转移:

\[dp_i = \sum_{i = 1}^{\log_2 m} dp_{j - i} \ \ sum_j \ \ (-1)^{j - 1} \]

之后就没了。

二项式反演

To Be Continued

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

相关文章:

  • react useCallback Hook详解
  • 从Docker构建失败到CRA被淘汰:一个React项目的ES模块探索记录
  • 充气泵PCBA方案中数字传感器和模拟传感器的差异
  • 实用指南:小米17手机的上市公司供应商
  • CDN + WAF + CLB + Higress 架构下的 TLS 加解密详细解析(适用阿里云)
  • react useMemo Hook详解
  • react useContext 详解
  • Python技能大赛-备赛建议
  • 【软件系统架构】系列七:系统性能——操作系统性能深入解析 - 实践
  • 你的下一款定位神器,何必是GPS?Nordic带你解锁Wi-Fi SSID的隐藏潜能
  • CF407E k-d-sequence 题目分析(0929模拟赛最后一题)
  • Linux 生成随机端口
  • MATLAB 中 dsp.FFT 系统对象:从原理到实践的完整指南
  • 并发编程可见性
  • C# Devexpress GridControl实现全选功能(转载,记录)
  • github Connection reset by 20.205.243.160 port 443 fatal: Could not read from remote repository.
  • VsCode Ai插件
  • 完整教程:基于完全分布式模式部署Hadoop(喂饭教程)
  • Vue 3.6 引入 Vapor Mode,虚拟DOM已死?
  • part 10
  • Nordic发布用于nRF54L系列的nRF Connect SDK裸机选项
  • 微软SSO集成中的顺序用户ID身份验证绕过漏洞剖析
  • content和text方法的区别
  • shell脚本动态域名解析阿里云
  • 聪明的wyk
  • Windows下进程和账户权限
  • Spring Gateway动态路由实现方案 - 详解
  • Nordic 高性能无线SoC nRF54LM20A,专为低功耗蓝牙与Matter设计
  • 调用setState 之后发生了什么?
  • element plus 配置主题色