問題一覧 > 通常問題

No.1555 Constructed Balancing Sequence

レベル : / AI推定難易度 : 2375 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : chineristAC / テスター : maspy
お気に入りにしたユーザー ProblemId : 5715 / 自分の提出
問題文最終更新日: 2021-06-07 00:56:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 300 (順位表) の他の問題:

Problem Statement

An integer sequence $A=(A_1,\ A_2,\ \dots ,\ A_N)$ of length $N$ is called a "well-balanced sequence" if $\displaystyle \sum_{k=1}^{i-1}A_{k} \geq A_{i}$ holds for every $i\ (2\le i \le N)$.

For example, the sequence $(2,\ 1,\ 3,\ 6)$ is a "well-balanced sequence", but $(3,\ 2,\ -2,\ 4)$ is not a "well-balanced sequence".

First, you are given integers $N,K$ and an integer sequence $A=(A_1,\ A_2,\ \dots ,\ A_N)$ of length $N$.

Find the number, modulo $998244353$, of integer sequences $B=(B_1,\ B_2,\ \dots ,\ B_N)$ of length $N$ that satisfy all of the following conditions.

Conditions

  • $-K \leq B_i \leq K$ holds for every $1\le i \le N$
  • Among the "well-balanced sequences" $C=(C_1,\ C_2,\ \dots,\ C_N)$ of length $N$ such that $B_i \leq C_i$ holds for every $1\le i \le N$, the lexicographically smallest one is $A$

Input

$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)$
  • All values in the input are integers
  • The given sequence $A$ is a "well-balanced sequence"

Output

Output the answer.

Print a newline at the end.

Sample

Sample 1
Input
3 1
1 0 1
Output
6

For example, the sequence $B=(-1,\ 0,\ 1)$ satisfies the conditions.

$B=(0,\ -1,\ 0)$ does not satisfy the conditions, because $C=(0,\ 0,\ 0)$ can be taken as $C$, and this is lexicographically smaller than $A$.

Sample 2
Input
13 600
2 1 3 6 4 16 32 64 -53 75 150 300 600
Output
698798218

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