AT_abc313_g [ABC313G] Redistribution of Piles

题目背景

管理备注：atcoder library 提供计算 $\sum\limits_i\left\lfloor\dfrac{ai+b}{c}\right\rfloor$ 的函数，使得本题使用和不使用 atcoder library 的难度相差过大，故本题评灰。

题目描述

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

• 从所有至少有 $1$ 个石子的盘子中各取出 $1$ 个石子，并将这些石子放入袋子中。
• 从袋子中取出 $N$ 个石子，并将每个盘子上各放 $1$ 个石子。仅当袋子中至少有 $N$ 个石子时，才能进行此操作。

操作结束后，第 $i$ 个盘子上的石子数为 $b_i$。请计算所有可能的长度为 $N$ 的整数序列 $(b_1,\ b_2,\ \dots,\ b_N)$ 的种数，并对 $998244353$ 取模。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

输出所有可能的 $(b_1,\ b_2,\ \dots,\ b_N)$ 的种数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3
3 1 3

输出 #1

7

输入输出样例 #2

输入 #2

1
0

输出 #2

1

输入输出样例 #3

输入 #3

5
1 3 5 7 9

输出 #3

36

输入输出样例 #4

输入 #4

10
766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044

输出 #4

666174028

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq a_i \leq 10^9$

样例解释 1

例如，按照以下步骤操作，可以得到 $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

操作后可能得到的 $b$ 只有 $(0)$ 这一种。

由 ChatGPT 4.1 翻译