ABC291 G - OR Sum (600)
実装を簡単にするために$ Aは2回繰り返していることにする
愚直に実装すると$ N回ずらして毎回$ N個のORを求めるので$ \mathcal{O}(N^2)
普通の積ならば$ Bを反転することでFFTで$ \mathcal{O}(N \log N)で計算できる
各bitで考えると片方でも1ならば結果が1になることが分かる
なので各bitを反転させると普通の積と同じ結果になる
よってまず各bitを反転させFFTをする
各$ j ビット目で $ (N - FFTの結果) << jを求めて足す
この値の最大値を求める
$ A,B両方とも31以下なので5ビットで表せる