课件里的题目.
考虑如果没有图的限制那么 \(c\) 显然可以被规约成 \(c = 0\) 的情况,只需要考虑所有数的异或为 \(0\) 即可,这一步可以用简单的 DP 自由元位置简单计算方案,之前的题目里也具体谈到了这一点.
那么最保留的方式便是容斥,枚举哪些边不满足条件,条件便变成了若干个连通块里的数都要相等,此时显然只可能选最小的界,对连通块大小为奇数和偶数的情况分开讨论一下,显然是我们无法接受的时间复杂度.
考虑选择一个边集的本质便是划分成若干连通块,因为可能存在不同取边集方式使得连通块划分情况一样(比如说一个连通块导出子图可以选任意一个生成树),那么现在问题便变为求每个连通块容斥系数和,最后再乘起来.求容斥系数和则是主旋律一题中经典的容斥 DP,同样也用一个容斥处理可以做到 \(O(3^n)\).
上述做法瓶颈在于枚举划分数,这个数的级别是 \(\text{Bells}(n)\) 级别的,很过不去.
你又发现,即使连通块划分不一样,可能其中最小的界是一样的,可以按照 \(a\) 从小到大排序,然后每次枚举每个数扔到前面出现过的集合中还是新开一个集合,相当于你搜索的过程换成一个 DP,只用用状压记录最小界的下标即可,容斥系数仍然求和,最后扔到最开始的结构里跑一遍即可.