[蓝桥杯 2022 国 C] 数组个数

Luogu

IDLGP8810

Time1000ms

Memory128MB

DifficultyP4

动态规划 DP2022蓝桥杯国赛

小蓝有一个长度为 $n$ 的数组 $B = (b_0,b_1,\cdots,b_{n−1})$，数组 $B$ 是由另一个长度为 $n$ 的环形数组 $A = (a_0,a_1,\cdots,a_{n−1})$ 经过一次相邻最大化操作得到的，其中 $a_i$ 与 $a_{i+1}$ 相邻，$a_0$ 与 $a_{n−1}$ 相邻。形式化描述为： $$ b_i= \begin{cases} \max\{a_{n-1},a_0,a_1\}& i=0\\ \max\{a_{i-1},a_i,a_{i+1}\}& 0<i<n-1\\ \max\{a_{n-2},a_{n-1},a_0\}& i=n-1\\ \end{cases} $$ 小蓝想知道，可能有多少个满足条件的数组 $A$，经过一次相邻最大化操作后能得到数组 $B$，注意 $A$ 中的每个元素都要求为非负整数。 ## Input 输入的第一行包含一个整数 $n$，表示数组长度。第二行包含 $n$ 个整数 $b_0,b_1,\cdots,b_{n−1}$，相邻两个整数之间用一个空格分隔。 ## Output 输出一行包含一个整数表示答案，答案可能很大，请输出答案除以 $1000000007$（即 $10^9+7$）后的余数。 [samples] ## Note **【样例说明】** 可能的 $A$ 数组有 $7$ 个：$(6,0,0,1,8)$、$(6,0,1,0,8)$、$(6,0,1,1,8)$、$(6,1,0,0,8)$、$(6,1,0,1,8)$、$(6,1,1,0,8)$、$(6,1,1,1,8)$。【评测用例规模与约定】对于 $30\%$ 的评测用例，$3≤n≤10$；对于 $60\%$ 的评测用例，$3≤n≤100$；对于所有评测用例，$3 ≤ n ≤ 1000$，$0 ≤ b_i ≤ 10$。蓝桥杯 2022 国赛 C 组 G 题。

Samples

Input #1

5
8 6 1 8 8

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2022 国 C] 数组个数",
    "description": {
      "content": "  小蓝有一个长度为 $n$ 的数组 $B = (b_0,b_1,\\cdots,b_{n−1})$，数组 $B$ 是由另一个长度为 $n$ 的环形数组 $A = (a_0,a_1,\\cdots,a_{n−1})$ 经过一次相邻最大化操作得到的，其中 $a_i$ 与 $a_{i+1}$ 相邻，$a_0$ 与 $a_{n−1}$ 相邻。 形式化描述为： $$ b_i= \\begin{cases} ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8810"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小蓝有一个长度为 $n$ 的数组 $B = (b_0,b_1,\\cdots,b_{n−1})$，数组 $B$ 是由另一个长度为 $n$ 的环形数组 $A = (a_0,a_1,\\cdots,a_{n−1})$ 经过一次相邻最大化操作得到的，其中 $a_i$ 与 $a_{i+1}$ 相邻，$a_0$ 与 $a_{n−1}$ 相邻。\n\n形式化描述为：\n\n$$\nb_i=\n\\begin{cases}\n\\m...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments