ARC141 B - Increasing Prefix XOR (500)
単純な比較でもXORを取った結果でも単調増加するということはMSBが単調増加しているということ
MSBが小さかったら$ Aの条件を満たさない
MSBが同じだったら$ Bの条件を満たさない
なので$ N \gt 60だと明らかに不可能
$ dp[i][j] で$ i番目までの要素でMSBが$ jビット目の数の場合の数とする
MSBが$ j ビット目のある値$ x に決めたとき$ dp[i][j] = \sum_{k=0}^{j-1} dp[i-1][k]
$ x の取り得る範囲は$ 2^j \le x \le \min(m,2^{j+1}-1) なのでこれを$ dp[i][j] に掛けると全$ xについて計算したことにできる
$ N \gt \log Mの場合を考えなくて良いので$ \mathcal{O}(\log^3 M)