CFGYM102394I CCPC2019哈尔滨 I题 Interesting Permutations

签到题我都不会做，我爬了。

首先检测一些明显非法的情况:

1. $h_i\geq n$，明显不可能，$h_i$上限是$n-1$

2. $h_i<h_{i-1}$(对于$i\geq 2$)，最大值不会减小，最小值不会增大，所以$h_i$一定是单调不减的。

3. $h_1\neq 0$，这很显然。

4. $h_n\neq n-1$这也很显然。

然后我们考虑从第$2$个元素开始枚举，我们维护一个`gap`变量，用以存储”在当前这个位置，一共有多少个位置可以填数，并且保证填了数之后不影响当前位置前缀最大值和前缀最小值的取值”。当前枚举到第$i$个元素时：

• 如果$h_i=h_{i-1}$，那就说明当前这个位置的值没有改变前缀最值的分布，那么总答案就可以乘上`gap`（因为有这么多的方案数让我们来填，并且填了后不影响前缀最值），并且 `gap`要减掉1，因为我们填了个数后占了一个空位。
• 如果$h_i>h_{i-1}$，那就说明当前这个位置的值改变了前缀最大值或者前缀最小值二者之一，那么总答案乘上2。同时`gap`要加上$h_i-h_{i-1}-1$，因为我们新创造了这么多的空位。

#include <algorithm>
#include <cstdio>
#include <iostream>

using int_t = long long;

using std::cin;
using std::cout;
using std::endl;

const int_t mod = 1e9 + 7;
const int_t LARGE = 1e5 + 10;
int_t arr[LARGE + 1];
int_t n;
int main() {
    std::ios::sync_with_stdio(false);
    int_t T;
    cin >> T;
    while (T--) {
        cin >> n;
        bool fail = false;
        for (int_t i = 1; i <= n; i++) {
            cin >> arr[i];
            if (arr[i] < arr[i - 1])
                fail = true;
            if (i == 1 && arr[i] != 0)
                fail = true;
            if (i == n && arr[i] != n - 1)
                fail = true;
            if (arr[i] >= n)
                fail = true;
        }
        if (fail) {
            cout << 0 << endl;
            continue;
        }
        int_t prod = 1;
        int_t sec = 0;
        for (int_t i = 2; i <= n; i++) {
            if (arr[i] == arr[i - 1]) {
                prod = prod * sec % mod;
                sec--;  //消耗了一个中间空位
            }
            if (arr[i] > arr[i - 1]) {
                prod = prod * 2 % mod;
                sec = (sec + arr[i] - arr[i - 1] - 1 + mod) % mod;
            }
        }
        cout << prod << endl;
    }
    return 0;
}