排他的論理和が総和以下っぽい。詳しく説明する。 とする。 まずが成り立つ。更にも成り立つ。 部分文字列の左端lを固定してみる。このときr=lならば明らかに条件を満たす。 A[l]⊕A[l+1]⊕...⊕A[r] < A[l]+A[l+1]+...+A[r] が成り立つと仮定する。このとき、…

まず最上位ビットについて考えてみよう。最上位ビットが異なる頂点同士を結ぶと、ほかの全てのビットが異なる頂点同士を結ぶよりも高コストなので、できるだけ少なく済ませたい。そこで0b0???のグループと0b1???のグループに分けてそれぞれ木になっていると…