【模拟赛】20190615

# A. 联邦 设 $f_S$ 表示连通 $S$ 的方案数，设 $g_S$ 表示 $S$ 内部随便连的方案数 设 $x$ 为 $S$ 的 $\text{lowbit}$，显然有 $f_S=g_S-\sum_{x \in T \subset S} f_Tg_{S-T}$ 然而这个是 $O(3^n)$ 的，没啥前途 首先预处理就 $O(2^n \times n^2)$ 了，所以之后瞎搞搞应该就过了 考虑到最后这个图一定连通，那么每次就不需要选 $\text{lowbit}$ 了，只需要每次都随便选一个点就好了，在这里每次都选择 $x=1$ 特别的，如果 $x \notin S$，那么 $f_S=0$ 于是现在转移就差不多变成了 $f_S=g_S-\sum_{T \subset S}f_Tg_{S-T}$ 于是就可以子集卷积了，每一层 $\text{fmt}$ 回去的时候清空一下就行了 # B. 能量 emmmmm 在一个月前，我在这个出题人的博客上读过这个题的题解……然后当时并不会做，感觉不可能在考试中见到这种题，于是就鸽了 一个月后的今天，心情十分复杂.jpg 然而还是不会，这东西真的不是MO模拟赛吗…… # C. 交通 显然对于一个点，肯定是要把最大的连通块中切下来一部分扔到最小的连通块上 写个主席树就过了，当然还要维护每个点到根的信息，再额外开个树状数组就好 听说有别的很厉害的做法