ABC199 E Permutation
$ dp_S
:= とっている数の集合が
$ S
であるような場合の数 としてDPをしていく. 遷移はある数
$ x
を全探索し, それについて,
$ S
に含まれていなく, かつ集合に追加した際に条件を満たす場合に,
$ dp_{S | 2^x} = dp_{S | 2^x} + dp_S
とすればよい. 計算量は
$ O(2^NN)
となり, これは十分高速である.
実装例:
https://atcoder.jp/contests/abc199/submissions/22013916