問題一覧 > 通常問題

No.1963 Subset Mex

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : 👑 tute7627tute7627 / テスター : PCTprobabilityPCTprobability
1 ProblemId : 7836 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-27 20:17:31

問題文

$N$ 個の整数からなる多重集合 $S$ があります。最初、$S$ の $i$ 個目の要素は $S_i$ です。

あなたは $S$ に対して以下の操作を $0$ 回以上の任意の回数行うことができます。

  • $S$ の要素を $1$ 個以上の任意の個数選択する。選んだ要素を $S$ から削除し、選んだ要素に含まれない最小の非負整数を $S$ に追加する。

操作後の $S$ としてあり得るものの数を $998244353$ で割った余りを求めてください。

二つの多重集合が異なるとは、ある数 $X$ が含まれる個数が二つの多重集合で異なることを指します。

入力

$N$
$S_1 \ S_2 \ \dots \ S_N$

  • 入力は全て整数である。
  • $1 \le N \le 100$
  • $0 \le S_i \le 100$

出力

操作後の $S$ としてあり得るものの数を $998244353$ で割った余りを求めてください。 最後に改行してください。

サンプル

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

$\{0\},\{0,0\},\{0,1\},\{0,2\},\{1\},\{1,1\},\{1,2\},\{2\}$ があり得ます。
例えば、$1$ に対して操作を行うと、$\{0,2\}$ となり、その後、両方の要素を選んで操作を行うと $\{1\}$ となります。

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

サンプル3
入力
3
3 3 3
出力
21

サンプル4
入力
11
3 8 3 4 5 6 7 6 6 7 4
出力
22265

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