No.1533 Don't be Negative!
タグ : / 解いたユーザー数 13
作問者 :
PCTprobability
/ テスター :
tatyam
googol_S0
Note
The time limit for this problem is $8$ sec.
Problem Statement
Not Negative
You are given an integer sequence $X_1,X_2,\dots,X_N$.
You may perform the following operation $0$ or more times.
Choose an element $X_i$. Then, perform the following $3$ actions simultaneously.
- If $X_{i-1}$ exists, set $X_{i-1}=X_{i-1}+X_i$.
- If $X_{i+1}$ exists, set $X_{i+1}=X_{i+1}+X_i$.
- Set $X_i=-X_i$.
Find the minimum number of operations required to make all elements of $X$ non-negative. It can be proven that all elements of $X$ can be made non-negative with a finite number of operations.
However, PCT-kun forgot all the elements of $X$ and became depressed. Still, he remembered that the absolute value of each element of $X$ is not $K$. So the problem was changed as follows.
Don't be Negative!
Solve Not Negative for every sequence $A_1,A_2,\dots,A_N$ of length $N$ whose elements are all integers between $-M$ and $M$, inclusive, with absolute value not equal to $K$, and find the sum of the answers modulo $\bmod 998244353$.
To cheer up PCT-kun, who is feeling negative, please solve Don't be Negative!.
Input
$N\ M\ K$
- All inputs are integers.
- $1 \le N \le 4 \times 10^{\Large{\textcolor{red}{4}}}$
- $1 \le M \le 4$
- $0 \le K \le M$
Output
Output the answer to Don't be Negative.
Sample
Sample 1
Input
2 1 0
Output
5
For a sequence $A$, define $f(A)$ as the answer to Not Negative for $A$. (Added at 20:53)
Let us find $f(1,-1)$.
Choosing $X_2$ turns $(1,-1)$ into $(0,1)$, which satisfies the condition. Since it is impossible to make all elements of $X$ positive with $0$ or fewer operations, $f(1,-1)=1$.
The other cases where $f(a,b)$ is positive are $f(-1,1)=1,f(-1,-1)=3$, so the answer is $1+1+3=5$.
Sample 2
Input
3 3 2
Output
306
Sample 3
Input
10 4 2
Output
49870937
Sample 4
Input
2021 4 0
Output
180258189
Output the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。