AT_ttpc2024_2_k 01 Abs Sum

$ 0 $ , $ 1 $ , $ -1 $ からなる長さ $ N $ の数列 $ A=(A_1,A_2,\cdots,A_N) $ が与えられます。 $ A $ に含まれる $ −1 $ をすべて $ 0 $ または $ 1 $ で置き換える方法は、 $ A $ に含まれる $ −1 $ の個数を $ q $ とすると $ 2^q $ 通りあります。このうち $ A $ に $ 0 $ と $ 1 $ を両方含むものすべてに対して、以下の問題を解いたときの答えの和を $ 998244353 $ で割ったあまりを求めてください。 > $ A $ に含まれる $ 0 $ , $ 1 $ の個数をそれぞれ $ \alpha $ , $ \beta $ とします。 > また、 $ A_i=0 $ となるような $ i $ を小さい順に並べた数列を $ X=(X_0,X_1,\cdots,X_{\alpha-1}) $ とし、 $ A_i=1 $ となるような $ i $ を小さい順に並べた数列を $ Y=(Y_0,Y_1,\cdots,Y_{\beta-1}) $ とします( $ X $ と $ Y $ はともに添え字が $ 0 $ から始まることに注意してください)。 > > $ \displaystyle\sum_{i=0}^{\mathrm{LCM}(\alpha,\beta)-1}|X_{(i\bmod \alpha)}-Y_{(i\bmod \beta)}| $ > > > > の値を求めてください。 ただし、 $ \mathrm{LCM}(x,y) $ は $ x $ と $ y $ の最小公倍数、 $ x\bmod y $ は $ x $ を $ y $ で割ったあまりを表すものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ。

### 部分点 - 追加の制約 $ N\leq 100 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 $ A=(1,1,0,0) $ のとき $ |3-1|+|4-2|=4 $ $ A=(1,1,0,1) $ のとき $ |3-1|+|3-2|+|3-4|=4 $ $ A=(1,1,1,0) $ のとき $ |4-1|+|4-2|+|4-3|=6 $ よって、答えは $ 4+4+6=14 $ となります。 ### Sample Explanation 2 $ 0 $ と $ 1 $ を両方含むような数列を作れないため、答えは $ 0 $ となります。 ### Constraints - 入力はすべて整数 - $ 2\leq N\leq 2250 $ - $ A_i $ は $ 0 $ , $ 1 $ , $ -1 $ のいずれか $ (i=1,2,\cdots,N) $