画家小P

题意

n个点m条边，要给每个点染色一种颜色，(col_i)，则图的美丽值为(igopluslimits_{i=1}^n col_i)，其中给定了(limit_i)，需要满足(col_iin[0,limits_i])。若满足美丽值为(C)，对于任意边((u,v))，需要满足(col_u=col_v)。求有多少种不同的方案数。（(nle 15,mle {nchoose 2})，(C,limit_ile 10^{18})）

做法

考虑对边容斥，即强制边的端点相同
显然容斥系数为((-1)^{|所选边集|})
而边集的状态其实为：族(P={S_1,S_2,cdots ,s_k})，其表示图的联通状态
进一步的，令(coef(S)=sumlimits_{E'subseteq E}[E'在S的导出子图内，且E'使得S联通](-1)^{|E'|})，(P)的总容斥系数法就为(prodlimits_{i=1}^k coef(S_i))

而对于族(P)，方案数为如下（令(u_i)为(S_i)中(limit)最小的点）

(m)个(limit_{u_i})的限制，其中(k)个(S_i~is~odd)，使得(igopluslimits_{i=1}^k col_i=C(col_iin[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)以后再补