べき乗和は$K$の値に関わらず奇数と偶数を交互に足すので、総和は奇、奇、偶、偶、奇、奇、……となる。総和が奇/偶の時の自明な下限がそれぞれ1/0なので、これを達成できれば最善となる。実験してみると、$N$が十分に大きければ常に下限が達成できるという予想が立つ。
$K=1$の場合、長さ4の区間は$0110$とわければよくて、$N$が$4$の倍数ならこれに従って等分できる。倍数でない場合もそれぞれ4つずつ等分した後、残りを適当にわければよい。
$K=2$について。また実験すると、長さ8の区間は$01101001$で等分できることがわかるので、$N$が小さい場合の構成を列挙した上で、以降は$8$個ずつ等分すればよい。
$K=3, 4$の場合も常に等分できるような長さの区間が見つかれば解決しそうだ。
$K=3$の場合は長さ16の区間は$0110100110010110$で等分できる。（ここでようやく、ひとつ小さい次数で得た列をflipしてくっつければよいことに気づく。）やはり$N$が小さい場合を列挙して、以降は$16$個ずつ等分すればよい。$K=4$も同様で、長さ32の区間を$01101001100101101001011001101001$で等分できる。
さて、$N$が小さい場合の解を用意する必要があるのだが、明らかにIPソルバで解けるのでOR-ToolsのCP-SATを使った。$K=3$までは愚直でいいとして、$K=4$はDPや半分全列挙でも簡単ではないように見える。（ちゃんと考えていない）
