\(S\) に対応するヤング図形に注目します． 0,1 をそれぞれ左/下方向への移動に対応させることで得られるパスをヤング図形の境界とします． こうして得られるヤング図形を \(Y(S)\) と書くことにします．

例えば \(S=\)1101010 に対応するのは以下のヤング図形です．

OOO
OOO
OO
O

\(i\) 行目の \(j\) 列目のマスをマス \((i,j)\) と呼ぶことにします．

\(S\) に対する問題の答えを \(f(S)\) と置くことにします． もし，各マス \((i,j)\) に対して，\(i,j\) にのみ依存する重み \(w(i,j)\) が存在し，\(f(S)=\sum_{(i,j) \in Y(S)} w(i,j)\) が成立すればとても嬉しいです．そこで，このような \(w(i,j)\) が存在すると仮定し，それがどんな値になるか考えてみます．

\(S\) に対して \(1\) 回操作を行った結果，\(Y(S)\) がどう変化するか考えてみます．

\(1\) 回操作した結果削られる可能性があるマスを考え，この集合を \(\partial Y(S)\) と呼ぶことにします． 例として，上で挙げた \(S\) に対応する \(\partial Y(S)\) を下図に X で示します．．

OOX
OXX
XX
X

\((i,j) \in \partial Y(S)\) について，これを削るような操作は \(i \times j\) 通りだけあります． \(Y(S)\) の面積を \(A\) と置くと，\(w(i,j)\) が満たすべき等式は以下のようになります．

\(\displaystyle \sum_{(i,j) \in \partial Y(S)} \frac{i \times j}{ A}w(i,j) = 1\)

\(g(i,j) = i \times j \times w(i,j)\) と置いて式変形すると，成立させたい等式は以下です．

\(\displaystyle \sum_{(i,j) \in \partial Y(S)} g(i,j) = A\)

ここで \(\partial Y(S)\) について考えてみます． \(Y(S)\) のそれぞれのマスを \(i-j\) の値でグループ分けすると，各グループ内でちょうど \(1\) つのマスが \(\partial Y(S)\) に含まれます． 別の言い方をすれば，\(\partial Y(S)\) の各マスについて，主対角線上にあるマスを集めてくると \(Y(S)\) に一致します．

つまり，\(g(i,j)=\min (i,j)\) とすれば上の等式は成立します． よって \(w(i,j)=1/\max(i,j)\) となります．

ここまでわかれば，\(w(i,j)\) をすべてのマスについて足し合わせれば良いです． これは累積和を用いると \(O(N)\) で計算できます．

よってこの問題は \(O(N)\) で解けます．

回答例