103136: [Atcoder]ABC313 G - Redistribution of Piles

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

问题描述

有编号为1到N的N个盘子。盘子i上有a_i个石头。还有一个空袋子。
你可以按照任意顺序任意次数（包括0次）执行以下两种操作。

• 从每个有一个或更多石头的盘子上移除一个石头。将移除的石头放入袋子里。
• 从袋子里取出N个石头，并将每个盘子上放一个石头。只有当袋子中有N个或更多石头时才能执行此操作。

当操作结束后，盘子i上有b_i个石头。输出在操作后可以得到的长度为N的整数序列(b_1, b_2, ..., b_N)的数量，对998244353取模。

限制条件

• 1 <= N <= 2 \* 10^5
• 0 <= a_i <= 10^9

输入

输入从标准输入中以以下格式给出：

$N$
$a_1$ $a_2$ $\dots$ $a_N$

输出

输出可能的序列(b_1, b_2, ..., b_N)的数量，对998244353取模。

样例输入1

3
3 1 3

样例输出1

7

例如，通过以下操作，b可以变为(2, 1, 2)。

• 执行第一个操作。b变为(2, 0, 2)。
• 执行第一个操作。b变为(1, 0, 1)。
• 执行第二个操作。b变为(2, 1, 2)。

以下七个序列可能是结果b。

• (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

有一个序列，(0)，可能是结果b。

样例输入3

5
1 3 5 7 9

样例输出3

36

样例输入4

10
766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044

样例输出4

666174028