部分点解法

\(A\) に \(-1\) が含まれない場合

問題文中の部分問題を解くことができれば良いです。

部分問題に現れる式を以下のように変形します。ここで、\(g\) は \(\alpha\) と \(\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} \]

ここで、

\[|\{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\]

の値を \(X_i\) の寄与と定義します。\(Y_j\) についても同様に定義します。

\(k=1,2,\cdots,N\) に対し、 \(X_i=k\) となるときの \(X_i\) の寄与を求めることについて考えます。\(X_i=k\) より \((A_1,\cdots,A_{X_i-1})\) に含まれる \(0\), \(1\) の個数はそれぞれ \(i,k-1-i\) となります。また、\(|\{j\mid Y_j<X_i,i\bmod g=j\bmod g\}|\) と \(|\{j\mid Y_j>X_i,i\bmod g=j\bmod g\}|\) はそれぞれ以下のように式変形できます。

\[ \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} \]

以上より、\(X_i=k\) のときの \(X_i\) の寄与は以下の式で表せます。

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

同様に考えると、 \(Y_j=k\) のときの \(Y_j\) の寄与は以下の式で表せることを導出できます。

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

この値を各 \((i,k)\), \((j,k)\) に対し足し合わせることで答えを求めることができます。なお、\(X_i=k\) の寄与は \(A_k\) が \(i\) 番目 (0-indexed) の \(0\) のとき、\(Y_j=k\) の寄与は \(A_k\) が \(j\) 番目 (0-indexed) の \(1\) のときにのみ生まれることに注意してください。

\(A\) に \(-1\) が含まれる場合

\(-1\) を置き換えた後の \(\alpha\) を固定します（このとき \(\beta\) も固定されます）。

以下のように DP を定義します。このとき、求める答えは \(\text{dp}_{N,\alpha}\) となります。

• \(\text{dp}_{k,l}\) \(\coloneqq\) \((A_1,\cdots,A_k)\) に含まれる \(0\) が \(l\) 個となるような、\((A_1,\cdots,A_k)\) に含まれる \(-1\) の置き換え方すべてに対する \(X_0,\cdots,X_{k-1},Y_0,\cdots,Y_{k-l-1}\) の寄与の合計

\(c_{k,l}\) を \((A_1,\cdots,A_{k})\) に含まれる \(0\) の個数が \(l\) となるような \((A_1,\cdots,A_k)\) の \(-1\) の置き換え方の数とします。上記の DP の遷移は以下のように表せます。

\(k=1,2,\cdots,N\) に対し、

• \(A_k=0\) または \(A_k=-1\) のとき、\(l=0,1,\cdots,k-1\) に対し、
  • \(0\) の個数が \(1\) 増えるため、\(\text{dp}_{k,l+1}\) に \(\text{dp}_{k-1,l}\) の値を加算する。
  • \(X_{l}=k\) の寄与が加わるため、\(\text{dp}_{k,l+1}\) に以下の値を加算する。

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

• \(A_k=1\) または \(A_k=-1\) のとき、\(l=0,1,\cdots,k-1\) に対し、
  • \(0\) の個数は変わらないため、\(\text{dp}_{k,l}\) に \(\text{dp}_{k-1,l}\) の値を加算する。
  • \(Y_{k-l-1}=k\) の寄与が加わるため、\(\text{dp}_{k,l}\) に以下の値を加算する。

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

\(\text{dp}_{k,l}\) と \(c_{k,l}\) の値を同時に更新することで、\(\text{dp}_{N,\alpha}\) の値を \(O(N^2)\) で求めることができます。

\(\alpha\) の取りうる値は \(1,2,\cdots,N-1\) より、この問題を \(O(N^3)\) で解くことができます。

実装例(C++)

なお、部分点の制約は \(N\leq100\) と小さいため、計算量が \(O(N^4)\) となっても十分高速です。

\(O(N^4)\) の実装例(C++)

満点解法

部分点解法では \(\alpha\) を固定しましたが、ここでは \(\alpha\) ではなく \(g\)（ \(\alpha\) と \(\beta\) の最大公約数）を固定します。

このとき \(\alpha\) の値がわからないため、部分点解法のような \(\alpha,\beta\) を含む DP の遷移ができません。そこで、\(X_i,Y_j\) の寄与を分割して考えることにします。

\(|\{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\) の値をそれぞれ \(X_i\) の前への寄与、後ろへの寄与と定義します。\(Y_j\) についても同様に定義します。

まず、前への寄与について考えます。

以下のように DP を定義します（部分点解法の DP とは異なります）。このとき、求める答えは \(\sum_{\gcd(\alpha,\beta)=g}\text{dp}_{N,\alpha}\) となります。

• \(\text{dp}_{k,l}\) \(\coloneqq\) \((A_1,\cdots,A_k)\) に含まれる \(0\) が \(l\) 個となるような、\((A_1,\cdots,A_k)\) に含まれる \(-1\) の置き換え方すべてに対する \(X_0,\cdots,X_{k-1},Y_0,\cdots,Y_{k-l-1}\) の前への寄与の合計

\(c_{k,l}\) を \((A_1,\cdots,A_{k})\) に含まれる \(0\) の個数が \(l\) となるような \((A_1,\cdots,A_k)\) の \(-1\) の置き換え方の数とします（こちらは部分点解法と同様です）。上記の DP の遷移は以下のように表せます。

\(k=1,2,\cdots,N\) に対し、

• \(A_k=0\) または \(A_k=-1\) のとき、\(l=0,1,\cdots,k-1\) に対し、
  • \(0\) の個数が \(1\) 増えるため、\(\text{dp}_{k,l+1}\) に \(\text{dp}_{k-1,l}\) の値を加算する。
  • \(X_{l}=k\) の前への寄与が加わるため、\(\text{dp}_{k,l+1}\) に以下の値を加算する。

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

• \(A_k=1\) または \(A_k=-1\) のとき、\(l=0,1,\cdots,k-1\) に対し、
  • \(0\) の個数は変わらないため、\(\text{dp}_{k,l}\) に \(\text{dp}_{k-1,l}\) の値を加算する。
  • \(Y_{k-l-1}=k\) の前への寄与が加わるため、\(\text{dp}_{k,l}\) に以下の値を加算する。

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

\(\text{dp}_{k,l}\) と \(c_{k,l}\) の値を同時に更新することで、\(\sum_{\gcd(\alpha,\beta)=g}\text{dp}_{N,\alpha}\) の値を \(O(N^2)\) で求めることができます。

\(X_i,Y_j\) の後ろへの寄与についても同様に求めることができ、\(A\) を反転することで実装が楽になります。詳細は実装例を参考にしてください。

\(g\) の取りうる値は \(N\) の約数であるため、この問題を \(O(N^2 d(N))\) で解くことができます。ここで、\(d(N)\) は \(N\) の約数の個数を表します。

実装例(C++)