問題一覧 > 通常問題

No.2485 Add to Variables (Another)

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

問題文

ここに、長さ NN の数列 AA があります。最初、 AA のすべての値は 00 です。

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

  • 何もしない。
  • 整数 k (1≤k≤N−1)k \ (1 \leq k \leq N-1) を選び、1≤i≤k1 \leq i \leq k を満たす全ての整数 ii について、 AiA_i に 11 を足す。
  • 整数 k (2≤k≤N)k \ (2 \leq k \leq N) を選び、k≤i≤Nk \leq i \leq N を満たす全ての整数 ii について、 AiA_i に 11 を足す。
  • 1≤i≤N1 \leq i \leq N を満たすすべての整数 ii について、 AiA_i に 11 を足す。

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

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

入力

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

NN MM
B1B_1 B2B_2 …\ldots BNB_N
  • 入力はすべて整数
  • 1≤N,M≤10001 \leq N,M \leq 1000
  • 0≤Bi≤M0 \leq B_i \leq M

    • 出力

    答えを出力せよ。

    サンプル

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

    11 回目の操作で A1,A2,A3A_1,A_2,A_3 に 11 を足し、22 回目の操作でどの変数にも 11 を足さない方法と、11 回目の操作でどの変数にも 11 を足さず 22 回目の操作で A1,A2,A3A_1,A_2,A_3 に 11 を足す方法の 22 通りが考えられます。

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

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