Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) F. Sports Betting

最初 $ans=n$ と置き、winner にならないケースを引いていく

人 $i$ が winner にならない各ケースで、以下を満たす極小な人集合 $S$ がちょうどただ一つ存在する

従って各 $S$ に対して $S$ が起こる確率を $P(S)$ と置くと、 $( n-popcount(S) ) P(S)$ を $ans$ から引けば良い

$win_{i,j}=\frac{a_i}{a_i+a_j}$ と置くと、 $P(S)$ は以下の式で求められる
各 $T \subset S$ に対して、極小な人集合が $T$ になるケースを除いている

$P(S) = \prod_{i \in S} \prod_{j \not\in S} win_{i,j} - \sum_{T\subset S} P(T) \prod_{i \in S-T} \prod_{j\not\in S}win_{i,j}$

[tex:O(3ⁿ n²)] とかで厳しいけど適度に高速化を入れると通る
もう少しいい計算量で $P(S)$ 求められそうな気はするんだよな

blogskol