about 2 years ago

前言

集合反演来一发。。。UOJ上的题解有些变量混淆,我来重新写一发。。

题目大意

给定一个个点的图,对于每个生成的基环外向树定义权值,其中为度大于的点(叶子结点)数量,求所有的基环外向树的权值和。

分析

首先我们考虑用叶子结点来容斥,设表示基环外向树的集合为的答案:

解释一下变量的含义:表示枚举的叶子集合,表示贡献,表示每个中的点在中相邻的点的个数的乘积,也就是把的结点当作叶子结点加入中构成基环外向树的方案数,表示构成基环外向树的方案数。整个容斥的含义就是叶子结点集合的集合的方案数求和。
假如我们已经求出了,考虑传统的枚举来计算,我们需要的时间(计算),然而我们可以做到在的时间内计算出答案,具体方法就是从开始,不断的加点进去,同时计算
现在来看看怎样计算,我们同样有一个容斥的式子:

其中表示构成一个环的方案数,这个式子的含义就是求出叶子结点数为的方案数,然后容斥求出叶子结点数的方案数(是为了避免容斥时自我调用)。
可以发现还是比较好求的,设一个表示当前集合为,链上的当前点为,链的开头结点为集合中编号最小的点,最小表示是为了去重。把求出来后,就很好求了,加起来后要除以二,因为一个环会被两个方向都算一次。
所以我们就解决了这个问题了,时间复杂度
UOJ193.cpp

← 几道线段树题 CC MATCH →
 
comments powered by Disqus