/ CWOI / 题库 /

2017.07.19 P1 等价序列

2017.07.19 P1 等价序列

题目描述

peter 有一个整数序列 \(a_1\), \(a_2\), …, \(a_n\),他想让序列中所有的数都变成 h。他可以执行以下操作:选择一个区间 \([l, r]\),让区间内的所有数增加 1。多次选择不同区间可以让整个序列都变成 h。不过在选择区间时,任何区间的左端点不能一样,右端点也不能一样。
问你有多少种方案能让序列中的 n 个元素都变成 h。由于方案数比较多,输出方案数对 1000000007 (\(10^9 + 7\))取模的结果。

输入格式

第一行两个整数 n, h;
接下来 n 个整数 \(a_1\), \(a_2\), …, \(a_n\)。

输出格式

输出方案数取模的结果。

样例1

输入

3 2
1 1 1

输出

4

样例2

输入

5 1
1 1 1 1 1

输出

1

样例3

输入

4 3
3 2 1 1 1

输出

0

数据范围

对于 30%的数据,1 \(\leq\) n, h \(\leq\) 100,0 \(\leq\) \(a_i\) \(\leq\) 100;
对于 100%的数据,1 \(\leq\) n, h \(\leq\) 2000,0 \(\leq\) \(a_i\) \(\leq\) 2000。

限制

1s

样例解释

样例 1:方案有 \([1, 1]\), \([2, 2]\), \([3, 3]\)、\([1, 1]\), \([2, 3]\)、\([1, 2]\), \([3, 3]\)、\([1, 3]\) 四种方案。

来源

Codeforces466D
CWOI新高二专题测试十六

信息

难度
3
分类
动态规划 点击显示
标签
(无)
递交数
6
已通过
4
通过率
67%
上传者