【CODEFORCES】 D. Increase Sequence

本文主要是介绍【CODEFORCES】 D. Increase Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Peter has a sequence of integers a1, a2, ..., an. Peter wants all numbers in the sequence to equal h. He can perform the operation of "adding one on the segment [l, r]": add one to all elements of the sequence with indices from l to r (inclusive). At that, Peter never chooses any element as the beginning of the segment twice. Similarly, Peter never chooses any element as the end of the segment twice. In other words, for any two segments [l1, r1] and [l2, r2], where Peter added one, the following inequalities hold: l1 ≠ l2 and r1 ≠ r2.

How many distinct ways are there to make all numbers in the sequence equal h? Print this number of ways modulo 1000000007 (109 + 7). Two ways are considered distinct if one of them has a segment that isn't in the other way.

Input

The first line contains two integers n, h (1 ≤ n, h ≤ 2000). The next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 2000).

Output

Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Sample test(s) 
input 
3 2
1 1 1
output 
4
input 
5 1
1 1 1 1 1
output 
1
input 
4 3
3 2 1 1
output 
0

题解：这题好难想.....因为我是看了别人的题解才写出来的，所以我就不多说了.....以下是别人的题解：别人的题解，感觉这个写的比较好，除了这个以外还有一个，不过感觉他表述上有些问题，这个。

以下是我的代码，写出来其实不要5分钟，可我想却想了好久。

#include <iostream>
#include <cstdio>using namespace std;int n,h;
long long t,ans,a[2003],b[2003];
int main()
{scanf("%d%d",&n,&h);for (int i=1;i<=n;i++){scanf("%d",&t);a[i]=h-t;}for (int i=1;i<=n+1;i++) b[i]=a[i]-a[i-1];t=0; ans=1;for (int i=1;i<=n+1;i++){if (b[i]==1) t++;else if (b[i]==-1) ans*=t--;else if (b[i]==0) ans*=(t+1);else{cout <<0<<endl;return 0;}ans=ans%1000000007;}cout <<ans<<endl;return 0;
}

这篇关于【CODEFORCES】 D. Increase Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！