Partial Points Solution

When \(A\) Does Not Contain \(-1\)

It suffices to solve the subproblem described in the problem statement.

The expression in the subproblem can be transformed as follows. Here, \(g\) is the greatest common divisor of \(\alpha\) and \(\beta\).

\[ \begin{aligned} &\sum_{i=0}^{\mathrm{LCM}(\alpha,\beta)-1}|X_{(i\bmod \alpha)}-Y_{(i\bmod \beta)}| \\ =& \sum_{i\bmod g=j\bmod g}|X_i-Y_j|\\ =& \sum_{i\bmod g=j\bmod g,\,X_i<Y_j}-(X_i-Y_j)+\sum_{i\bmod g=j\bmod g,\,X_i>Y_j}(X_i-Y_j) \\ =& \sum_{i=0}^{\alpha-1}|\{j\mid Y_j<X_i,i\bmod g=j\bmod g\}|\times X_i +\sum_{j=0}^{\beta-1}|\{i\mid X_i<Y_j,i\bmod g=j\bmod g\}|\times Y_j \\ & -\sum_{i=0}^{\alpha-1}|\{j\mid Y_j>X_i,i\bmod g=j\bmod g\}|\times X_i -\sum_{j=0}^{\beta-1}|\{i\mid X_i>Y_j,i\bmod g=j\bmod g\}|\times Y_j \end{aligned} \]

Here, we define the value of

\[|\{j\mid Y_j<X_i,i\bmod g=j\bmod g\}|\times X_i -|\{j\mid Y_j>X_i,i\bmod g=j\bmod g\}|\times X_i\]

as the contribution of \(X_i\). Similarly, the contribution of \(Y_j\) is defined.

For \(k=1,2,\cdots,N\), consider determining the contribution of \(X_i\) when \(X_i=k\). Since \(X_i=k\), the number of \(0\)s and \(1\)s in \((A_1,\cdots,A_{X_i-1})\) are \(i\) and \(k-1-i\), respectively. Additionally, \(|\{j\mid Y_j<X_i,i\bmod g=j\bmod g\}|\) and \(|\{j\mid Y_j>X_i,i\bmod g=j\bmod g\}|\) can be transformed as follows:

\[ \begin{aligned} |\{j\mid Y_j<X_i,i\bmod g=j\bmod g\}|&=\Big\lceil\frac{|\{j\mid Y_j<X_i\}|-(i\bmod g)}{g}\Big\rceil \\ &=\Big\lceil\frac{k-1-i-(i\bmod g)}{g}\Big\rceil\\ |\{j\mid Y_j>X_i,i\bmod g=j\bmod g\}|&=\frac{\beta}{g}-|\{j\mid Y_j<X_i,i\bmod g=j\bmod g\}| \\ &=\frac{\beta}{g}-\Big\lceil\frac{k-1-i-(i\bmod g)}{g}\Big\rceil \end{aligned} \]

Thus, the contribution of \(X_i\) when \(X_i=k\) can be expressed as follows:

\[\Big(2\Big\lceil\frac{k-1-i-(i\bmod g)}{g}\Big\rceil-\frac{\beta}{g}\Big)k\]

Similarly, the contribution of \(Y_j\) when \(Y_j=k\) can be derived as follows:

\[\Big(2\Big\lceil\frac{k-1-j-(j\bmod g)}{g}\Big\rceil-\frac{\alpha}{g}\Big)k\]

By summing these values for all \((i,k)\) and \((j,k)\), the solution can be obtained. Note that the contribution of \(X_i=k\) arises only when \(A_k\) corresponds to the \(i\)-th (0-indexed) \(0\), and the contribution of \(Y_j=k\) arises only when \(A_k\) corresponds to the \(j\)-th (0-indexed) \(1\).

When \(A\) Contains \(-1\)

Fix the \(\alpha\) after replacing \(-1\) (in this case, \(\beta\) is also fixed).

Define the DP as follows. The desired answer is \(\text{dp}_{N,\alpha}\).

• \(\text{dp}_{k,l}\) \(\coloneqq\) The sum of contributions of \(X_0,\cdots,X_{k-1},Y_0,\cdots,Y_{k-l-1}\) for all ways of replacing \(-1\) in \((A_1,\cdots,A_k)\) such that the number of \(0\)s is \(l\).

Let \(c_{k,l}\) denote the number of ways to replace \(-1\)s in \((A_1,\cdots,A_k)\) such that the number of \(0\)s is \(l\). The DP transition can be expressed as follows:

For \(k=1,2,\cdots,N\):

