No.174

カードは昇順にソートしておく.

どのカード手持ちにしているかをビット表現で表し, そのビット表現に到達する確率を DP で計算しながら, カード $i$ が $j$ 番目に出される確率 $P(i, j)$ を計算する.

このとき期待値は,

$$\sum_i\sum_j\sum_k P_a(j, i)P_b(k, i)A_jB_k$$

で求められる. (ただし, $A_j > B_k$ の場合だけ足す)