主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解 P5933 【[清华集训2012]串珠子】
最后更新于 2025-07-31 08:27:08
作者
MikukuOvO
分类
题解
题解
P5933
复制 Markdown
查看原文
删除文章
更新内容
考虑$f[i]$表示状态为$i$的连边方案数，$g[i]$表示状态为$i$的能使得联通的连边方案数，$t[i]$表示状态为$i$使得不连通的方案数。 首先$f[i]$是比较好求的，就是$f[i]=\prod_{(u<v)\in k}(c[u][v]+1)$。 关于求$t[i]$，我们首先固定$i$中的一个点$p$，那么剩余的点要么与$p$联通，要么与$p$不连通。 假设和$p$联通的点集为$S$，不连通的点集为$T$，那么对于$t[i]$的贡献就是$g[S]\times f[T]$。 这样我们枚举子集转移即可，$g[i]=f[i]-t[i]$。 这里我解答一个问题，为什么$p$可以任意？ 考虑实际上我们固定$p$点的意义，就是使得其余的所有点的状态只有两种，这样我们枚举子集转移就会做到不重不漏。 [$code$](https://captaindag.github.io/2020/04/05/%E6%B8%85%E5%8D%8E%E9%9B%86%E8%AE%AD2012-%E4%B8%B2%E7%8F%A0%E5%AD%90/)
正在渲染内容...
点赞
10
收藏
0
