题解：CF1792F1 Graph Coloring (easy version)

george0929 · 2025-11-13 21:27:24 · 题解

红蓝互为补图，因此红蓝都不连通的情况不存在。

第一反应是对红蓝都连通的情况容斥，但是发现这样根本做不了。

不妨转化为有一个颜色不连通，对恰有一种颜色不连通的情况计数，此时另一种颜色必定连通。

令 f_i 表示 i 个点，每个子集满足蓝色不连通的方案数，枚举与 1 相连极大的蓝色连通块 S，保证跨过 S 和 [1,i]/S 的集合中不存在红蓝都连通的集合，这个连通块需要满足红色不连通，用“极大”保证不重。

由于是"极大连通块"，所以两个集合之间的连边方案是固定的，只能是红色边。

恰好，这样的连边方式满足【跨过 S 和 [1,i]/S 的集合中不存在红蓝都连通的集合】，因此逻辑以一种很奇怪的方式自洽了。

由于对称性，红色不连通方案数 = 蓝色不连通方案数。

则 f_i=\sum\limits_{j=1}^{n-1}\binom{i-1}{j-1}\times f_{j}\times (2f_{n-j}-[n-j=1])。

乘二是因为当集合有边时可以任意交换红蓝。