Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-数组个数(C/C++/Java组)
题目 2705:

蓝桥杯2022年第十三届决赛真题-数组个数(C/C++/Java组)

时间限制: 3s 内存限制: 512MB 提交: 79 解决: 15

题目描述

小蓝有一个长度为 n 的数组 B = (b0, b1, · · · , bn−1),数组 B 是由另一个长度为 n 的环形数组 A = (a0, a1, · · · , an−1) 经过一次相邻最大化操作得到的,其中 ai 与 ai+1 相邻,a0 与 an−1 相邻。 

形式化描述为: 

蓝桥杯2022年第十三届决赛真题-数组个数(C/C++/Java组)

小蓝想知道,可能有多少个满足条件的数组 A,经过一次相邻最大化操作后能得到数组 B,注意 A 中的每个元素都要求为非负整数。

输入格式

输入的第一行包含一个整数 n ,表示数组长度。

第二行包含 n 个整数 b0, b1, · · · , bn−1,相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示答案,答案可能很大,请输出答案除以 1000000007 后的余数。

样例输入

5
8 6 1 8 8

样例输出

7

提示

可能的 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 ≤ bi ≤ 10。

标签