問題一覧 > 通常問題

No.2485 Add to Variables (Another)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : ytqm3ytqm3 / テスター : MagentorMagentor
3 ProblemId : 10114 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-22 21:45:16
F 問題と G 問題は設定が共通しており、制約のみが異なります。

問題文

ここに、長さ $N$ の数列 $A$ があります。最初、 $A$ のすべての値は $0$ です。

この数列に対し、以下の $4$ 種類の操作を行うことを考えます。

  • 何もしない。
  • 整数 $k \ (1 \leq k \leq N-1)$ を選び、$1 \leq i \leq k$ を満たす全ての整数 $i$ について、 $A_i$ に $1$ を足す。
  • 整数 $k \ (2 \leq k \leq N)$ を選び、$k \leq i \leq N$ を満たす全ての整数 $i$ について、 $A_i$ に $1$ を足す。
  • $1 \leq i \leq N$ を満たすすべての整数 $i$ について、 $A_i$ に $1$ を足す。

操作をちょうど $M$ 回行う方法のうち、 $A=B$ となるものの個数を $998244353$ で割った余りを求めてください。

ただし、ある整数 $i$ が存在して $i$ 回目に $1$ が足された数の index の集合が異なる時、またその時に限り操作列が異なるとみなします。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$B_1$ $B_2$ $\ldots$ $B_N$
  • 入力はすべて整数
  • $1 \leq N,M \leq 1000$
  • $0 \leq B_i \leq M$

    • 出力

    答えを出力せよ。

    サンプル

    サンプル1
    入力
    4 2
1 1 1 0
    出力
    2

    $1$ 回目の操作で $A_1,A_2,A_3$ に $1$ を足し、$2$ 回目の操作でどの変数にも $1$ を足さない方法と、$1$ 回目の操作でどの変数にも $1$ を足さず $2$ 回目の操作で $A_1,A_2,A_3$ に $1$ を足す方法の $2$ 通りが考えられます。

    サンプル2
    入力
    4 2
1 1 1 1
    出力
    8
    $1$ 回目の操作で $1$ が足されなかった変数に $1$ を足すときに限り $A_1=A_2=A_3=A_4=1$ を達成することが出来るので、答えは $8$ 通りです。
    サンプル3
    入力
    4 3
0 3 2 2
    出力
    0
    サンプル4
    入力
    4 314
202 3 9 22
    出力
    362672301
    サンプル5
    入力
    1 1
1
    出力
    1

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