https://atcoder.jp/contests/dp/submissions/10980341
- ビット全探索をする
- 男[i]に対してnCi全通りの更に男女[i][j]=1になってるj通りのループ
制約が21しかないのでビット全探索が出来そうと推測できる。男性[i]までにマッチングが成立した女性の組み合わせビットをdp[i][bit1]で表す。例えば、bit1=010010なら女性[1]と女性[4]がマッチング成立済みとする。
if (A[i][j] == '1' && bit1のj桁目が1でない) dp[i][bit1のj桁目を1にした値] += dp[i-1][bit1]
各男性[i]に対して各女性[j]とマッチングするかどうか、それぞれに更に
]のビットの組み合わせ全て試していけば解ける。ただし、このままだと
で計算量的に少々厳しい。
そこで、毎回]のビットの組み合わせを試す必要がないように枝刈りする。例えば、男性[3]と女性のマッチングを考えるときにbit1=101111のような組み合わせは無駄になる。男性[3]までにマッチングした女性の組み合わせビットは1が2個しか立ってないような値になるはず。1がP個立っているビットを高速に列挙するアルゴリズムが蟻本p144に載っている。このアルゴリズムを利用すると
となりTLEにならずに通る（いまいち計算量が把握できない…）
https://www.wolframalpha.com/input/?i=21+*+21+*+sum+%2821%21%2F%28i%21+*+%2821-i%29%21%29%29%2C+i%3D1+to+21&lang=ja
