問題一覧 > 通常問題

No.1533 Don't be Negative!

レベル : / AI推定難易度 : 2800 / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : PCTprobability / テスター : tatyam googol_S0
お気に入りにしたユーザー ProblemId : 6389 / 自分の提出
問題文最終更新日: 2021-06-04 20:53:50
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 298 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。