Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届省赛真题-数组切分
题目 2676:

蓝桥杯2022年第十三届省赛真题-数组切分

时间限制: 1s 内存限制: 512MB 提交: 409 解决: 78

题目描述

已知一个长度为 N 的数组:A1, A2, A3, ...AN 恰好是 1 ∼ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个,最多 N 个) 连续的子数组,并且每个子数组中包含的整数恰好可以组成一段连续的自然数。

例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法:

{1}{3}{2}{4}:每个单独的数显然是 (长度为 1 的) 一段连续的自然数

{1}{3, 2}{4}:{3, 2} 包含 2 到 3,是 一段连续的自然数,另外 {1} 和 {4} 显然也是。

{1}{3, 2, 4}:{3, 2, 4} 包含 2 到 4,是 一段连续的自然数,另外 {1} 显然也是。

{1, 3, 2}{4}:{1, 3, 2} 包含 1 到 3,是 一段连续的自然数,另外 {4} 显然也是。

{1, 3, 2, 4}:只有一个子数组,包含 1 到 4,是 一段连续的自然数

输入格式

第一行包含一个整数 N。第二行包含 N 个整数,代表 A 数组。

输出格式

输出一个整数表示答案。由于答案可能很大,所以输出其对 1000000007 取模后的值。

样例输入

4
1 3 2 4

样例输出

5

提示

对于 30% 评测用例,1 ≤ N ≤ 20. 

对于 100% 评测用例,1 ≤ N ≤ 10000. 

标签