← 返回题目列表

AtCoder · arc162_d

D. 最小顶点

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

分数: 700 点

问题陈述

在此问题中,有根有向树是所有边都从根指向叶子的有根树。

给你一个非负整数序列 d=(d_1,d_2,\ldots,d_N) 总和 N-1.

其中 N- 顶点有根的有向树,顶点编号 1 to N 和顶点 1 作为根,a 好树 满足以下条件:

  • 顶点的出度 i\ (1\leq i \leq N) is d_i.

此外,对于一个顶点 v 一棵好树,让 f(v) 为顶点的最小顶点数(包括 v) 在以顶点为根的子树中 v,和 v 被称为 好顶点 如果满足 f(v)=v.

求所有好树的好顶点数的总和,模 998244353.

约束

  • 2 \leq N \leq 500
  • 0 \leq d_i \leq N-1
  • d_1 \geq 1
  • \sum_{i=1}^N d_i = N-1
  • 所有输入值均为整数。

输入

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

N
d_1 d_2 \ldots d_N

输出

打印答案。


示例输入 1

4
2 0 1 0

示例输出 1

7

有两棵好树,如下图。蓝色顶点是好的顶点。

对于这些树,有 4 和 3 分别是好的顶点,所以答案是 7.


示例输入 2

10
3 1 0 0 2 0 1 2 0 0

示例输出 2

37542