题目详情题解（0）讨论（0）提交记录（0）

AT_sumitb2019_e.Colorful Hats 2

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 NN 个人排成一列，按照从前到后的顺序编号为 1,2,3,…,N1, 2, 3, \ldots, N。每个人都戴着一顶帽子，帽子的颜色可以是红色、蓝色或绿色中的一种。

现在，第 ii 号的人说：

  • “在我前面，戴着和我同样颜色帽子的人恰好有 AiA_i 个。”

假设所有人的发言都是真实的，请你计算 NN 个人帽子颜色的所有可能组合数。

由于答案可能非常大，请输出对 10000000071000000007 取模后的结果。

输入格式

输入通过标准输入给出，格式如下：

NN A1A_1 A2A_2 A3A_3 …\ldots ANA_N

输出格式

输出 NN 个人帽子颜色的所有可能组合数，对 10000000071000000007 取模后的结果。

输入输出样例

  • 输入#1

    6
0 1 2 3 4 5

    输出#1

    3

  • 输入#2

    3
0 0 0

    输出#2

    6

  • 输入#3

    54
0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17

    输出#3

    115295190

说明/提示

限制条件

  • 1≤N≤1000001 \leq N \leq 100000
  • 0≤Ai≤N−10 \leq A_i \leq N-1
  • 输入中的所有值均为整数

样例解释 1

可以考虑以下 33 种组合：

  • 红，红，红，红，红，红
  • 蓝，蓝，蓝，蓝，蓝，蓝
  • 绿，绿，绿，绿，绿，绿

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页