No.1963 Subset Mex
タグ : / 解いたユーザー数 14
作問者 : 👑
tute7627
/ テスター :
PCTprobability
Problem Statement
There is a multiset $S$ consisting of $N$ integers. Initially, the $i$-th element of $S$ is $S_i$.
You may perform the following operation on $S$ any number of times, possibly $0$ times.
- Choose any number of elements of $S$, at least $1$. Remove the chosen elements from $S$, and add to $S$ the smallest non-negative integer not contained in the chosen elements.
Find the number of possible multisets $S$ after the operations, modulo $998244353$.
Two multisets are considered different if there exists a number $X$ whose number of occurrences differs between the two multisets.
Input
$N$ $S_1 \ S_2 \ \dots \ S_N$
- All inputs are integers.
- $1 \le N \le 100$
- $0 \le S_i \le 100$
Output
Find the number of possible multisets $S$ after the operations, modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
2 1 2
Output
8
$\{0\},\{0,0\},\{0,1\},\{0,2\},\{1\},\{1,1\},\{1,2\},\{2\}$ are possible.
For example, performing the operation on $1$ gives $\{0,2\}$, and then choosing both elements and performing the operation gives $\{1\}$.
Sample 2
Input
1 100
Output
3
Sample 3
Input
3 3 3 3
Output
21
Sample 4
Input
11 3 8 3 4 5 6 7 6 6 7 4
Output
22265
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。