容斥原理
前言
萌新做了下 发现自己对容斥的理解完全不深入
容斥,顾名思义,就是分别算每个的贡献,然后减去重复的贡献。
我们考虑容斥的应用。
应用
求 满足 的个数
显然,我们考虑唯一分解定理,
我们考虑 的情况
换句话说 不能是 的倍数,这显然就是一个容斥原理。
1 | mmp=tmp; |
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
萌新做了下 发现自己对容斥的理解完全不深入
容斥,顾名思义,就是分别算每个的贡献,然后减去重复的贡献。
我们考虑容斥的应用。
显然,我们考虑唯一分解定理,
我们考虑 的情况
换句话说 不能是 的倍数,这显然就是一个容斥原理。
1 | mmp=tmp; |