容斥系数

关于容斥系数:

8,9考试,建设城市:

考试时推+写了一个小时半,因为容斥系数卡了半天,一直在想之前做过的相似的集合计数的复杂系数。但最后不是,通过DP验证发现是最简单的正负1系数。

在一般容斥中都是1,-1,1,-1。保证每个点都只有1层。可用组合数推出。

而《集合计数》(见CQzhangyu  :https://www.cnblogs.com/CQzhangyu/p/7124411.html)

之所以不同,是因为1、他枚举的不是从第一层开始的,而是从第k层开始。

         2、并非每层全覆盖,而是只要第k层。

因此造成了与传统意义上容斥的不同。这是因为所求不同,范围不同。

所以一般题可以放心用一般容斥系数做。( 薇恩 图,奇加偶减)

本题:在有上下界(至少有a,至多有b)的计数中,任意可转化为不存在,则可斥掉 存在

Informatik verbindet dich und mich. 信息将你我连结。
原文地址:https://www.cnblogs.com/seamtn/p/11327251.html