← 返回题目列表

AtCoder · joi2019_yo_f

F. 座位

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

配点: 100 点

問題文

2XXX年,世界各国排列成一条直线。 有N 个国家, 它的编号为1, 2, ..., N 。 对于i = 1, 2, ..., N - 1 ,国家/地区 i 和国家 连接 i + 1 是邻国。

在今年的国际信息奥运会上, 来自 i 从 A_i 玩家参与。作为国际信息学奥林匹克技术委员会的成员,您负责制定比赛的座位表。由于比赛场地狭长,大家都排成一排。 决定将球员分配到 A_1 + A_2 + ... + A_N 座位。为了防止欺诈,来自同一国家或邻国的运动员不得被分配到相邻的座位。

有多少种方式为玩家分配座位?这个数字可能非常大,所以我们 我想求除以 10007 后的余数。

制約

  • 1 ≦ N ≦ 100
  • 1 ≦ A_i ≦ 4 (1 ≦ i ≦ N)

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 ... A_N

出力

为玩家分配座位的方式数量 除以 10007 后的余数 1 以行的形式输出。

小課題

  1. (6 点) N ≦ 5,A_i ≦ 2 (1 ≦ i ≦ N)
  2. (14 点) N ≦ 10,A_i ≦ 3 (1 ≦ i ≦ N)
  3. (80 点)没有额外的限制。

入力例 1

4
2 1 1 1

出力例 1

4

国 1 加入 2 玩家 如果我们将其表示为 1 和 按字典顺序比较 1',国 2 加入 1 玩家 如果我们将其表示为 2,国 3 加入 1 玩家 如果我们将其表示为 3,国 4 加入 1 玩家 如果我们将其表示为 4 ,则使用以下方法为玩家分配座位: 4 排列街道的可能方法:

  • 1, 3, 1', 4, 2
  • 1', 3, 1, 4, 2
  • 2, 4, 1, 3, 1'
  • 2, 4, 1', 3, 1

入力例 2

5
1 2 3 2 1

出力例 2

0

在此输入示例中,不存在满足条件的座位表。


入力例 3

6
1 2 3 3 2 1

出力例 3

4754

在此示例输入中,为玩家分配座位的方式是 24768 既然有很多方法, 10007 所得的余数 请输出 4754 。 你只需要砍掉