We focus on the Young diagram corresponding to \(S\). The path of the Young diagram is defined as the path obtained by associating 0 and 1 with leftward and downward movements, respectively. This is denoted as \(Y(S)\).

For example, the Young diagram corresponding to \(S=\)1101010 is as follows:

OOO
OOO
OO
O

Let \((i,j)\) denote the cell at the \(i\)-th row and \(j\)-th column.

Let \(f(S)\) be the answer to the problem for \(S\). It would be very nice if, for each cell \((i,j)\), there exists a weight \(w(i,j)\) that depends only on \(i\) and \(j\) so that \(f(S)=\sum_{(i,j) \in Y(S)} w(i,j)\). So, we assume that such \(w(i,j)\) exists and consider what values it might take.

Let’s consider how \(Y(S)\) changes by performing one operation on \(S\).

We consider the cells that might be removed by performing one operation and call this set \(\partial Y(S)\). As an example, \(\partial Y(S)\) corresponding to \(S\) mentioned above is shown with X in the diagram below.

OOX
OXX
XX
X

For \((i,j) \in \partial Y(S)\), there are \(i \times j\) ways to perform an operation that removes this cell. Let \(A\) be the area of \(Y(S)\). \(w(i,j)\) should satisfy the following equation:

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

Let \(g(i,j) = i \times j \times w(i,j)\) and transform the equation. We want to satisfy the following:

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

Now, let’s consider \(\partial Y(S)\). If we group the cells of \(Y(S)\) by the value of \(i-j\), exactly one cell in each group will be included in \(\partial Y(S)\). In other words, if we collect the cells on the diagonal lines from top-left to bottom-right containing each cell in \(\partial Y(S)\), those cells match \(Y(S)\).

Thus, if \(g(i,j)=\min (i,j)\), the above equation holds. Therefore, \(w(i,j)=1/\max(i,j)\).

Once we understand this, we just need to sum \(w(i,j)\) for all cells. This can be calculated in \(O(N)\) using cumulative sums.

Therefore, this problem can be solved in \(O(N)\).

Sample Implementation