【清华集训2014】主旋律
星梦Q
·
·
个人记录
题目链接
题解
首先,什么样的图不是强联通图.
缩点后存在入度为0的点,且这个点不包括全集.
考虑状压dp+容斥
$g[S]$表示$S$形成奇数个强连通分量的方案数−$S$形成偶数个强连通分量的方案数
那么,枚举编号最小的点所在联通块
$g[i]=-\sum_{i\subsetneqq S}f[j]g[S-j]
则
f[S]=2^{sum[i]}-\sum_{i\subsetneqq S}f[i]*g[S-i]*2^{sum[i]-w[i]}
w[i]$表示$S$有多少边终点属于$i