一些条件,都要满足
为什么容斥问题会有一套专门的计算方法?
其实容斥问题是一种常见子集答案总和的信息,常见的求解方法为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\),则:
\[f_n=g_n-\sum_if_ig_{n-i}{n-1\choose i-1} \]意为枚举第\(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)\),
标签:方案,系数,sum,元素,容斥,times,原理,计算方法 From: https://www.cnblogs.com/lupengheyyds/p/18499069