题解：AT_xmascon24_a Artistic Modulus

complexor · 2025-05-20 14:08:17 · 个人记录

题意简述

有一个 n 个点 m 条边的无向图，保证没有重边自环，你需要给每条边和每个点标上 0/1。

要求对于任意一个标了 0 的点，都有一条标了 0 的边和它相连。对于任意一个标了 1 的边，两个端点中至少有一个端点标了 1。问所有 2^{n+m} 种方案中合法的方案数，对 2 取模。

数据范围无需在意。

解法

打表/手模几个图，猜想答案很有可能是 1。

事实上，答案一定是 1，本文目的就是证明这一点。

连通块之间是独立的，只需要证明连通图且 m\geq 1 的情况。

考虑容斥计算答案。方便起见，在每个边上插一个点（标号为 n+1\sim n+m），然后把边的颜色放在这个点上。那么限制变成了对于原来的 n 个点，每个标 0 的周围必须有 1；对于新加的 m 个点，每个标 1 的周围必须有 0。

设图的集合 G_1,G_2,\dots,G_{n+m}，其中表示 G_i 表示第 i 个点不满足限制的图，具体地：若 1\leq i\leq n，那么 G_i 是所有点 i 标 0，且其所有相邻点标 1 的图构成的集合；若 n+1\leq i\leq n+m，那么 G_i 是所有点 i 标 1 且其所有相邻点标 0 的图构成的集合。那么有答案即为：

2^{n+m}+\sum_{T\subset\{1,2,\dots,n\}\wedge T\neq\varnothing}(-1)^{|T|}|\bigcap_{i\in T}G_i|

现在 \bmod 2，那么 2^{n+m} 和 (-1)^{|T|} 都不需要考虑了，也就是只要求：

\sum_{T\subset\{1,2,\dots,n\}\wedge T\neq\varnothing}|\bigcap_{i\in T}G_i|\mod 2

经过上面的转化，我们图变成了二分图，其中 1\sim n 为左部点，n+1\sim n+m 为右部点。

对于一个钦定的集合 T，我们称一个点被覆盖当且仅当这个点在 T 中或者这个点至少有一个相邻点在 T 中。那么如果一个左部点被覆盖，它只能标 0；一个右部点被覆盖，它只能标 1。

所以如果 T 覆盖了所有的 n+m 个点，|\bigcap_{i\in T}G_i|=1，否则一定存在一个可以任意染色的点，这导致 |\bigcap_{i\in T}G_i| 为偶数。

现在问题进一步转化到有多少个 T 能覆盖所有点。设 T 中左部点集合为 T_L，右部点集合为 T_R，有四类情况（下面所说的“原图中的边”也可以指这条边上新加的点）：

若 T_L=\varnothing，则 T_R 为右部点全集，共一种。
若 T_L 中两个点在原图上相邻，那么它们之间的边在不在 T_R 中对 T 是否覆盖全部点没有影响，故总数为偶数。
若在原图上删去所有 T_L 中的点和相连的边后，还存在一个不小于 2 的连通块，那么这个连通块中的边必然在 T_R 中，此时这个连通块中的所有点都被覆盖，所以那些一端在这个连通块，另一端不在的边在不在 T_R 中不影响覆盖性，故总数为偶数。
若在原图上删去所有 T_L 中的点和相连的边后，所有连通块大小均为 1，那么每个连通块的点周围的边至少需要选一条，总方案数为 2^{cnt}-1，为奇数，对每个连通块乘起来，总数也是奇数。此时，注意到排除上面三种情况后，这样的 T_L 实际上对应了一个原图上的二分图染色。而一个连通图的二分图染色方案数只有可能为 0 或 2，故可能的 T_L 有偶数种，对应的总数也是偶数。

这样就说明了能覆盖所有点的 T 有奇数个，故证明了本题答案一定为 1。