/ TYWZ / 题库 /

2019.2.13 Problem C - count

2019.2.13 Problem C - count

题目描述

有一个含\(n\)个点的无向图,这个图本身是未知的,但你知道关于它的一些信息(下文中点的标号从1开始计数):
* 它是一个简单无权图,也就是说,它没有重边自环,所有边的权均为1;
* 从1号点到任意点的最短路都是唯一的。设\(l_i\)是从1号点出发到达\(i\)号点的最短路长度,你虽然不知道\(l_i\)具体是多少,但知道\(l_i\)关于\(i\)非严格单调递增。换句话说,对于\(2 \leq i \leq n\),有\(l_{i-1} \leq l_i\);
* 每个点的度(与之直接相连的边的个数)\(d_i\)都是给定的,且只可能是2或3。
你想知道共有多少个满足条件的无向图,由于答案可能很大,你只需给出答案模\({10}^9+7\)的值即可

输入格式

第一行一个正整数\(n\);
第二行n个正整数依次表示每个节点的度\(d_1, d_2 \cdots d_n\)。

输出格式

一个非负整数,表示答案模\({10}^9+7\)的值。

样例1

输入

5
2 3 3 2 2

输出

2

样例2

输入

20
2 2 2 2 3 2 3 2 2 2 2 2 2 2 2 2 2 3 3 2

输出

82944

样例说明

第一个样例对应以下两种情况:

数据规模、时空限制

对于30%的数据,\(n \leq 4\)
对于40%的数据,\(n \leq 5\)
对于100%的数据,\(3 \leq n \leq 50, \quad d_i \in \{ 2,3 \} \)
时间限制1s,空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人:于剑

信息

难度
9
分类
动态规划 点击显示
标签
(无)
递交数
78
已通过
1
通过率
1%
上传者

相关