AtCoder Regular Contest 160
翻译中…
Problem Statement
翻译中…
You are given a multiset of positive integers with $N$ elements: $A=\lbrace A_1,A_2,\dots,A_N \rbrace$.
翻译中…
You may repeat the following operation any number of times (possibly zero).
翻译中…
- Choose a positive integer
$x$that occurs at least twice in$A$. Delete two occurrences of$x$from$A$, and add one occurrence of$x+1$to$A$.
翻译中…
Find the number, modulo $998244353$, of multisets that $A$ can be in the end.
翻译中…
Constraints
翻译中…
$1 \le N \le 2 \times 10^5$$1 \le A_i \le 2 \times 10^5$
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N
A_1 A_2 \dots A_N翻译中…
Output
翻译中…
Print the answer.
翻译中…
样例
Input #1
4
1 1 2 4
Output #1
3
$A$ can be one of the three multisets $\lbrace 1,1,2,4 \rbrace,\lbrace 2,2,4 \rbrace,\lbrace 3,4 \rbrace$ in the end.
You can make $A = \lbrace 3,4 \rbrace$ as follows.
- Choose $x = 1$. Delete two $1$s from $A$ and add one $2$ to $A$, making $A=\lbrace 2,2,4 \rbrace$.
- Choose $x = 2$. Delete two $2$s from $A$ and add one $3$ to $A$, making $A=\lbrace 3,4 \rbrace$.
Input #2
5
1 2 3 4 5
Output #2
1
Input #3
13
3 1 4 1 5 9 2 6 5 3 5 8 9
Output #3
66
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。