No.1555 Constructed Balancing Sequence
タグ : / 解いたユーザー数 12
作問者 :
maspy
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もしくは右上の雲マークをクリックしてアカウントを作成してください。