一些条件，都要满足

为什么容斥问题会有一套专门的计算方法？

其实容斥问题是一种常见子集答案总和的信息，常见的求解方法为DP。

在求解过程中往往需要利用之前已经有了的信息，尝试整体转移，以优化时间复杂度。

定义

根据定义式： \(\sum_{S\subset T}(-1)^{|S|}f_S\) 进行计算，复杂度\(\mathcal O(2^n)\)

集合大小等价合并

只与集合大小有关，而不关心里面的元素，可以合并，用组合数表示其系数，复杂度 \(\mathcal O(n)\)

增量法

每次往集合中加入元素进行考虑。

设 \(g_i=\sum\limits_{S\subset\{1,2,\cdots,i-1\},T=S\cup\{i\}}(-1)^{|S|}f_T\)，表示为考虑前 \(i\) 个元素，确定 \(i\) 必选时的不满足条件的方案数量，在 \(g\) 之间进行 DP。

局部合法

整体都要合法的方案数 \(=\) 所有方案数 \(-\) \(\sum\) 一部分合法方案数 \(\times\) 另一部分无限制的方案数 \(\times\) 一个结合系数使得合起来不合法。

\(f_n=g_n-\sum_i f_i\times g_{n-i}\times c_{i,n-i}\)

\(\color{red}连通图计数\)

比如说 \(n\) 个点的联通图的方案数为 \(f_n\)，\(n\) 个点的图的的个数为 \(g_n\)，则：

意为枚举第\(n\)个点所在的连通块大小。

\(\color{red}等于=小于等于-小于\)

带容斥系数DP

就是将容斥系数当作方案的权值，变成一个方案权值和问题进行解决。

具体详见方案权值和问题。

枚举刚好不合法

即假设要求元素 \(\le a\)，那我就使得元素 \(=a+1\) ，进行求解

等价合并

即要求所有元素\(\le a\)，直接枚举\(=a\) 的数的个数。

\(\color{red}Slime段模型\)

问题：对于一个有 \(m\) 个 \(1\)，\(n-m\)个 \(0\) 的，求其中最长的 01 段不超过 \(k\) 的方案数。

我们可以再\(k+1\) 个 \(1\) 后面添一个 \(0\) 表示一段的结束。

令 \(S(n,t,k,m)=(-1)^t{n-tk\choose t}{n-t(k+1)\choose m-tk}\)

假设当前有 \(t\) 段不满足，带容斥系数方案数为 \(L(k,t)=S(n,t,k+1,m)-S(n-k-1,t-1,k+1,m-k-1)\)

因为还要考虑最后一个段后面不用加 \(0\) 需要将方案数加上，但这里是加上容斥系数\(-1\)，所以为减。

答案为 \(A(k)=\sum_{t=0}^{\min((n-k-1)/(k+1)+1,m/(k+1)}L(k,t)\)，