問題一覧 > 通常問題

No.1693 Invasion

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 99
作問者 : eSeFeSeF / テスター : 👑 KazunKazun 👑 ygussanyygussany
18 ProblemId : 6643 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-29 17:45:49

問題文

横一列に並んだ $M$ 個のマスがあります。 SF くんは、以下のような操作を $0$ 回以上繰り返すことで、これらのマスに区別のないコインを置くことにしました。

  • 操作開始時点でコインの置かれていないマスの個数を $x$ とする。
  • $1\le i\le N$ かつ $A_i\le x$ を満たす整数 $i$ を指定する。ここで、過去の操作で選んだ $i$ を再度指定しても構わない。(条件を満たす $i$ がない場合、操作は行えない。)
  • まだコインの置かれていないマスを $A_i$ 個自由に選ぶ。 ただし、コインの置かれていないマスのうち最も左にあるマスは必ず選ばなければならない
  • 選んだ全てのマスにコインを置く。

操作を終えたあとのコインの配置として考えられるものの個数を $998244353$ で割ったあまりを求めてください。

ここで、2つのコインの配置が異なるとは、あるマスが存在して、一方でのみそのマスにコインが置かれていることとします。

入力

$N\ \ M$
$A_1\ \cdots \ A_N$
【制約】
  • $1\le N\le 100$
  • $N\le M\le 10^5$
  • $1\le A_i\le M$
  • $i\neq j$ ならば $A_i\neq A_j$
  • 入力は全て整数

出力

答えを $\bmod{998244353}$ で出力せよ。

サンプル

サンプル1
入力
2 3
1 2
出力
5

コインの置かれているマスを 'o'、置かれていないマスを '.' で表せば、 以下のような配置が考えられます。

  • ...
  • o..
  • oo.
  • o.o
  • ooo

最終的な配置が同じであれば、操作手順を区別しないことに注意してください。

サンプル2
入力
1 11
11
出力
2

サンプル3
入力
3 141
5 9 2
出力
113653783

$\bmod{998244353}$ で出力してください。

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