容斥小结

容斥小结

HNOI/AHOI2018毒瘤

JLOI/SHOI2016黑暗前的幻想乡

JLOI/SHOI2016方

pro

求n条限制的方案数

sol

枚举(2^n)次方,打破了哪些限制

答案=至少打破0个限制-至少打破1个限制+至少打破2个限制-至少打破3个限制……

HAOI2018染色

JLOI/SHOI2016成绩比较

pro

至少和恰好之间转换

sol

二项式反演

【*****】与上面最少与至少不同的是这里不确定选了哪些,只是用组合数表示方案数,而上面那种是枚举每一种情况再容斥

CEOI2019游乐园

pro

给边,自定方向,求(DAG)数量

sol

子集容斥

子集反演,针对的是集合交并的容斥。

二项式反演,针对组合原理的容斥。

莫比乌斯反演,针对约数和倍数的容斥。

斯特林反演,针对集合划分的容斥。

最值反演(Min_Max容斥),针对集合元素出现的最值的反演。

AHOI/HNOI2017抛硬币

简单容斥,考虑哪些算重了即可

好难┭┮﹏┭┮……

原文地址:https://www.cnblogs.com/aurora2004/p/12917815.html