Codeforces 578B. "Or" Game

問題

n個の整数a_iが与えられる。
高々k回、整数xを整数a_iから一つ選んでかける、という操作を行える。
各整数のORをとったものa_1 | a_2 | ・・・| a_nの最大値はいくつになるか？

1<=n<=2*10^5
1<=k<=10
2<=x<=8
0<=a_i<=10^9

考え方

直感的に、xが2以上なので、x^kをかけた方が最大bitを更新できるので、a_iの最大値にx^kをかけた方がよさそうに感じる。
しかし、k=1程度だと、a_iの最大値でないものにかけた方が良い結果が得られる場合が存在してしまう。
(a={12,9},k=1,x=2の場合、12に2をかけるよりも9に2をかける方がよい。)

xをかける操作を複数のa_iに分けた方が良いかというと、最大bitを更新できたほうがよいので、x^kを一つにかけた方が良い。
どれにかけた方がよいかは試すしかなく、計算量を減らして探す必要がある。

1番目からi-1番目までのORを取ったもの、と、i+1番目からn番目までのORを取った物がわかれば、この2つとa_i*x^kとのORを取れば、a_iをx^k倍したときの全体のORがO(1)で求められ、最初の2つの範囲のORはO(n)で計算できる。
これらの中で最大のものを返せば良い。