本文主要是介绍（FJWC2020） DTOJ 4689 图（graph），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
有一张 n n n 个点， m m m 条边的无向图，你想选出一个非空点集，使得仅保留这个点集中的点和两个端点都在这个点集里的边后得到的图是连通的。你想知道有多少种可能的选点集的方案。
由于出题人不是毒瘤，所以本题不对 998244353 998244353 998244353 取模，改为对 2 2 2 取模。
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 50 ， 0 ≤ m ≤ n ( n − 1 ) / 2 ， 1 ≤ ∣ a i − b i ∣ ≤ 12 1\le n\le 50，0\le m\le n(n−1)/2，1\le |a_i−b_i|\le 12 1≤n≤50，0≤m≤n(n−1)/2，1≤∣ai−bi∣≤12。
题解
注意到对 2 2 2取模，而直接做不太可做的样子，所以肯定要利用 % 2 \%2 %2的性质。
再考虑题目另一个条件： 1 ≤ ∣ a i − b i ∣ ≤ 12 1\le |a_i−b_i|\le 12 1≤∣ai−bi∣≤12，如果状态能只记最后12个点就好了。但如果要判图是否连通，需要记录它们所属的连通块编号，用最小表示法仍然记不下（我也不会）。
但如果改为连边与染色的限制，就能记下。考虑做这样的转化：设 f [ s ] f[s] f[s]为点集 s s s导出子图连通块的个数，则在 % 4 \%4 %4意义下 2 f [ s ] 2^{f[s]} 2f[s]不为0，当且仅当 f [ s ] = 1 f[s]=1 f[s]=1。于是问题可转化为求所有导出子图的所有连通块黑白染色的方案数，直接状压DP即可。
这篇关于（FJWC2020） DTOJ 4689 图（graph）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
