分数: 500 点
问题陈述
给你一个正整数的多重集 N 元素: A=\lbrace A_1,A_2,\dots,A_N \rbrace.
您可以重复以下操作任意次数(可能为零)。
- 选择一个正整数 x 至少出现两次 A。删除两次出现的 x 来自 A,并添加出现一次 x+1 to A.
求模数 998244353,多重集 A 可以到底。
约束
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 2 \times 10^5
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
4 1 1 2 4
示例输出 1
3
A 可以是三个多重集之一 \lbrace 1,1,2,4 \rbrace,\lbrace 2,2,4 \rbrace,\lbrace 3,4 \rbrace 最后。
你可以 A = \lbrace 3,4 \rbrace 如下。
- 选择 x = 1。删除两个 1来自 A 并添加一个 2 to A, 制作 A=\lbrace 2,2,4 \rbrace.
- 选择 x = 2。删除两个 2来自 A 并添加一个 3 to A, 制作 A=\lbrace 3,4 \rbrace.
示例输入 2
5 1 2 3 4 5
示例输出 2
1
示例输入 3
13 3 1 4 1 5 9 2 6 5 3 5 8 9
示例输出 3
66