/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 625 点
問題文
1 から N までの番号がついた N 枚の皿があります。皿 i には a_i 個の石が載っています。また、空の袋があります。
あなたは以下の 2 種類の操作を好きな順番で 0 回以上何度でも行うことができます。
- 石が 1 個以上載っている皿全てから石を 1 個ずつ取る。取った石は袋に移動する。
- 袋から石を N 個取り出し、全ての皿に 1 個ずつ石を載せる。ただし、この操作は袋に石が N 個以上ある場合にのみ行うことができる。
操作後に皿 i に載っている石の個数を b_i とします。b_i を並べてできる長さ N の整数列 (b_1, b_2, \dots, b_N) としてあり得るものの個数を 998244353 で割った余りを求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq a_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 \dots a_N
出力
(b_1, b_2, \dots, b_N) としてあり得るものの個数を 998244353 で割った余りを出力せよ。
入力例 1
3 3 1 3
出力例 1
7
例えば以下の手順で操作を行うと b は (2, 1, 2) になります。
- 1 番目の操作を行う。b は (2, 0, 2) になる。
- 1 番目の操作を行う。b は (1, 0, 1) になる。
- 2 番目の操作を行う。b は (2, 1, 2) になる。
操作後の b としてあり得る列は次の 7 種類です。
- (0, 0, 0)
- (1, 0, 1)
- (1, 1, 1)
- (2, 0, 2)
- (2, 1, 2)
- (2, 2, 2)
- (3, 1, 3)
入力例 2
1 0
出力例 2
1
操作後の b としてあり得るものは (0) の 1 種類です。
入力例 3
5 1 3 5 7 9
出力例 3
36
入力例 4
10 766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044
出力例 4
666174028
Score : 625 points
Problem Statement
There are N plates numbered 1 through N. Dish i has a_i stones on it. There is also an empty bag.
You can perform the following two kinds of operations any number of times (possibly zero) in any order.
- Remove one stone from each plate with one or more stones. Put the removed stones into the bag.
- Take N stones out of the bag, and put one stone to each plate. This operation can be performed only when the bag has N or more stones.
Let b_i be the number of stones on plate i after you finished the operations. Print the number, modulo 998244353, of sequences of integers (b_1, b_2, \dots, b_N) of length N that can result from the operations.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq a_i \leq 10^9
Input
The input is given from Standard Input in the following format:
N a_1 a_2 \dots a_N
Output
Print the number, modulo 998244353, of possible sequences (b_1, b_2, \dots, b_N).
Sample Input 1
3 3 1 3
Sample Output 1
7
For example, b becomes (2, 1, 2) by the following procedure.
- Perform the first operation. b becomes (2, 0, 2).
- Perform the first operation. b becomes (1, 0, 1).
- Perform the second operation. b becomes (2, 1, 2).
The following seven sequences can be the resulting b.
- (0, 0, 0)
- (1, 0, 1)
- (1, 1, 1)
- (2, 0, 2)
- (2, 1, 2)
- (2, 2, 2)
- (3, 1, 3)
Sample Input 2
1 0
Sample Output 2
1
There are one sequence, (0), that can be the resulting b.
Sample Input 3
5 1 3 5 7 9
Sample Output 3
36
Sample Input 4
10 766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044
Sample Output 4
666174028