解説


この問題では与えられた操作により、 の行基本変形を行うことが出来ます。

まず、[操作] を組み合わせることにより、以下のような [操作 X] を実現することができます。

[操作 X]
整数 を選び、 に代入する。

例えば、他の要素を変えずに、 に置き換える方法を説明します。
と順番に操作を行うと、各 について、 の累積 に置き換わります。
次に、 と順番に操作を行うと、 の要素が元に戻り、
のみが の累積 に置き換わった状態になります。
そして、 と順番に操作を行うと、各 について、 の累積 に置き換わります。
このとき、 の累積 であり、 の累積 であるため、
の操作を行うと、 になります。
最後に、 と順番に操作を行うと、 の要素が元に戻ります。
(ここでは から始めていますが、他の整数でも同様に行うことができます。)
よって、[操作] を組み合わせることで、[操作 X] を実現することが示せました。

また、[操作 X] について、整数 を適切に選ぶことによって、
以下の操作のように言い換えることができます。

[操作 Y]
異なる つの整数 を選び、 に代入する。

数列 の各要素の 進表記を つの行とし、 の行列と考えると、
上記の操作を組み合わせることで、 における行基本変形を行うことができます。

行基本変形が行えることから、掃き出し法で行列の基底を求めることができます。
掃き出し法によって求めた基底は、各基底の最上位ビットを他の基底が持たない( でない)という性質があります。
求めた の基底を小さい順に とします。
また、操作後の数列を とします。

の各要素は基底のうちいくつかを で組み合わせたものになります。
要素として考えうる最大のものは、全ての基底を でつないだものです。(これを とします。)
なぜなら、上で述べた性質より、 は全ての基底の最上位ビットを持っており、
これから つ以上の基底を取り除くと値が真に小さくなるからです。
よって、 となります。

の各要素の和を大きくするには、 をできるだけ多くの で埋めたいです。
ただし、 は同じ基底を取ることができる必要があり、全ての要素を にすることはできません。
そのため、各基底の つずつとる必要があります。
また、 が含まれているため、 基底の中で のみ をとる必要がありません。
具体的には、以下のような は、 と同じ基底をとることができます。

このとき、各要素の和が最大となります。
この数列に対していかなる操作を行っても各要素の和が真に小さくなることを示せばよいです。
この数列に対する操作とは、( と同じ基底を取ることができるという条件の下で、)要素を選び、任意の基底の をとることです。
まず前提として、要素 をとることはできません。
が同じ基底を取ることができるという条件に反してしまいます。
要素 をとることを考えます。
の最上位ビットを持っているため、 をとることで要素の値は真に減少します。
これは、要素 に複数の基底の をとった場合でも同様です。

よって上の のときが各要素の和が最大になります。
全体の計算量について、掃き出し法を行うことで となります。( を各要素のビット数とします。)