No.3767 Earth Mover's Distance Sum
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 4
作問者 :
apricity
/ テスター :
👑 
AngrySadEight
タグ : / 解いたユーザー数 4
作問者 :
apricity
/ テスター :
👑
問題文最終更新日: 2026-10-08 16:44:52
yukicoder contest 518
(順位表)
の他の問題:
問題文
長さと総和が等しい二つの非負整数列 $X = (X_1, X_2, \dots, X_n)$ と $Y = (Y_1, Y_2, \dots, Y_n)$ に対して， $X$ に次の操作を繰り返して $Y$ に一致させる際の操作回数として考えられる最小値を $f(X,Y)$ とします．
- $1 \leq i \leq n$ かつ $X_i > 0$ を満たす整数 $i$ と， $1 \leq j \leq n$ かつ $|i-j| = 1$ を満たす整数 $j$ を選ぶ． $X_i$ を $X_i-1$ で， $X_j$ を $X_j+1$ で置き換える．
長さ $N$ の非負整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます． $A$ と長さおよび総和が等しいすべての非負整数列 $B$ に対する $f(A,B)$ の総和を $998244353$ で割った余りを求めてください．
入力
$N$ $A_1\ A_2\ \dots\ A_N$
- 入力はすべて整数．
- $2 \leq N \leq 10^6$
- $0 \leq A_i$
- $1 \leq \sum_{i=1}^{N} A_i \leq 10^6$
出力
考えられる $B$ すべてに対する $f(A,B)$ の総和を $998244353$ で割った余りを出力してください．
サンプル
サンプル1
入力
3 1 0 1
出力
8
$B$ として考えられるものは $(0,0,2), (0,1,1), (0,2,0), (1,0,1), (1,1,0), (2,0,0)$ の $6$ 通りです． $B = (0,0,2)$ のとき，次のようにして $2$ 回で $A$ を $B$ に一致させることができ，これが最小の操作回数です．
- $i=1, j=2$ を選ぶ． $A = (0,1,1)$ となる．
- $i=2, j=3$ を選ぶ． $A = (0,0,2)$ となる．
その他の $B$ に対する $f(A,B)$ の値は以下の通りです．
- $B = (0,1,1)$ のとき， $f(A,B) = 1$ です．
- $B = (0,2,0)$ のとき， $f(A,B) = 2$ です．
- $B = (1,0,1)$ のとき， $f(A,B) = 0$ です．
- $B = (1,1,0)$ のとき， $f(A,B) = 1$ です．
- $B = (2,0,0)$ のとき， $f(A,B) = 2$ です．
よって答えは $2+1+2+0+1+2 = 8$ です．
サンプル2
入力
2 0 1
出力
1
サンプル3
入力
5 1 5 2 3 4
出力
42018
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。