\(S\) に含まれる \(2\) べきでない最小の数 \(a\) を固定して，\(a\) ごとに何通りあるかを求めます．

\(S\) の要素の和として表す方法が何通りあるかを表す数列を考えます．最終的に，\(0,1,...,N\) での値は \(1\) または \(2\) である必要があります．ここで，\(S\) の要素を小さい順に追加していき，その各段階で同様の数列を考えることにします．要素を \(a\) まで追加したとき，数列は \(1\) が \(a\) 個，\(2\) が \((2^k-a)\) 個，その後に \(1\) が \(a\) 個並んだものとなります．（\(2^k\) は \(a\) 以上の最小の \(2\) べき．）

ここで，要素を \(1\) つ追加すると，数列は次のように変化します．

• 数列のコピーを \(1\) つ用意する．そして，数列の右端に並んでいる \(a\) 個の \(1\) と，コピーの左端に並んでいる \(a\) 個の \(1\) を「重ね合わせ」て，\(1\) つの数列を得る．

「重ね合わせる」とは，対応する部分を \(1\) が \(b\) 個，\(2\) が \((a-b)\) 個，その後に \(1\) が \(b\) 個並んだ状態にして，繋ぎ合わせることを指します．（\(b\) は任意の \(a\) 以下の非負整数．）

\(N\) より大きい値については \(3\) 通り以上の表し方があってもよいことに注意すれば，求める値は以下になります．

• 数列の長さが \((N+1)\) 以上になるまで先の過程を繰り返して，最終的に得られた数列それぞれについての，添え字 \(N\) の要素から降順にみて最初に現れる \(2\) までの距離の総和．

数列を構成する過程に対応して，完全二分木を考えることができます．各頂点には以下のようにして，数列の部分列を対応させることができます．

• 完全二分木の各葉には，最初の数列の「\(2\) が \((2^k-a)\) 個並んでいる部分」のコピーに対応する部分列が \(1\) つ対応している．
• 完全二分木の高さ \(k\) の各頂点には，\(k\) 回目の操作で「重ね合わせた」部分のコピーに対応する部分列が \(1\) つ対応している．

ここで，対応する部分列の添え字が \(0\) 以上 \(N\) 以下となるような頂点の個数を固定します．高さが \(1\) 以上の頂点に対応する部分列の長さは \(a\) 以上なので，この個数は高々\(2N/a + 1\) 個しかありません．

このとき，各高さの頂点に対応する部分列の長さは \(a\) 以上 \(2a\) 以下で自由に定めることができます．よって，長さの合計が \((N+1)\) 以下で，次の頂点に対応する部分列を含めると，長さの合計が \((N+1)\) を超えるような長さの定め方は，単純な動的計画法により求めることができます．

実際には，添え字 \(N\) の要素から降順にみて最初に現れる\(2\) までの距離の総和を求める必要がありますが，これも同様に動的計画法で求めることができます

高さは \(O(\log N)\) であるので，各固定した状態ごとの計算量は \(O(N\log N)\) です．状態数は \(O(\sum N/a)=O(N \log N)\) なので，全体として \(O(N^2 \log ^2 N)\) となります．

ただし，添え字 \(0,...,N\) の部分列に含まれる頂点の個数を \(1\) つずつ順に増やしていき，各過程での動的計画法の結果を再利用することで，\(O(N^2 \log N)\) の計算量で求めることも可能です． 実際には定数倍が軽く，先程の計算量でも十分高速に求まります，