← 返回题目列表

AtCoder · abc313_g

G. 桩的重新分布

中文机器翻译题面 查看原题

分数: 625 点

问题陈述

有 N 车牌编号 1 通过 N。 菜品 i 有 a_i 上面有石头。 还有一个空袋子。
您可以按任意顺序执行任意次数(可能为零)以下两种操作。

  • 从每个带有一颗或多颗石子的盘子中取出一颗石子。 将取出的石头放入袋子中。
  • 采取 N 从袋子里拿出石头,然后在每个盘子里放一颗石头。 只有当袋子有时才能执行此操作 N 或更多石头。

让 b_i 是板上石子的数量 i 完成操作后。 打印数字,模数 998244353,整数序列 (b_1, b_2, \dots, b_N) 长度 N 可能由操作产生。

约束

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

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 \dots a_N

输出

打印数字,模数 998244353,可能的序列 (b_1, b_2, \dots, b_N).


示例输入 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