这是本文档旧的修订版！
Deltix Round, Summer 2021 (Div. 1 + Div. 2)
F. Sports Betting
题意
给定 $n$ 个队伍的能力值，队伍间两两进行一场比赛，队伍 $i$ 战胜队伍 $j$ 的概率为 $\frac {a_i}{a_i+a_j}$。
定义间接战胜：如果队伍 $i$ 战胜队伍 $b_1$，$b_1$ 战胜 $b_2\cdots b_k$ 战胜 $j$，则称 $i$ 间接战胜 $j$。
称一个队伍为冠军队伍当且仅当该队直接战胜或间接战胜所有其他队伍。问冠军队伍的期望个数。
题解
如果队伍 $i$ 战胜队伍 $j$，则从点 $i$ 向点 $j$ 连一条边。
设 $U=\{1,2\cdots n\}$，不难发现，假设冠军队伍集合为 $S$ 当且仅当 $S$ 为强连通分量且 $S$ 与 $U-S$ 的所有边方向为 $S\to U-S$。
设 $G(S,T)$ 表示 $S$ 与 $T$ 的所有边方向为 $S\to T$ 的概率，$f(S)$ 为 $S$ 构成强连通分量的概率，根据容斥定理，有
$$ f(S)=1-\prod_{T\subset S,T\neq \emptyset}G(T,S-T)f(T) $$
最终答案为
$$ \sum_{S\subseteq U}G(S,U-S)f(S)|S| $$
考虑如何计算 $G(S,T)$，有
$$ G(S,T)=\prod_{i\in S}\prod_{j\in T}\frac{a_i}{a_i+a_j} $$
显然可以暴力 $O(n^2)$ 计算单个 $G(S,T)$。预处理 $F(i,T)=\prod_{j\in T}\frac{a_i}{a_i+a_j}$，则 $G(S,T)=\prod_{i\in S}F(i,T)$ 可以 $O(n)$ 计算。
进一步，考虑将前 $\frac n2$ 个点染黑，其余点染白，记黑点集为 $U_1$，白点集为 $U_2$，于是有
$$ G(S,T)=G(S\cap U_1,T\cap U_1)G(S\cap U_1,T\cap U_2)G(S\cap U_2,T\cap U_1)G(S\cap U_2,T\cap U_2) $$
考虑 $O(n2^n)$ 预处理出下述四种情况
$$ G_{0/1,0/1}(S,T)=G(S,T)(S\subseteq U_1/S\subseteq U_2,T\subseteq U_1/T\subseteq U_2) $$
于是可以 $O(1)$ 计算 $G(S,T)$，总时间复杂度为 $O\left(3^n\right)$。
