[hdu6718][百度之星2019]权值

这个题我考试时候想了半个小时,后来又想了一天多,终于想出来了,发现这是一道傻逼题。
首先我们得到的是一个基环树森林,由于我们可以把联通块之间的代价乘起来得到最终答案,所以我们可以转化为求解一个基环树的问题。
对于一个基环树,我们发现只要环上方案确定了,树上的方案就可以直接做了,所以我们转化为了环上的问题。
所以这道题大致可以转化为这样一个问题,求有多少个序列$a_1,a_2,…,a_n$,满足对于所有的$i$,$a_i\le c_i$,且所有的$a_i$异或起来是$0$。
这个问题有点烦,考虑一般异或的问题,我们都是考虑从高到低枚举位的,那么这道题也可以这样。考虑所有数都在$[0,2^k)$中的问题,我们发现只要有一个$a_i$可以取$[0,2^k)$中的任意一个数,那么方案数可以直接算了,因为不管其它数取什么,这个可以取任意数的$a_i$总能将其调整成0,且方案只有一种。
我们尝试着将这个问题转化为这样的模型,我们发现,考虑某一位所有元素的取值,发现只要有一个$a_i$脱离了上界($c_i$这一位上是1,$a_i$这一位上是0),那么这个问题在下一位上就会变成这样的形式。
那么我们可以分成两种情况。
第一种:存在至少一个$a_i$脱离了上界。
这种情况下我们暴力枚举第一个脱离上界的位置,然后计算方案数,方案数可以用前缀和和后缀和预处理之后$O(1)$算出(注意这一位上的1的个数要是偶数),这部分我们耗费$O(n)$的时间即可算出
第二种:不存在$a_i$脱离上界
首先我们要判断这种情况是否合法(1的个数是否为偶数),如果不合法,直接退出,如果合法,如果还有下一位,那么我们递归计算下一位,如果没有下一位,直接计算贡献。
所以总复杂度为$O(n\lg n)$,代码略有些难写。

Tagged with:

发表评论