No.1533 Don't be Negative!
タグ : / 解いたユーザー数 12
作問者 :
PCTprobability
/ テスター :
tatyam
googol_S0
注意
この問題のTLは $8$ secです。
問題文
Not Negative
整数列 $X_1,X_2,\dots,X_N$ が与えられます。
あなたは以下の操作を $0$ 回以上行うことができます。
ある要素 $X_i$ を選択する。その後、以下の $3$ 個の行動を同時に行う。
- もし $X_{i-1}$ が存在するならば $X_{i-1}=X_{i-1}+X_i$ とする。
- もし $X_{i+1}$ が存在するならば $X_{i+1}=X_{i+1}+X_i$ とする。
- $X_i=-X_i$ とする。
$X$ の全ての要素を非負にするために必要な操作の最小回数を求めてください。有限回の操作で $X$ の全ての要素を非負にできることが証明可能です。
しかし、PCT君は $X$ の要素を全て忘れてしまい、落ち込んでしまいました。しかし、$X$ の要素の絶対値は $K$ でないことは覚えていました。そこで問題を以下のように変更しました。
Don't be Negative!
全ての要素が $-M$ 以上 $M$ 以下かつ絶対値が $K$ でない整数である長さ $N$ の数列 $A_1,A_2,\dots,A_N$ 全てに対して Not Negative を解き、解の総和を $\bmod 998244353$ で求めてください。
ネガティブになっているPCT君を元気付けるために Don't be Negative! を解いてください。
入力
$N\ M\ K$
- 入力は全て整数である。
- $1 \le N \le 4 \times 10^{\Large{\textcolor{red}{4}}}$
- $1 \le M \le 4$
- $0 \le K \le M$
出力
Don't be Negative の解を出力してください。
サンプル
サンプル1
入力
2 1 0
出力
5
数列 $A$ に対して $f(A)$ を Not Negative の $A$ に対する解と定義します。(20:53 追記)
$f(1,-1)$ を求めます。
$X_2$ を選ぶことにより $(1,-1)$ が $(0,1)$ となり条件を満たします。$0$ 回以下の操作で $X$ の要素を全て正にすることはできないので $f(1,-1)=1$ です。
それ以外に $f(a,b)$ が正になるものを列挙すると、$f(-1,1)=1,f(-1,-1)=3$ なので解は $1+1+3=5$ です。
サンプル2
入力
3 3 2
出力
306
サンプル3
入力
10 4 2
出力
49870937
サンプル4
入力
2021 4 0
出力
180258189
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。