ARC116 D - I Wanna Win The Game (500)
$ mが奇数の場合は構築不可能
最下位bitを考えるとXORしても最下位bitが必ず立ってしまい不可能
この考え方を下のbitから再帰的に使うことで求められる
$ mを2で割っていく
各bitについてそのbitを$ n個の内いくつ立てるかを全探索する
$ 0 \le i \le \min(n,m)について
$ m = \frac{m - i}{2}として再帰的計算する
立てるbitの位置は$ _{n}C_{i}通りあるので再帰的に求めた結果にかける
奇数の$ iは飛ばす
メモ化再帰にすることで$ O(M)回しか呼ばれなくなる
一回の呼び出し毎に$ O(\min(N,M))なので全体で$ O(M \min(N,M))