Comet OJ - Contest #11 F arewell

题意

给一个\(n\)个点\(m\)条边的无向图，每条边\((u,v)\)有从\(u\)指向\(v\)，从\(v\)指向\(u\)和消失三种情况，概率均为\(\frac{1}{3}\)。问该图为DAG的概率是多少。
\(n\le20\)

做法

定义集合幂级数，乘法为子集卷积
令\(F_S\)为\(S\)为DAG的方案数，\(E_{S,T}\)为\(S\)与\(T\)间的边，\(E_S\)为\(S\)内的边

其中\(2^{E_{T,S\backslash T}}=2^{E_S - E_T - E_{S\backslash T}}\)

Comet OJ - Contest #11 F arewell

原文：https://www.cnblogs.com/Grice/p/12939694.html