题意
给定一个序列 \(a\)，每次操作可以将区间 \([l, r]\) 中的所有元素加一，要求最后使所有元素等于 \(h\)。
要求：
- 任意两个区间的左右端点互不重合（\(l1 \neq l2\) 且 \(r1 \neq r2\)）；
- 对 \(10^9 + 7\) 取模。
思路
首先，可以考虑预处理出一个新的序列，表示出原数列中每个数与 \(h\) 的差，这样可以节约一定的时间复杂度。这里约定 \(c_i = a_i - a_{i - 1}\)，将问题转换为了如何使序列 \(c\) 全部归零。
现在考虑 \(c_i\) 可能的几种情况：
- \(c_i > 1\)：无解。由于每个区间最多选一次，如果 \(c_i > 1\)，这意味着 \(i\) 处需要大于一次被选择，不符合题意。
- \(c_i = 1\)：此时一定有一个起始点 \(l\) 在 \(i\) 处。这里我们维护一个 \(cnt\)，表示 \(l\) 的个数。那么在此时，\(cnt\) 加一。
- \(c_i = -1\)：此时需要在 \(i\) 处在设置一个 \(r\)，所以需要和前面的某个 \(l\) 匹配，故将答案乘以 \(cnt\)，再将 \(cnt\) 减一。
- \(c_i = 0\)：这时考虑几种情况：
- \(i\) 处其实什么都没有；
- \(i\) 处同时作为一个 \(l\) 和一个 \(r\)。那么就需要对当前位置的 \(l\) 进行匹配，将答案乘上 \(cnt + 1\)。
代码
友情提示：一定要开 long long。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7, N = 2005;
int a[N], b[N];
int n, h, cnt = 0, ans = 1;
signed main() {
while (~scanf("%lld%lld", &n, &h)) {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
a[i] = h - a[i];
}
for (int i = 1; i <= n + 1; i++)
b[i] = a[i] - a[i - 1];
for (int i = 1; i <= n + 1; i++) {
if (b[i] == 1) cnt++;
else if (b[i] == 0) {
ans = ans * (cnt + 1) % mod;
} else if (b[i] == -1) {
ans = ans * cnt % mod;
cnt--;
} else {
printf("0\n");
return 0;
}
}
printf("%lld\n", ans);
}
return 0;
}