专栏文章

题解：AT_xmascon24_a Artistic Modulus

ccomplexor管理员
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8xhts
此快照首次捕获于
2025/12/03 08:05
3 个月前
此快照最后确认于
2025/12/03 08:05
3 个月前
查看原文

题意简述

有一个 nn 个点 mm 条边的无向图，保证没有重边自环，你需要给每条边和每个点标上 0/10/1。
要求对于任意一个标了 00 的点，都有一条标了 00 的边和它相连。对于任意一个标了 11 的边，两个端点中至少有一个端点标了 11。 问所有 2n+m2^{n+m} 种方案中合法的方案数，对 22 取模。
数据范围无需在意。

解法

打表/手模几个图，猜想答案很有可能是 11。
事实上，答案一定是 11，本文目的就是证明这一点。
连通块之间是独立的，只需要证明连通图且 m≥1m\geq 1 的情况。
考虑容斥计算答案。方便起见，在每个边上插一个点（标号为 n+1∼n+mn+1\sim n+m），然后把边的颜色放在这个点上。那么限制变成了对于原来的 nn 个点，每个标 00 的周围必须有 11；对于新加的 mm 个点，每个标 11 的周围必须有 00。
设图的集合 G1,G2,…,Gn+mG_1,G_2,\dots,G_{n+m}，其中表示 GiG_i 表示第 ii 个点不满足限制的图，具体地：若 1≤i≤n1\leq i\leq n，那么 GiG_i 是所有点 ii 标 00，且其所有相邻点标 11 的图构成的集合；若 n+1≤i≤n+mn+1\leq i\leq n+m，那么 GiG_i 是所有点 ii 标 11 且其所有相邻点标 00 的图构成的集合。那么有答案即为：
2n+m+∑T⊂{1,2,…,n}∧T≠∅(−1)∣T∣∣⋂i∈TGi∣2^{n+m}+\sum_{T\subset\{1,2,\dots,n\}\wedge T\neq\varnothing}(-1)^{|T|}|\bigcap_{i\in T}G_i|
现在  mod 2\bmod 2，那么 2n+m2^{n+m} 和 (−1)∣T∣(-1)^{|T|} 都不需要考虑了，也就是只要求：
∑T⊂{1,2,…,n}∧T≠∅∣⋂i∈TGi∣mod  2\sum_{T\subset\{1,2,\dots,n\}\wedge T\neq\varnothing}|\bigcap_{i\in T}G_i|\mod 2
经过上面的转化，我们图变成了二分图，其中 1∼n1\sim n 为左部点，n+1∼n+mn+1\sim n+m 为右部点。
对于一个钦定的集合 TT，我们称一个点被覆盖当且仅当这个点在 TT 中或者这个点至少有一个相邻点在 TT 中。那么如果一个左部点被覆盖，它只能标 00；一个右部点被覆盖，它只能标 11。
所以如果 TT 覆盖了所有的 n+mn+m 个点，∣⋂i∈TGi∣=1|\bigcap_{i\in T}G_i|=1，否则一定存在一个可以任意染色的点，这导致 ∣⋂i∈TGi∣|\bigcap_{i\in T}G_i| 为偶数。
现在问题进一步转化到有多少个 TT 能覆盖所有点。设 TT 中左部点集合为 TLT_L，右部点集合为 TRT_R，有四类情况（下面所说的“原图中的边”也可以指这条边上新加的点）：
  1. 若 TL=∅T_L=\varnothing，则 TRT_R 为右部点全集，共一种。
  2. 若 TLT_L 中两个点在原图上相邻，那么它们之间的边在不在 TRT_R 中对 TT 是否覆盖全部点没有影响，故总数为偶数。
  3. 若在原图上删去所有 TLT_L 中的点和相连的边后，还存在一个不小于 22 的连通块，那么这个连通块中的边必然在 TRT_R 中，此时这个连通块中的所有点都被覆盖，所以那些一端在这个连通块，另一端不在的边在不在 TRT_R 中不影响覆盖性，故总数为偶数。
  4. 若在原图上删去所有 TLT_L 中的点和相连的边后，所有连通块大小均为 11，那么每个连通块的点周围的边至少需要选一条，总方案数为 2cnt−12^{cnt}-1，为奇数，对每个连通块乘起来，总数也是奇数。此时，注意到排除上面三种情况后，这样的 TLT_L 实际上对应了一个原图上的二分图染色。而一个连通图的二分图染色方案数只有可能为 00 或 22，故可能的 TLT_L 有偶数种，对应的总数也是偶数。
这样就说明了能覆盖所有点的 TT 有奇数个，故证明了本题答案一定为 11。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...