Score : $625$ points

问题描述

设有编号为 $1$ 到 $N$ 的 $N$ 个盘子，其中第 $i$ 个盘子上有 $a_i$ 个石头。此外，还有一个空袋子。

你可以按照任意顺序执行以下两种操作任意次数（包括零次）：

• 从每个至少有一个石头的盘子上移除一个石头，并将移除的石头放入袋中。
• 当袋子中有 $N$ 个或更多石头时，从袋子里取出 $N$ 个石头，然后给每个盘子放一个石头。

令 $b_i$ 表示在完成所有操作后，第 $i$ 个盘子上的石头数量。请输出可以通过这些操作得到的长度为 $N$ 的整数序列 $(b_1, b_2, \dots, b_N)$ 的个数，结果对 $998244353$ 取模。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 08:56:41