• When \(A_k=0\) or \(A_k=-1\), for \(l=0,1,\cdots,k-1\):
  • Since the number of \(0\)s increases by \(1\), add \(\text{dp}_{k-1,l}\) to \(\text{dp}_{k,l+1}\).
  • Add the following value to \(\text{dp}_{k,l+1}\) for the contribution of \(X_{l}=k\):

\[\Big(2\Big\lceil\frac{k-1-l-(l\bmod g)}{g}\Big\rceil-\frac{\beta}{g}\Big)k\times c_{k-1,l}\]

• When \(A_k=1\) or \(A_k=-1\), for \(l=0,1,\cdots,k-1\):
  • Since the number of \(0\)s remains unchanged, add \(\text{dp}_{k-1,l}\) to \(\text{dp}_{k,l}\).
  • Add the following value to \(\text{dp}_{k,l}\) for the contribution of \(Y_{k-l-1}=k\):

\[\Big(2\Big\lceil\frac{l-((k-1-l)\bmod g)}{g}\Big\rceil-\frac{\alpha}{g}\Big)k\times c_{k-1,l}\]

By simultaneously updating \(\text{dp}_{k,l}\) and \(c_{k,l}\), the value of \(\text{dp}_{N,\alpha}\) can be computed in \(O(N^2)\).

Since \(\alpha\) can take values \(1,2,\cdots,N-1\), this problem can be solved in \(O(N^3)\).

Example Implementation (C++)

Note that since the constraint for partial points is \(N\leq100\), even a time complexity of \(O(N^4)\) is fast enough.

Example Implementation with \(O(N^4)\) (C++)

Full Points Solution

Instead of fixing \(\alpha\) as in the partial points solution, we fix \(g\) (the greatest common divisor of \(\alpha\) and \(\beta\)).

Since \(\alpha\) is unknown in this case, the DP transitions involving \(\alpha,\beta\) in the partial points solution cannot be used. Instead, we divide and consider the contributions of \(X_i,Y_j\).

The values \(|\{j\mid Y_j<X_i,i\bmod g=j\bmod g\}|\times X_i\) and \(|\{j\mid Y_j>X_i,i\bmod g=j\bmod g\}|\times X_i\) are defined as the forward contribution and backward contribution of \(X_i\), respectively. Similarly, these are defined for \(Y_i\).

First, we consider the forward contribution.

Define the DP as follows (different from the DP in the partial points solution). The desired answer is \(\sum_{\gcd(\alpha,\beta)=g}\text{dp}_{N,\alpha}\).

• \(\text{dp}_{k,l}\) \(\coloneqq\) The sum of forward contributions of \(X_0,\cdots,X_{k-1},Y_0,\cdots,Y_{k-l-1}\) for all ways of replacing \(-1\) in \((A_1,\cdots,A_k)\) such that the number of \(0\)s is \(l\).

Let \(c_{k,l}\) denote the number of ways to replace \(-1\)s in \((A_1,\cdots,A_k)\) such that the number of \(0\)s is \(l\) (same as in the partial points solution). The DP transition can be expressed as follows:

For \(k=1,2,\cdots,N\):

• When \(A_k=0\) or \(A_k=-1\), for \(l=0,1,\cdots,k-1\):
  • Since the number of \(0\)s increases by \(1\), add \(\text{dp}_{k-1,l}\) to \(\text{dp}_{k,l+1}\).
  • Add the following value to \(\text{dp}_{k,l+1}\) for the forward contribution of \(X_{l}=k\):

\[\Big\lceil\frac{k-1-l-(l\bmod g)}{g}\Big\rceil\times k\times c_{k-1,l}\]

• When \(A_k=1\) or \(A_k=-1\), for \(l=0,1,\cdots,k-1\):
  • Since the number of \(0\)s remains unchanged, add \(\text{dp}_{k-1,l}\) to \(\text{dp}_{k,l}\).
  • Add the following value to \(\text{dp}_{k,l}\) for the forward contribution of \(Y_{k-l-1}=k\):

\[\Big\lceil\frac{k-1-l-(l\bmod g)}{g}\Big\rceil\times k\times c_{k-1,l}\]

The contribution to the back of \(X_i\) and \(Y_j\) can also be calculated in the same way, and by reversing \(A\), the implementation becomes easier. For details, please refer to the implementation example.

The possible values of \(g\) are divisors of \(N\), so this problem can be solved in \(O(N^2 d(N))\). Here, \(d(N)\) represents the number of divisors of \(N\).

Implementation Example (C++)