串珠子(简单容斥+避免重复计算)

题意简述:(n) 个点,两个点之间有 (c_{i,j}) 条边。问把整幅图连通的连边方案数?

SOL:

这种题一般先考虑把总方案数求出减去不合法方案数。

设集合 (S) 的总方案数为 (z_{{S}}) ,那么 (z_{{S}}=sum_{i,jin S} (c_{i,j}+1))

再考虑不合法的方案数 (ilg_{{S}}) ,考虑固定一个点 (p) ,然后枚举包含 (p)({S}) 的真子集,那么 (ilg_{{S}}=lg_{{T}} imes z_{{S-T}})

(lg_{{S}}=z_{{S}}-ilg_{{S}})

集合从 (0) 枚举到 ((1<<16)-1) 即可。

初始化:(lg_{1<<i}=1)

原文地址:https://www.cnblogs.com/currytrey/p/15389596.html