source:zr 二十联测 day 15 C
题意
给定 \(n\) 个点 \(m\) 条边的图,求该图导出连通子图数量对 2 取模的结果。保证一条边两个端点编号差 \(\le 13\)。
\(n\le 50\)。
分析
原题相当于求连通块数量为 1 的导出子图的数量。
考虑利用模数为 2 的性质。
性质:答案等于 \(\dfrac{\sum 2^{f(S)}\bmod 4}{2}\),其中 \(f(S)\) 表示导出子图 \(S\) 的连通块数量。
\(2^{f(S)}\bmod 4\) 的值仅在 \(f(S)=1\) 的情况下为 \(2\),其他情况下都为 \(0\)。故 \(\sum 2^{f(S)}\bmod 4=2\sum[f(S)=1]\),而 \(\sum[f(S)=1]\) 就是答案。
题目转化为求 \(\sum 2^{f(S)}\bmod 4\) 的值。
为 \(2^{f(S)}\) 寻找一个组合意义,相当于,对该导出子图染上黑白两种颜色的方案数。转化一下,就是给每个点染黑白两色,使得有边相连的两个点颜色相同。
同理,为 \(\sum 2^{f(S)}\) 寻找一个组合意义,相当于,对整个图染上黑白两种颜色或者不染色(不染色表示不在子图中),使得有边相连的两个点颜色相同。
据此可以直接设计 \(f_{i,S}\) 表示已经填了 \(1\sim i\) 的点,后 \(13\) 个点的染色情况是 \(S\)。转移考虑 \(i\) 填什么颜色即可,合法性判断可以 \(O(1)\) 做到。于是时间复杂度 \(O(n3^{13})\)。
标签:13,颜色,导出,bmod,子图,sum,城市,ZR From: https://www.cnblogs.com/dcytrl/p/18535556