問題一覧 > 通常問題

No.1555 Constructed Balancing Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 : chineristACchineristAC / テスター : maspymaspy
3 ProblemId : 5715 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-07 00:56:03

問題文

長さ $N$ の整数列 $A=(A_1,\ A_2,\ \dots ,\ A_N)$ は、任意の $i\ (2\le i \le N)$ に対し $\displaystyle \sum_{k=1}^{i-1}A_{k} \geq A_{i}$ が成り立つとき、「バランスの良い数列」であるといいます。

例えば数列 $(2,\ 1,\ 3,\ 6)$ は「バランスの良い数列」ですが、 $(3,\ 2,\ -2,\ 4)$ は「バランスの良い数列」ではありません。

はじめに整数 $N,K$ と長さ $N$ の整数列 $A=(A_1,\ A_2,\ \dots ,\ A_N)$ が与えられます。

以下の条件をすべて満たすような長さ $N$ の整数列 $B=(B_1,\ B_2,\ \dots ,\ B_N)$ の総数を $998244353$ で割った余りを求めてください。

条件

  • すべての $1\le i \le N$ に対し $-K \leq B_i \leq K$ が成り立つ
  • 長さ $N$ の「バランスの良い数列」 $C=(C_1,\ C_2,\ \dots,\ C_N)$ であって、すべての $1\le i \le N$ に対し $B_i \leq C_i$ が成り立つもののうち、辞書式順序で最小のものは $A$ である

入力

$N\ K$
$A_1\ A_2\ \dots\ A_N$

  • $2 \leq N \leq 10^5$
  • $1 \leq K \leq 10^5$
  • $-K \leq A_i \leq K\ (1\le i \le N)$
  • 与えられる入力はすべて整数
  • 与えられる数列 $A$ は「バランスの良い数列」

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 1
1 0 1
出力
6

例えば数列 $B=(-1,\ 0,\ 1)$ などが条件を満たします。

$B=(0,\ -1,\ 0)$ は $C$ として $C=(0,\ 0,\ 0)$ がとれ、これは辞書式順序で $A$ よりも小さいため条件を満たしません。

サンプル2
入力
13 600
2 1 3 6 4 16 32 64 -53 75 150 300 600
出力
698798218

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。