Educational DP Contest O コード 問題 ビットDPを使う. 女性のある部分集合を \(B = \{ b_1, b_2, \dots, b_n \}\) として,男性の先頭 \(n\) 人と \(B\) とのマッチングの数を \(C(B)\) とする. これを計算するには, 男性 \(n\) 番目に対する女性を仮定して足し合わせればいい. 数式で書くと, \[C(B) = \sum_{i=1}^n C(B \setminus b_k)a_{n, b_k}\] となる. 集合はビットで表す. 計算量は \(O(2^N N)\) である.