Problem1179--#6094. 「Codeforces Round #418」归乡迷途

1179: #6094. 「Codeforces Round #418」归乡迷途

Time Limit: 2 Sec  Memory Limit: 1024 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

日が暮れてる　年も暮れてる　途方に暮れちゃってる
黄昏降临，岁暮到来，路途变得一片迷茫

有一张 nnn 个节点组成的无向图，点从 111 至 nnn 编号，图中没有重边和自环。我们不知道它的确切形态，但是它满足以下条件：

  • 由任一节点至节点 111 的最短路径（经过边数最少的路径）存在且唯一；
  • 令 ℓi\ell_iℓ​i​​ 表示由节点 iii 至节点 111 的最短路径上边的数目，那么对于所有 2≤i≤n2 \leq i \leq n2≤i≤n，有 ℓi≥ℓi−1\ell_i \geq \ell_{i-1}ℓ​i​​≥ℓ​i−1​​ 成立；
  • 节点 iii 的度数给定，为 did_id​i​​，并且所有 did_id​i​​ 均等于 222 或 333。

请计算满足条件的不同的图的数目，输出其除以 109+710^9 + 710​9​​+7 的余数。两张无向图不同当且仅当存在点对 (u,v) (1≤u<v≤n)(u, v) \ (1 \leq u < v \leq n)(u,v) (1≤u<v≤n) 使得其中一张图中 (u,v)(u, v)(u,v) 间有边而另一张图中没有。

输入格式

输入的第一行包含一个正整数 nnn —— 节点的数目。

第二行包含 nnn 个空格分隔的整数 d1,d2,…,dnd_1, d_2, \ldots, d_nd​1​​,d​2​​,…,d​n​​ —— 依次为节点 1,2,…,n1, 2, \ldots, n1,2,…,n 的度数。输入保证所有 did_id​i​​ 之和为偶数。

输出格式

输出一个整数 —— 满足条件的不同的图的数目除以 109+710^9 + 710​9​​+7 所得的余数。

样例

样例输入 1

4
3 2 3 2

样例输出 1

1

样例解释 1

样例 1 中，满足条件的图有且仅有下图中的一张，其中节点 2,3,42, 3, 42,3,4 至节点 111 的最短路径均经过 111 条边。

Sample 1

样例输入 2

5
2 3 3 2 2

样例输出 2

2

样例解释 2

样例 2 中，满足条件的图有且仅有下图中的两张。

Sample 2

样例输入 3

5
2 2 2 2 2

样例输出 3

2

样例输入 4

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

样例输出 4

82944

数据范围与提示

3≤n≤4003 \leq n \leq 4003≤n≤400
2≤di≤32 \leq d_i \leq 32≤d​i​​≤3

子任务 1　n≤10n \leq 10n≤10；
子任务 2　n≤50n \leq 50n≤50；
子任务 3　n≤80n \leq 80n≤80；
子任务 4　没有附加限制。

遠回りでも　特別な道
即使迂回而行，亦是别样的旅途
遠回りでも　遠回りじゃない
即使迂回而行，也浑然不觉
　　　　　　　　　　　　——「帰り道」

Source/Category

 
[Submit] [Status]