CF466D Increase Sequence

cloud2764scallop_eve · 2024-01-02 19:50:41 · 题解

题意

给定一个序列 a，每次操作可以将区间 [l, r] 中的所有元素加一，要求最后使所有元素等于 h。

要求：

1. 任意两个区间的左右端点互不重合（l1 \neq l2 且 r1 \neq r2）；
2. 对 10^9 + 7 取模。

思路

首先，可以考虑预处理出一个新的序列，表示出原数列中每个数与 h 的差，这样可以节约一定的时间复杂度。这里约定 c_i = a_i - a_{i - 1}，将问题转换为了如何使序列 c 全部归零。

现在考虑 c_i 可能的几种情况：

• 1. $i$ 处其实什么都没有； 2. $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;
}