#P13643. [ARC162D] Smallest Vertices

    ID: 12845 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-贡献法Prüfer 序列0/1 背包计数 DP倒序更新避免重复使用阶乘逆元预处理滚动数组

[ARC162D] Smallest Vertices

题目描述

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

给定一个非负整数序列 d=(d1,d2,…,dN)d=(d_1,d_2,\ldots,d_N),其总和为 N−1N-1。

在编号为 11 到 NN 的顶点中,以顶点 11 为根的 NN 个顶点的有根有向树中,满足以下条件的树被称为好树:

  • 顶点 i (1≤i≤N)i\ (1\leq i \leq N) 的出度为 did_i。

进一步地,对于好树中的每个顶点 vv,定义 f(v)f(v) 为“顶点 vv 的子树中包含的所有顶点(包括 vv 本身)编号的最小值”。满足 f(v)=vf(v)=v 的顶点称为好顶点。

请计算所有好树中好顶点的个数之和,并对 998244353998244353 取模后输出。

输入格式

输入通过标准输入给出,格式如下:

NN d1d_1 d2d_2 …\ldots dNd_N

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
2 0 1 0

输出 #1

7

输入输出样例 #2

输入 #2

10
3 1 0 0 2 0 1 2 0 0

输出 #2

37542

说明/提示

限制条件

  • 2≤N≤5002 \leq N \leq 500
  • 0≤di≤N−10 \leq d_i \leq N-1
  • d1≥1d_1 \geq 1
  • ∑i=1Ndi=N−1\sum_{i=1}^N d_i = N-1
  • 输入的所有数均为整数

样例解释 1

存在如下 22 种好树。被涂成蓝色的顶点为好顶点。

对于每棵树,好顶点的数量分别为 44 和 33,因此答案为 77。