容斥原理 + 子集卷积 + 拉格朗日插值 + 色多项式.
对三种子任务分别设计算法.
$m\le 24$
考虑容斥,暴力枚举哪些边连接的两个点颜色是相同的,用并查集维护相同颜色的点形成的连通块.
若钦定了 $p$ 条边连接的两个点颜色相同,形成了 $s$ 个连通块,贡献应为 $(-1)^p k^s$ .
由于每加一条边最多减少 $1$ 个连通块,所以 $s$ 与 $n$ 的差不会超过 $m$ ,维护出这个关于 $k$ 的多项式各项系数即可.
时间复杂度 $O(2^mm+qm)$ ,但可以剪枝,若搜到某条边时,两个端点同色,选它和不选它的贡献会恰好抵消掉.
$n\le 15$
从 $m\le 24$ 的做法可以注意到答案是关于 $k$ 的 $n$ 次多项式.
于是只需要代 $k=1,2,3\dots,n+1$ 求出答案,就可以插值得出这个多项式.
考虑对于一个 $k$ 如何求出答案.
染色可以看成依次为每种颜色确定点集,每种颜色的点集必须是独立集,不同颜色的点集不能相交.
记集合幂级数 $F(x)=\sum_{S\in I} x^S$ ,其中 $I$ 表示所有独立集的集合,则 $F$ 子集卷积意义下 $k$ 次幂全集的系数即为所求.
时间复杂度 $O(2^nn^3+qn)$ ,为了实现方便也可以写成 $O(2^nn^3+qn^2)$ 之类的,插值不是复杂度瓶颈.
每个点度数为 $2$
此时的图一定是由若干个互不相交的环构成的,考虑一个长度为 $l$ 的环,它的色多项式为 $(k-1)^l+(-1)^l(k-1)$ .
注意长度相同的环是没有本质差别的,可以合并起来一起算.
环长种类数是 $O(\sqrt n)$ 的,时间复杂度 $O(q\sqrt n\log n)$ .
1 | //%std |