妙妙题 noi.ac 2323 Connecting

题意

数一个 (n) 个点图的子连通块数,对 (2) 取模。即,#(选一个点集的子集,使得它连通)。空集不算。

(nle 50)。对于边 (u,v)(|v-u|le 13)

从数据入手

首先这个对 (2) 取模一看就性质很好,它有啥性质呢?

这个 (|v-u|le 13) 似乎也有着一些性质:一个点的度数不会超过 (27);进一步,如果我们按顺序考虑点,它连向前面的点的边数 (le 13)

设一个点集 (V) 的子集 (S) 的导出子图的连通块数为 (c(S))。我们要求:

[(sumlimits_{Ssube V,s eqempty} [c(S)=1] ) mod 2 ]

而我们的 (c(S)) 应该都 (ge 1),所以不用考虑 (0),把 (>1) 的去掉即可。

但是要求 去掉。如果给 (c(S))(2)(=3,=5...) 那些还是会留下来。

要求 去掉,容易想到在 (poly) 题里面,会有模 (x^n) 以去掉 (n) 次项以上的方法。这题也同理,我们考虑

(2^{c(S)}mod 4)(c(S)=1) 的时候会取到 (2)(>1) 的时候就变成了 (0)。那好办,最后给它除掉一个 (2) 即可。

这是这道题的精髓

其实你也可以用 (3^{c(S)}mod 9),但是那个就要复杂,不好 dp

然后这个东西的组合意义很好:假设已知了 (S),给每个连通块黑白染色(同一个块同色),方案数就是 (2^{c(S)})

但现在不知道 (S),我们相当于要先选一个 (S),再染色。但其实我们的条件还是不变:同一个块同色。转化一下(逆否条件),如果两个点异色,就不能再同一个块;再等价,就是 黑白两个点不能有边相连

如果要处理这个 “先选一个 (S)”,可以搞一个 "灰色”:表示不选某个点。灰色和黑白点间没有任何的限制,它单纯是为了区分选了和没选的点。

然后注意到一个点前面只有 (13) 个点,状压记录它们染了啥颜色,dp算一下即可。复杂度 (O(n imes 3^{13}))

原文地址:https://www.cnblogs.com/LightningUZ/p/15033099.html