【UOJ】#37.【清华集训2014】主旋律

题解

一道&＃xff0c;神奇的题&＃61; &＃61;

我们考虑正难则反&＃xff0c;我们求去掉这些边后有多少图不是强连通的

怎么求呢&＃xff0c;不是强连通的图缩点后一定是一个DAG&＃xff0c;并且这个DAG里面有两个点

我们想一下&＃xff0c;如果我们把1当成入度为0的点&＃xff0c;随便造出个图&＃xff0c;可以是这个图吧
如果把2当成入度为0的点&＃xff0c;随便造出个图&＃xff0c;也可以是这个图吧
把1和2当成入度为0的点&＃xff0c;随便造出个图&＃xff0c;还可以是这个图吧……

那么这像什么&＃xff0c;容斥啊

以下的点说的都是缩点后的点

奇数个入度为0的点就是&＃43;&＃xff0c;偶数个入度为0的点就是-

那么我们就有了一个精妙的容斥&＃xff01;
设\(f[S]\)为点集S是强连通分量的方案数
设\(g[S]\) ……是……
定义可能很奇怪&＃xff0c;是容斥出来的&＃xff0c;点集S的系数

嗯&＃xff0c;这么考虑&＃xff0c;我们知道了S这个点全是入度为0的点&＃xff0c;那么剩下的造图的过程&＃xff0c;就是S这个点集向外延伸的边&＃xff0c;和除S中的点之外的点之间的边&＃xff0c;有或没有&＃xff0c;乘上一个2的指数幂就好

那么&＃xff0c;怎么知道S这个系数呢&＃xff1f;&＃xff1f;&＃xff1f;

我们考虑S中包含一个编号最小的点u的强连通分量&＃xff0c;且入度为0

假如这个点的集合是T&＃xff0c;T包含u

那么\(g[S] &＃61; g[S] - g[S ^ T] * f[T]\)&＃xff0c;咦&＃xff0c;为什么是减法
因为\(g[S ^ T]\)容斥的系数&＃xff0c;在多了一个联通块后&＃xff0c;所有的奇偶性都改变了&＃xff0c;那么&＃43;-号也取反了&＃xff0c;所以是减法

最后&＃xff0c;我们用每个S的子集&＃xff08;包括S&＃xff09;算一遍不合法的图&＃xff0c;用总共的图减掉就行&＃xff0c;就是\(f[S]\)的值
还有\(g[S] &＃43;&＃61; f[S]\)这样的话&＃xff0c;代表整个S是一个强连通分量&＃xff0c;S缩点后构成的入度为0的点是1个

\(h[S]\)表示S这个点集中的边
\(w[T]\)表示在全集是S的情况下&＃xff0c;选择T这个点集作为缩点后入度为0的点&＃xff0c;能向外延伸的边集

代码

#include
#include
#include
#include
#include
#include
#include