/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正整数からなる N 要素の多重集合 A=\lbrace A_1,A_2,\dots,A_N \rbrace が与えられます。
あなたは、以下の操作を好きな回数 ( 0 回でもよい) 繰り返すことが出来ます。
- A に 2 個以上含まれる正整数 x を選ぶ。A から x を 2 個削除し、A に x+1 を 1 個加える。
最終的な A としてあり得るものの個数を 998244353 で割ったあまりを求めてください。
制約
- 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 の 3 個があります。
\lbrace 3,4 \rbrace は以下のようにして作ることが出来ます。
- x として 1 を選ぶ。A から 1 を 2 個削除し、2 を 1 個加える。A=\lbrace 2,2,4 \rbrace となる。
- x として 2 を選ぶ。A から 2 を 2 個削除し、3 を 1 個加える。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
Score : 500 points
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.
Sample Input 1
4 1 1 2 4
Sample 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 1s from A and add one 2 to A, making A=\lbrace 2,2,4 \rbrace.
- Choose x = 2. Delete two 2s from A and add one 3 to A, making A=\lbrace 3,4 \rbrace.
Sample Input 2
5 1 2 3 4 5
Sample Output 2
1
Sample Input 3
13 3 1 4 1 5 9 2 6 5 3 5 8 9
Sample Output 3
66