n个点m条边，要给每个点染色一种颜色，\(col_i\)，则图的美丽值为\(\bigoplus\limits_{i=1}^n col_i\)，其中给定了\(limit_i\)，需要满足\(col_i\in[0,limits_i]\)。若满足美丽值为\(C\)，对于任意边\((u,v)\)，需要满足\(col_u=col_v\)。求有多少种不同的方案数。（\(n\le 15,m\le {n\choose 2}\)，\(C,limit_i\le 10^{18}\)）
考虑对边容斥，即强制边的端点相同
显然容斥系数为\((-1)^{|所选边集|}\)
而边集的状态其实为：族\(P=\{S_1,S_2,\cdots ,s_k\}\)，其表示图的联通状态
进一步的，令\(coef(S)=\sum\limits_{E‘\subseteq E}[E‘在S的导出子图内，且E‘使得S联通](-1)^{|E‘|}\)，\(P\)的总容斥系数法就为\(\prod\limits_{i=1}^k coef(S_i)\)
而对于族\(P\)，方案数为如下（令\(u_i\)为\(S_i\)中\(limit\)最小的点）
\(m\)个\(limit_{u_i}\)的限制，其中\(k\)个\(S_i~is~odd\)，使得\(\bigoplus\limits_{i=1}^k col_i=C(col_i\in[0,limits_i])\)
这个见过无数次了...\(O(nlogC)\)
\(P\)的数量是\(O(bell(n))\)级别的，但冷静一下会发现，其实只与\(limit_{u_i}\)有关，是\(O(2^n)\)级别的
令\(f_{S,T}\)为已经选过\(S\)了，其中奇数的集合代表元素（即最小元素）为\(T\)，预处理\(f_{[n],T}\)的数量，然后算方案数
\(O(4^n+2^nnlogC)\)
论文，\(4.3,5.2\)以后再补
原文：https://www.cnblogs.com/Grice/p/12939467.html