Problem from Red Panda

题意翻译

### 题目描述 有不超过 $10^6$ 个气球，每个气球被染上了 $k$ 种颜色中的一种，颜色用 $1 \sim k$ 进行标号。你可以选择做若干次（可以不做）以下操作： - 选择一个颜色 $i \in [1,k]$，如果其他的 $k-1$ 种颜色的气球每种都至少有一个，则在每一种其他颜色中选出一个气球染成颜色 $i$。 现在给出初始每种颜色的气球数量，你需要求出通过做若干次操作能够得到的不同的气球组合方案数对 $998244353$ 取模。两种气球组合方案不同当且仅当其中存在一种颜色满足在两种方案中染上这个颜色的气球数量不同。 ### 输入格式 第一行一个整数 $k$ 表示颜色数量，接下来一行 $k$ 个非负整数 $a_1,a_2,...,a_k$ 分别表示颜色 $1,2,...,k$ 的气球的初始数量。 ### 输出格式 一行一个整数表示方案数 $\bmod\ 998244353$。 ### 数据范围 $2 \leq k \leq 10^5 , a_i \geq 0,\sum\limits_{i=1}^k a_i \leq 10^6$

题目描述

At Moscow Workshops ICPC team gets a balloon for each problem they solved first. Team MSU Red Panda got so many balloons that they didn't know how to spend them. So they came up with a problem with them. There are several balloons, not more than $ 10^6 $ in total, each one is colored in one of $ k $ colors. We can perform the following operation: choose $ k-1 $ balloons such that they are of $ k-1 $ different colors, and recolor them all into remaining color. We can perform this operation any finite number of times (for example, we can only perform the operation if there are at least $ k-1 $ different colors among current balls). How many different balloon configurations can we get? Only number of balloons of each color matters, configurations differing only by the order of balloons are counted as equal. As this number can be very large, output it modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains a single integer $ k $ ( $ 2 \le k \le 10^5 $ ) —the number of colors. The second line contains $ k $ integers $ a_1, a_2, \ldots, a_k $ ( $ 0 \le a_i $ ) —initial configuration of balloons. $ a_i $ is number of balloons of color $ i $ . The total number of balloons doesn't exceed $ 10^6 $ . In other words, $ a_1 + a_2 + a_3 + \ldots + a_k \le 10^6 $ .

输出格式

Output number of possible configurations modulo $ 998244353 $ .

输入输出样例

输入样例 #1

3
0 1 2

输出样例 #1

3

输入样例 #2

4
1 1 1 1

输出样例 #2

5

输入样例 #3

5
0 0 1 2 3

输出样例 #3

1

输入样例 #4

3
2 2 8

输出样例 #4

31

说明

In the first example, there are $ 3 $ configurations we can get: $ [0, 1, 2] $ , $ [2, 0, 1] $ , $ [1, 2, 0] $ . In the second example, we can apply the operation not more than once, and possible configurations are: $ [1, 1, 1, 1] $ , $ [0, 0, 0, 4] $ , $ [0, 0, 4, 0] $ , $ [0, 4, 0, 0] $ , $ [4, 0, 0, 0] $ . In the third example, we can't apply any operations, so the only achievable configuration is the starting one.